How can one summarize a massive data set "on the fly", i.e., without even having seen it in its entirety? In this paper, we address problem of extracting representative elements from large stream data. I.e., would like to select subset say k points that are most according some objective function. Many natural notions "representativeness" satisfy submodularity, an intuitive notion diminishing returns. Thus, such problems be reduced maximizing submodular function subject cardinality...

Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trials, to communication networks, Web search advertising. In many these application domains learner may be constrained by one or more supply (or budget) limits, addition customary limitation on time horizon. The literature lacks a general encompassing sorts problems. We introduce such model, called "bandits with...

There has been much progress recently on improved approximations for problems involving submodular objective functions, and many interesting techniques have developed. However, the resulting algorithms are often slow impractical. In this paper we develop that match best known approximation guarantees, but with significantly running times, maximizing a monotone function f: 2[n] → R+ subject to various constraints. As in previous work, measure number of oracle calls which is dominating term...

Is it possible to maximize a monotone submodular function faster than the widely used lazy greedy algorithm (also known as accelerated greedy), both in theory and practice? In this paper, we develop first linear-time for maximizing general subject cardinality constraint. We show that our randomized algorithm, STOCHASTIC-GREEDY, can achieve (1 − 1/e ε) approximation guarantee, expectation, optimum solution time linear size of data independent empirically demonstrate effectiveness on functions...

Previous chapter Next Full AccessProceedings Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Fast algorithms for maximizing submodular functionsAshwinkumar Badanidiyuru and Jan VondrákAshwinkumar Vondrákpp.1497 - 1514Chapter DOI:https://doi.org/10.1137/1.9781611973402.110PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract There has been much progress recently improved approximations problems involving objective...

We study online procurement markets where agents arrive in a sequential order and mechanism must make an irrevocable decision whether or not to procure the service as agent arrives. Our mechanisms are subject budget constraint designed for stochastic settings which bidders either identically distributed or, more generally, permuted random order. Thus, problems we contribute literature on budget-feasible well secretary learning auctions.

Multi-armed bandit problems are the predominant theoretical model of exploration-exploitation tradeoffs in learning, and they have countless applications ranging from medical trials, to communication networks, Web search advertising. In many these application domains, learner may be constrained by one or more supply (or budget) limits, addition customary limitation on time horizon. The literature lacks a general encompassing sorts problems. We introduce such model, called bandits with...

Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes set functions can be sketched. More formally, let f a function mapping subsets some ground [n] to non-negative real numbers. We say that f' is an α-sketch if for every S, value f'(S) lies between f(S)/α f(S), specified poly(n) bits.We show subadditive there exists where α = n1/2. O(polylog(n)). Furthermore, provide algorithm finds these sketches with...

We study contextual bandits with ancillary constraints on resources, which are common in real-world applications such as choosing ads or dynamic pricing of items. design the first algorithm for solving these problems that handles constrained resources other than time, and improves over a trivial reduction to non-contextual case. consider very general settings both (arbitrary policy sets, e.g. Dudik et al. (UAI'11)) resource (bandits knapsacks, Badanidiyuru (FOCS'13)), prove regret guarantee...

The Adaptive Seeding problem is an algorithmic challenge motivated by influence maximization in social networks: One seeks to select among certain accessible nodes a network, and then select, adaptively, neighbors of those as they become order maximize global objective function. More generally, adaptive seeding stochastic optimization framework where the choices first stage affect realizations second stage, over which we aim optimize.Our main result (1 -- 1/e)2-approximation for any monotone...

Previous chapter Next Full AccessProceedings Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)Locally Adaptive Optimization: Seeding for Monotone Submodular FunctionsAshwinkumar Badanidiyuru, Christos Papadimitriou, Aviad Rubinstein, Lior Seeman, and Yaron SingerAshwinkumar Singerpp.414 - 429Chapter DOI:https://doi.org/10.1137/1.9781611974331.ch31PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAboutAbstract The problem is an...

We study the complexity of maximum coverage problem, restricted to set systems bounded VC-dimension. Our main result is a fixed-parameter tractable approximation scheme: an algorithm that outputs (1-ε)-approximation maximum-cardinality union k sets, in running time $O(f(ε,k,d)⋅ poly(n)) where n problem size, d VC-dimension system, and f(ε,k,d) exponential (kd/ε)c for some constant c. complement this positive by showing function running-time bound cannot be replaced depending only on (ε,d) or...

We study combinatorial procurement auctions, where a buyer with valuation function v and budget B wishes to buy set of items. Each item i has cost ci the is interested in S that maximizes v(S) subject ∑i∈Sci ≤ β. Special cases auctions are well-studied problems from submodular optimization. In particular, when costs all equal (cardinality constraint), classic result by Nemhauser et al shows greedy algorithm provides an e/e-1 approximation.

Motivated by the problem of querying and communicating bidders' valuations in combinatorial auctions, we study how well different classes set functions can be sketched. More formally let f a function mapping subsets some ground [n] to non-negative real numbers. We say that f′ is an α-sketch if for every S, value f′(S) lies between f(S)/α f(S), specified poly(n) bits. show subadditive there exists where α = n1/2 · O(polylog(n)). Furthermore, provide algorithm finds these sketches with...

Motivated by online decision-making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their counterparts. We focus on problems that are amenable a constant factor approximation using greedy algorithm is robust local errors. For such problems, provide general framework efficiently transforms ones Blackwell approachability.

Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit receiver an unreliable network, even presence computationally unbounded adversary. In this article, we study inherent trade-off between three important parameters PRMT protocols, namely, network connectivity ( n ), round complexity r and communication by considering following generic question (which can be considered as holy grail problem)...

Motivated by online decision making in time-varying combinatorial environments, we study the problem of transforming offline algorithms to their counterparts. We focus on problems that are amenable a constant factor approximation using greedy algorithm is robust local errors. For such problems, provide general framework efficiently transforms ones Blackwell approachability. show resulting have [Formula: see text] (approximate) regret under full information setting. further introduce bandit...

In this paper, we introduce a novel technique for constrained submodular maximization, inspired by barrier functions in continuous optimization. This connection not only improves the running time maximization but also provides state of art guarantee. More precisely, maximizing monotone function subject to combination $k$-matchoid and $\ell$-knapsack constraint (for $\ell\leq k$), propose potential that can be approximately minimized. Once minimize up an $\epsilon$ error it is guaranteed have...