Online auction is the essence of many modern markets, particularly networked in which information about goods, agents, and outcomes revealed over a period time, agents must make irrevocable decisions without knowing future information. Optimal stopping theory, especially classic secretary problem , powerful tool for analyzing such online scenarios generally require optimizing an objective function input. The its generalization multiple-choice were under thorough study literature. In this...

An effective technique for solving optimization problems over massive data sets is to partition the into smaller pieces, solve problem on each piece and compute a representative solution from it, finally obtain inside union of solutions all pieces. This can be captured via concept composable core-sets, has been recently applied diversity maximization as well several clustering [7,15,8]. However, coverage submodular problems, impossibility bounds are known this [15]. In paper, we focus...

This paper considers a traditional problem of resource allocation: scheduling jobs on machines. One such recent application is cloud computing; arrive in an online fashion with capacity requirements and need to be immediately scheduled physical machines data centers. It often observed that the requested capacities are not fully utilized, hence offering opportunity employ overcommitment policy, is, selling resources beyond capacity. Setting right level can yield significant cost reduction for...

We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game we have a set selfish node players, each creating some incident links, goal is to minimize α times cost created links plus sum distances all other players. Fabrikant et al. proved an upper bound O(√α) on price anarchy, i.e., relative lack coordination. Albers, Eilts, Even-Dar, Mansour, Roditty show that anarchy constant for = O(√n) ≥...

Motivated by online ad allocation, we study the problem of simultaneous approximations for adversarial and stochastic budgeted allocation problem. This consists a bipartite graph G = (X, Y, E), where nodes Y along with their corresponding capacities are known beforehand to algorithm, X arrive online. When node arrives, its incident edges, respective weights revealed, algorithm can match it neighbor in Y. The objective is maximize weight final matching, while respecting capacities.When an...

We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion large collection objects (representing anything from robot swarm or firefighter team to map labels network messages) achieve global property while minimizing maximum average movement. particular, we consider goals achieving connectivity (undirected directed), between given pair vertices, independence (a dispersion problem),...

We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker. In this game we have a set selfish node players, each creating some incident links, goal is to minimize α times cost created links plus sum distances all other players. Fabrikant et al. proved an upper bound O (√α) on price anarchy: relative lack coordination. Albers, Eilts, Even-Dar, Mansour, Roditty show that anarchy constant for = (√ n ) ≥ 12 ⌈ lg...

Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inherent tradeoff between how general language is, allowing it to capture more elaborate games, and hard computationally optimize solve such games. One prominent the simple yet expressive Weighted Graph Games (WGGs) representation (Deng Papadimitriou, 1994), which maintains knowledge about synergies agents form of edge weighted graph. We consider problem finding optimal coalition...

Maximizing submodular functions under cardinality constraints lies at the core of numerous data mining and machine learning applications, including diversification, summarization, coverage problems. In this work, we study question in context streams, where elements arrive one a time, want to design low-memory fast update-time algorithms that maintain good solution. Specifically, focus on sliding window model, are asked solution considers only last W items.

Online bipartite matching is one of the most fundamental problems in online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) introduced an elegant algorithm for unweighted that achieves optimal competitive ratio 1- <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sup> /e. Aggarwal et al. (SODA 2011) later generalized their analysis to vertex-weighted case. Little known, however, about general edge-weighted problem aside from...

In the differentially private partition selection problem (a.k.a. set union, key discovery), users hold subsets of items from an unbounded universe. The goal is to output as many possible union users' sets while maintaining user-level differential privacy. Solutions this are a core building block for privacy-preserving ML applications including vocabulary extraction in corpus, computing statistics over categorical data, and learning embeddings user-provided items. We propose algorithm...

Motivated by online ad allocation, we study the problem of simultaneous approximations for adversarial and stochastic budgeted allocation problem. This consists a bipartite graph G = (X, Y, E), where nodes Y along with their corresponding capacities are known beforehand to algorithm, X arrive online. When node arrives, its incident edges, respective weights revealed, algorithm can match it neighbor in Y. The objective is maximize weight final matching, while respecting capacities.When an...

The online stochastic matching problem is a variant of bipartite in which edges are labeled with probabilities. A match will succeed the probability along that edge; this models, for instance, click user search advertisement. goal to maximize expected number successful matches. This was introduced by Mehta and Panigrahi (FOCS 2012), who focused on case where all probabilities graph equal. They gave 0.567-competitive algorithm vanishing probabilities, relative natural benchmark, leaving...

Feature selection is a fundamental problem in machine learning and data mining. The majority of feature algorithms are designed for running on single (centralized setting) they less applicable to very large datasets. Although there some distributed methods tackle this problem, most them distributing the horizontally which not suitable datasets with number features few instances. Thus, paper, we introduce novel vertically distributable method order speed up process be able handle scalable...

In the submodular welfare maximization (SWM) problem, input consists of a set $n$ items, each which must be allocated to one $m$ agents. Each agent $\ell$ has valuation function $v_\ell$, where $v_\ell(S)$ denotes obtained by this if she receives items $S$. The functions $v_\ell$ are all submodular; as is standard, we assume that they monotone and $v_\ell(\emptyset) = 0$. goal partition into disjoint subsets $S_1, S_2, \ldots ,S_m$ in order maximize social welfare, defined $\sum_{\ell 1}^m...

Streaming algorithms are generally judged by the quality of their solution, memory footprint, and computational complexity. In this paper, we study problem maximizing a monotone submodular function in streaming setting with cardinality constraint $k$. We first propose Sieve-Streaming++, which requires just one pass over data, keeps only $O(k)$ elements achieves tight $(1/2)$-approximation guarantee. The best previously known either achieve suboptimal $(1/4)$-approximation $Θ(k)$ or optimal...

Submodular optimization generalizes many classic problems in combinatorial and has recently found a wide range of applications machine learning (e.g., feature engineering active learning). For large-scale problems, we are often concerned with the adaptivity complexity an algorithm, which quantifies number sequential rounds where polynomially-many independent function evaluations can be executed parallel. While low is ideal, it not sufficient for distributed algorithm to efficient, since...