Recent work on “quiet planting” in combinatorial optimization aims to generate instances with a hidden solution that is hard to recover, typically by making the planted distribution statistically indistinguishable from uniform for specific algorithms, such as statistical queries. A prominent example is planted $k$-SAT, where $O(n^{k/2})$ clauses can be planted while maintaining indistinguishability from uniform instances, evidenced by prior hardness results which also align with findings in SAT refutation. Despite extensive research and practical use in benchmarking SAT solvers, the challenge of quietly planting multiple solutions while preserving hardness has remained an open problem. This work initiates the study of quiet planting with an arbitrary number of solutions, proposing the first method to construct quiet planting distributions for $k$-SAT formulas that accommodate more than one solution. We provide statistical query lower bounds for distinguishing these planted instances from uniform ones, and our method allows for planting solutions with arbitrary geometric relationships, including varying Hamming distances. A key innovation facilitating multiple solutions is the ability to incorporate arbitrary correlations between variable selection in clauses and their negation patterns, departing from prior approaches. We also investigate the worst-case complexity of SAT by showing the difficulty in distinguishing satisfiable instances with numerous solutions from unsatisfiable ones, addressing an open problem of Hsieh, Mohanty, and Xu (CCC’22). From a technical standpoint, we generalize the concept of $(r-1)$-wise uniformness in clause distributions, proving hardness holds if the marginal distribution over negation patterns is $(r-1)$-wise uniform, and reveal a connection to binary linear codes, demonstrating how a $[k, t, r]$ code can guide the planting of up to $2^t - 1$ solutions on $k$ variables with $(r-1)$-wise uniform negation distributions.

An important thread in the study of data-stream algorithms focuses on settings where stream items are active only for a limited time. We introduce a new expiration model, where each item arrives with its own arbitrary expiration time. The special case where items expire in the order that they arrive, which we call consistent expirations, contains the classical sliding-window model of Datar, Gionis, Indyk, and Motwani [SICOMP 2002] and its timestamp-based variant of Braverman and Ostrovsky [FOCS 2007]. Our first set of results explores the expiration streaming model and presents algorithms for several fundamental problems, including approximate counting, uniform sampling, and weighted sampling by efficiently tracking active items without explicitly storing them all. Naturally, these algorithms have many immediate applications, e.g., to range counting. Our second and main set of results for the expiration model designs algorithms for the diameter and k-center problems, where items are points in a metric space. Our results significantly extend those known for the special case of sliding-window streams by Cohen-Addad, Schwiegelshohn, and Sohler [ICALP 2016], and obtain a strictly better approximation factor for the diameter in the important special case of high-dimensional Euclidean metrics. We develop new decomposition and coordination techniques along with a geometric dominance framework to filter out redundant points based on both temporal and spatial proximity.

Replicable algorithm design has emerged as a central notion in algorithmic stability, strengthening both differential privacy and adaptive generalization by requiring that an algorithm, with high probability, produce the same output on independent datasets when run with the same randomness. A central open problem in this area is replicable median estimation, where existing algorithms are either computationally inefficient or require sample complexity exponential in \(\log^* |\chi|\), despite a polynomial information-theoretic lower bound. We resolve this gap by reducing replicable median estimation to the replicable interior point problem, for which we present a polynomial-time algorithm with sample complexity \(\operatorname{poly}(\log^* |\chi|)\). This yields polynomial-time replicable algorithms for median estimation, PAC learning of thresholds, and distribution learning under Kolmogorov distance—addressing open problems of Impagliazzo et al. [STOC’22] in polynomial time and improving prior results of Bun et al. [STOC’23]. Our approach introduces the technique of semi-replicable recursion, which enables recursive algorithms to maintain replicability even when subproblems depend on the data, providing a new framework for efficient replicable algorithm design.

In the contest design problem, initiated by Lazear and Rosen (JPE’81), there are n strategic contestants, each of whom decides an effort level. A contest designer with a fixed budget must then design a mechanism that allocates a prize pi to the i-th rank based on the outcome, to incentivize contestants to exert higher costly efforts and induce high-quality outcomes.

We study the problem of designing replication-proof bandit mechanisms when agents strategically register or replicate their own arms to maximize their payoff. Specifically, we consider Bayesian agents who only know the distribution from which their own arms' mean rewards are sampled, unlike the original setting of by Shin, Lee, and Ok AISTATS'22. Interestingly, with Bayesian agents in stark contrast to the previous work, analyzing the replication-proofness of an algorithm becomes significantly complicated even in a single-agent setting. We provide sufficient and necessary conditions for an algorithm to be replication-proof in the single-agent setting, and present an algorithm that satisfies these properties. These results center around several analytical theorems that focus on comparing the expected regret of multiple bandit instances, and therefore might be of independent interest since they have not been studied before to the best of our knowledge. We expand this result to the multi-agent setting, and provide a replication-proof algorithm for any problem instance. We finalize our result by proving its sublinear regret upper bound which matches that of Shin, Lee, and Ok AISTATS'22.

One of the classic problems in online decision-making is the secretary problem, where the goal is to hire the best secretary out of n rankable applicants or, in a natural extension, to maximize the probability of selecting the largest number from a sequence arriving in random order. Many works have considered generalizations of this problem where one can accept multiple values subject to a combinatorial constraint. The seminal work of Babaioff, Immorlica, Kempe, and Kleinberg (SODA'07, JACM'18) proposed the matroid secretary conjecture, suggesting that there exists an O(1)-competitive algorithm for the matroid constraint, and many works since have attempted to obtain algorithms for both general matroids and specific classes of matroids. The ultimate goal of these results is to obtain an e-competitive algorithm, and the strong matroid secretary conjecture states that this is possible for general matroids. One of the most important classes of matroids is the graphic matroid, where a set of edges in a graph is deemed independent if it contains no cycle. Given the rich combinatorial structure of graphs, obtaining algorithms for these matroids is often seen as a good first step towards solving the problem for general matroids. For matroid secretary, Babaioff et al. (SODA'07, JACM'18) first studied graphic matroid case and obtained a 16-competitive algorithm. Subsequent works have improved the competitive ratio, most recently to 4 by Soto, Turkieltaub, and Verdugo (SODA'18). In this paper, we break the 4-competitive barrier for the problem, obtaining a new algorithm with a competitive ratio of 3.95. For the special case of simple graphs (i.e., graphs that do not contain parallel edges) we further improve this to 3.77. Intuitively, solving the problem for simple graphs is easier as they do not contain cycles of length two. A natural question that arises is whether we can obtain a ratio arbitrarily close to e by assuming the graph has a large enough girth. We answer this question affirmatively, proving that one can obtain a competitive ratio arbitrarily close to e even for constant values of girth, providing further evidence for the strong matroid secretary conjecture. We further show that this bound is tight: for any constant g, one cannot obtain a competitive ratio better than e even if we assume that the input graph has girth at least g. To our knowledge, such a bound was not previously known even for simple graphs.

The Steiner Forest problem, also known as the Generalized Steiner Tree problem, is a fundamental optimization problem on edge-weighted graphs where, given a set of vertex pairs, the goal is to select a minimum-cost subgraph such that each pair is connected. This problem generalizes the Steiner Tree problem, first introduced in 1811, for which the best known approximation factor is 1.39 by [Byrka, Grandoni, Rothvoβ, and Sanità, 2010]. The celebrated work of [Agrawal, Klein, and Ravi, 1989], along with refinements by [Goemans and Williamson, 1992], established a 2-approximation for Steiner Forest over 35 years ago. Pioneering iterative rounding techniques by [Jain, 1998] later extended these results to higher connectivity settings. Despite the long-standing importance of this problem, breaking the approximation factor of 2 has remained a major challenge, raising suspicions that achieving a better factor might indeed be hard. In this paper, we break the approximation barrier of 2 by designing a novel deterministic algorithm that achieves a $\mathbf{2} \mathbf{- 1 0}^{\mathbf{- 1 1}}$ approximation for this fundamental problem. As a key component of our approach, we also introduce a novel dual-based local search algorithm for the Steiner Tree problem with an approximation guarantee of 1.943, which is of independent interest.

In this paper, we present the first dynamic algorithms for Dyck edit distance and tree edit distance that achieve subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a wellparenthesized expression (i.e., the Dyck language), while tree edit distance quantifies the minimum number of node insertions, deletions, and substitutions required to transform one rooted, ordered, and labeled tree into another. These problems have been studied extensively since the 1970s, with recent advances in both algorithmic efficiency and fine-grained complexity lower bounds. Despite this progress, no prior work has addressed efficient dynamic algorithms for these problems, even though many real-world applications involve evolving structured data such as LaTeX, JSON, XML, HTML, hierarchical datasets, and RNA secondary structures. We take the first step in this direction by designing new approximation algorithms for Dyck and tree edit distances in the dynamic setting. Our key technical contribution is a set of novel reduction and decomposition techniques that transform instances of Dyck and tree edit distance into efficiently maintainable instances of string edit distance. Leveraging existing dynamic algorithms for string edit distance, we obtain an $n^{o(1)}$ approximation for Dyck edit distance with $n^{o(1)}$ update time. This builds upon and significantly extends prior work on Dyck language decomposition ([Saha, FOCS’14] and [Koucký & Saks; SODA’23]). For tree edit distance, we introduce a new static reduction that improves the best-known approximation bound from $O\left(n^{3 / 4}\right)$ [Akutsu, Fukagawa, and Takasu; Algorithmica, 2010] to $\tilde{O}(\sqrt{n})$. Moreover, while the previous result was restricted to constant-degree trees, ours holds for arbitrary trees. We then extend our reduction dynamically, yielding a dynamic tree edit distance algorithm with an approximation factor of $n^{1 / 2+o(1)}$ and update time $n^{o(1)}$. A core component of our approach is a new dynamic maintenance algorithm for heavy-light decomposition, a widely used technique in tree algorithms. Given its broad applicability, we believe this result is of independent interest. Finally, we introduce a novel static and dynamic decomposition method that achieves an $\tilde{O}(k)$-approximation for tree edit distance when the tree edit distance is at most k; combined with the trivial bound $k \leq n$, this yields a deterministic $\tilde{O}(\sqrt{n})$-approximation. While similar decompositions exist for strings, no prior work has successfully extended them to trees. Our approach breaks this barrier, improving the best-known approximations for tree edit distance both in the static and dynamic setting. In the static setting, our algorithm runs in $\tilde{O}(n)$ time; in the dynamic setting, it only requires a polylogarithmic worst-case update time. The state-of-the-art near-lineartime static algorithm for tree edit distance previously achieved an $O(\sqrt{n})$-approximation [Boroujeni, Ghodsi, Hajiaghayi, and Seddighin; STOC’19].

The Maximum Submodular Matching (MSM) problem is a generalization of the classical Maximum Weight Matching (MWM) problem. In this problem, given a monotone submodular function f: 2^E → ℝ^{≥ 0} defined over subsets of edges of a graph G(V, E), we are asked to return a matching whose submodular value is maximum among all matchings in graph G(V, E). In this paper, we consider this problem in a fully dynamic setting against an oblivious adversary. In this setting, we are given a sequence 𝒮 of insertions and deletions of edges of the underlying graph G(V, E), along with an oracle access to the monotone submodular function f. The goal is to maintain a matching M such that, at any time t of sequence 𝒮, its submodular value is a good approximation of the value of the optimal submodular matching while keeping the number of operations minimal. We develop the first dynamic algorithm for the submodular matching problem, in which we maintain a matching whose submodular value is within expected (8 + ε)-approximation of the optimal submodular matching at any time t of sequence 𝒮 using expected amortized poly(log n, 1/(ε)) update time. Our approach incorporates a range of novel techniques, notably the concept of Uniform Hierarchical Caches (UHC) data structure along with its invariants, which lead to the first algorithm for fully dynamic submodular matching and may be of independent interest for designing dynamic algorithms for other problems.

We introduce the tokenized linear bandit (TLB) and multi-armed bandit (TMAB), variants of linear and stochastic multi-armed bandit problems inspired by LLM decoding and alignment. In these problems, at each round $t \in [T]$, a user submits a query (context), and the decision maker (DM) sequentially selects a token irrevocably from a token set. Once the sequence is complete, the DM observes a random utility from the user, whose expectation is presented by a sequence function mapping the chosen token sequence to a nonnegative real value that depends on the query. In both problems, we first show that learning is impossible without any structure on the sequence function. We introduce a natural assumption, diminishing distance with more commons (DDMC), and propose algorithms with regret $\tilde{O}(L\sqrt{T})$ and $\tilde{O}(L\sqrt{T^{2/3}})$ for TLB and TMAB, respectively. As a side product, we obtain an (almost) optimality of the greedy decoding for LLM decoding algorithm under DDMC, which justifies the unresaonable effectiveness of greedy decoding in several tasks. This also has an immediate application to decoding-time LLM alignment, when the misaligned utility can be represented as the frozen LLM's utility and a linearly realizable latent function. We finally validate our algorithm's performance empirically as well as verify our assumptions using synthetic and real-world datasets.

We explore the concept of replicability, which ensures algorithmic consistency despite input data variations, for online pricing problems, specifically prophet inequalities and delegation. Given the crucial role of replicability in enhancing transparency in economic decision-making, we present a replicable and nearly optimal pricing strategy for prophet inequalities, achieving a sample complexity of $\textnormal{poly}(\log^* |\mathcal{X}|)$, where $\mathcal{X}$ is the ground set of distributions. Furthermore, we extend these findings to the delegation problem and establish lower bound that proves the necessity of the $\log^*|\mathcal{X}|$ dependence. En route to obtaining these results, we develop a number of technical contributions which are of independent interest. Most notably, we propose a new algorithm for a variant of the heavy hitter problem, which has a nearly linear dependence on the inverse of the heavy hitter parameter, significantly improving upon existing results which have a cubic dependence.

In this paper, we study the fundamental problems of maintaining the diameter and a $k$-center clustering of a dynamic point set $P \subset \mathbb{R}^d$, where points may be inserted or deleted over time and the ambient dimension $d$ is not constant and may be high. Our focus is on designing algorithms that remain effective even in the presence of an \emph{adaptive adversary}—an adversary that, at any time $t$, knows the entire history of the algorithm’s outputs as well as all the random bits used by the algorithm up to that point. We present a fully dynamic algorithm that maintains a $2$-approximate diameter with a \emph{worst-case} update time of $poly(d, \log n)$, where $n$ is the length of the stream. Our result is achieved by identifying a robust representative of the dataset that requires infrequent updates, combined with a careful deamortization. To the best of our knowledge, this is the first efficient fully-dynamic algorithm for diameter in high dimensions that \emph{simultaneously} achieves a $2$-approximation guarantee and robustness against an adaptive adversary. We also give an improved dynamic $(4+\epsilon)$-approximation algorithm for the $k$-center problem, also resilient to an adaptive adversary. Our clustering algorithm achieves an amortized update time of $k^{2.5} d \cdot poly(\epsilon^{-1}, \log n)$, improving upon the amortized update time of $k^6 d \cdot poly( \epsilon^{-1}, \log n)$ by Biabani et al. [NeurIPS'24].

Submodular maximization subject to a $p$-matchoid constraint has various applications in machine learning, particularly in tasks such as feature selection, video and text summarization, movie recommendation, graph-based learning, and constraint-based optimization. We study this problem in the dynamic setting, where a sequence of insertions and deletions of elements to a $p$-matchoid $\mathcal{M}(\mathcal{V},\mathcal{I})$ occurs over time and the goal is to efficiently maintain an approximate solution. We propose a dynamic algorithm for non-monotone submodular maximization under a $p$-matchoid constraint. For a $p$-matchoid $\mathcal{M}(\mathcal{V},\mathcal{I})$ of rank $k$, defined by a collection of $m$ matroids, our algorithm guarantees a $(2p + 2\sqrt{p(p+1)} + 1 + \epsilon)$-approximate solution at any time $t$ in the update sequence, with an expected amortized query complexity of $O(\epsilon^{-3} pk^4 \log^2(k))$ per update.

We investigate the problem of sequentially selecting elements of an unknown matroid in an online manner to form an independent set, with the goal of maximizing the minimum probability of acceptance across all elements, a property we define as $f$-fairness. Under adversarial arrival orders, we design an $\alpha(\ln(k)+1)$-fair algorithm, where $\alpha$ is the arboricity of the matroid and $k$ is the rank, a result that is nearly optimal. For laminar matroids, we develop an $(2\alpha-1)$-fair algorithm, which is optimal up to constant factors, achieved through a novel online coloring scheme. In the random arrival order setting, we achieve a $(4+o(1))\alpha$-fair algorithm for graphic matroids, matching the optimal result up to constant factors, relying on a novel technique for learning a degeneracy ordering using a sampled subset of edges. We further generalize our result to $p$-matchoids, obtaining a $\beta(p\ln k+1)$-fair algorithm for the adversarial arrival model, where $\beta$ is the optimal offline fairness. Notably, all our results can be extended to a setting with no prior knowledge of the matroid with only a logarithmic increase in the fairness factor.

Understanding the formation of opinions on multiple interconnected topics within social networks is of significant importance. It offers insights into collective behavior and decision-making processes, with applications in Graph Neural Networks. Existing models propose that individuals form opinions based on a weighted average of their peers' opinions and potentially their own beliefs. This averaging process, when viewed as a best-response game, can be seen as an individual minimizing disagreements with peers, defined by a quadratic penalty, leading to an equilibrium. Bindel, Kleinberg, and Oren (FOCS 2011) provided tight bounds on the "price of anarchy," which is defined as the maximum level of overall disagreement at equilibrium relative to a social optimum. Bhawalkar, Gollapudi, and Munagala (STOC 2013) generalized the penalty function to consider non-quadratic penalties and provided tight bounds on the price of anarchy of these functions.

The delegated choice problem, introduced by Armstrong and Vickers (ECTA'10), involves a principal delegating a decision-making of selecting an element among n to an agent with potentially misaligned utility. To mitigate the agent's selfish behavior, the principal commits to acceptable sets and utilities in advance. Kleinberg and Kleinberg (EC'18) observed a novel connection to prophet inequality, a central problem in optimal stopping theory, stating that the delegated choice problem is equivalent to a version of prophet inequality with oblivious stopping rules in the single choice setting. This amplifies the significance of prophet inequality, originally cemented by its fruitful connection to numerous problems including posted pricing in the online auction for digital goods/multi-dimensional mechanisms, stochastic optimization, secretary problem, and Pandora's box. A fundamental question in this context is, whether the connection between prophet inequality and delegated choice follows the same path even under arbitrary combinatorial constraints.

We study the problem of delegated choice with inspection cost (DCIC), which is a variant of the delegated choice problem by Kleinberg and Kleinberg (EC'18) as well as an extension of the Pandora's box problem with nonobligatory inspection (PNOI) by Doval (JET'18). In our model, an agent may strategically misreport the proposed element's utility, unlike the standard delegated choice problem which assumes that the agent truthfully reports the utility for the proposed alternative. Thus, the principal needs to inspect the proposed element possibly along with other alternatives to maximize its own utility, given an exogenous cost of inspecting each element. Further, the delegation itself incurs a fixed cost, thus the principal can decide whether to delegate or not and inspect by herself.

We study bilateral trade with a broker, where a buyer and seller interact exclusively through the broker. The broker strategically maximizes her payoff through arbitrage by trading with the buyer and seller at different prices. We study whether the presence of the broker interferes with the mechanism’s gains-from-trade (GFT) achieving a constant-factor approximation to the first-best gains-from-trade (FB), in a similar vein to the constant-factor approximability without a broker by Deng, Mao, Sivan and Wang (STOC’21).

Approximation algorithms for the prize-collecting Steiner forest problem (PCSF) have been a subject of research for over three decades, starting with the seminal works of Agrawal, Klein, and Ravi [1, 2] and Goemans and Williamson [15, 16] on Steiner forest and prize-collecting problems. In this paper, we propose and analyze a natural deterministic algorithm for PCSF that achieves a 2-approximate solution in polynomial time. This represents a significant improvement compared to the previously best known algorithm with a 2.54-approximation factor developed by Hajiaghayi and Jain [20] in 2006. Furthermore, Könemann, Olver, Pashkovich, Ravi, Swamy, and Vygen [25] have established an integrality gap of at least 9/4 for the natural LP relaxation for PCSF. However, we surpass this gap through the utilization of an iterative algorithm and a novel analysis technique. Since 2 is the best known approximation guarantee for Steiner forest problem [2] (see also [16]), which is a special case of PCSF, our result matches this factor and closes the gap between the Steiner forest problem and its generalized version, PCSF.

We present a study on a repeated delegated choice problem, which is the first to consider an online learning variant of Kleinberg and Kleinberg, EC'18. In this model, a principal interacts repeatedly with an agent who possesses an exogenous set of solutions to search for efficient ones. Each solution can yield varying utility for both the principal and the agent, and the agent may propose a solution to maximize its own utility in a selfish manner. To mitigate this behavior, the principal announces an eligible set which screens out a certain set of solutions. The principal, however, does not have any information on the distribution of solutions nor the number of solutions in advance. Therefore, the principal dynamically announces various eligible sets to efficiently learn the distribution. The principal's objective is to minimize cumulative regret compared to the optimal eligible set in hindsight. We explore two dimensions of the problem setup, whether the agent behaves myopically or strategizes across the rounds, and whether the solutions yield deterministic or stochastic utility. We obtain sublinear regret upper bounds in various regimes, and derive corresponding lower bounds which implies the tightness of the results. Overall, we bridge a well-known problem in economics to the evolving area of online learning, and present a comprehensive study in this problem.

We here address the problem of fairly allocating indivisible goods or chores to n agents with weights that define their entitlement to the set of indivisible resources. Stemming from well-studied fairness concepts such as envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) for agents with equal entitlements, we present, in this study, the first set of impossibility results alongside algorithmic guarantees for fairness among agents with unequal entitlements. Within this paper, we expand the concept of envy-freeness up to any good or chore to the weighted context (WEFX and XWEF respectively), demonstrating that these allocations are not guaranteed to exist for two or three agents. Despite these negative results, we develop a WEFX procedure for two agents with integer weights, and furthermore, we devise an approximate WEFX procedure for two agents with normalized weights. We further present a polynomial-time algorithm that guarantees a weighted envy-free allocation up to one chore (1WEF) for any number of agents with additive cost functions. Our work underscores the heightened complexity of the weighted fair division problem when compared to its unweighted counterpart.

Fault-tolerant Consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or (PODC'98) were the first who proved an absolute lower bound Ω(√{n/log n}) on expected time complexity of Consensus in any classical (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes. Seminal work of Ben-Or and Hassidim (STOC'05) broke the Ω(√{n/log n}) barrier for consensus in the classical (deterministic and randomized) networks by enhancing the model with quantum channels. In such networks, quantum communication between every pair of processes participating in the protocol is also allowed. They showed an (expected) constant-time quantum algorithm for a linear number of crashes t < n/3. In this paper, we improve upon that seminal work by reducing the number of quantum and communication bits to an arbitrarily small polynomial, and even more, to a polylogarithmic number - though, the latter in the cost of a slightly larger polylogarithmic time (still exponentially smaller than the time lower bound Ω(√{n/log n}) for the classical computation models).

We initiate the study of the submodular cover problem in a dynamic setting where the elements of the ground set are inserted and deleted. In the classical submodular cover problem, we are given a monotone submodular function $f : 2^{V} \to \mathbb{R}^{\ge 0}$ and the goal is to obtain a set $S \subseteq V$ that minimizes the cost subject to the constraint $f(S) = f(V)$. This is a classical problem in computer science and generalizes the Set Cover problem, 2-Set Cover, and dominating set problem among others. We consider this problem in a dynamic setting where there are updates to our set $V$, in the form of insertions and deletions of elements from a ground set $\mathcal{V}$, and the goal is to maintain an approximately optimal solution with low query complexity per update. For this problem, we propose a randomized algorithm that, in expectation, obtains a $(1-O(\epsilon), O(\epsilon^{-1}))$-bicriteria approximation using polylogarithmic query complexity per update.

We give the first non-trivial decremental dynamic embedding of a weighted, undirected graph $G$ into $\ell_p$ space. Given a weighted graph $G$ undergoing a sequence of edge weight increases, the goal of this problem is to maintain a (randomized) mapping $\phi: (G,d) \to (X,\ell_p)$ from the set of vertices of the graph to the $\ell_p$ space such that for every pair of vertices $u$ and $v$, the expected distance between $\phi(u)$ and $\phi(v)$ in the $\ell_p$ metric is within a small multiplicative factor, referred to as the distortion, of their distance in $G$. Our main result is a dynamic algorithm with expected distortion $O(\log^2 n)$ and total update time $O\left((m^{1+o(1)} \log^2 W + Q)\log(nW) \right)$, where $W$ is the maximum weight of the edges, $Q$ is the total number of updates and $n, m$ denote the number of vertices and edges in $G$ respectively. This is the first result of its kind, extending the seminal result of Bourgain ’85 to the expanding field of dynamic algorithms. Moreover, we demonstrate that in the fully dynamic regime, where we tolerate edge insertions as well as deletions, no algorithm can explicitly maintain an embedding into $\ell_p$ space that has a low distortion with high probability.

We consider the setting of repeated fair division between two players, denoted Alice and Bob, with private valuations over a cake. In each round, a new cake arrives, which is identical to the ones in previous rounds. Alice cuts the cake at a point of her choice, while Bob chooses the left piece or the right piece, leaving the remainder for Alice. We consider two versions: sequential, where Bob observes Alice's cut point before choosing left/right, and simultaneous, where he only observes her cut point after making his choice. The simultaneous version was first considered by Aumann and Maschler. We observe that if Bob is almost myopic and chooses his favorite piece too often, then he can be systematically exploited by Alice through a strategy akin to a binary search. This strategy allows Alice to approximate Bob's preferences with increasing precision, thereby securing a disproportionate share of the resource over time. We analyze the limits of how much a player can exploit the other one and show that fair utility profiles are in fact achievable. Specifically, the players can enforce the equitable utility profile of $(1/2, 1/2)$ in the limit on every trajectory of play, by keeping the other player's utility to approximately $1/2$ on average while guaranteeing they themselves get at least approximately $1/2$ on average. We show this theorem using a connection with Blackwell approachability. Finally, we analyze a natural dynamic known as fictitious play, where players best respond to the empirical distribution of the other player. We show that fictitious play converges to the equitable utility profile of $(1/2, 1/2)$ at a rate of $O(1/\sqrt{T})$.

The online bipartite matching problem, extensively studied in the literature, deals with the allocation of online arriving vertices (items) to a predetermined set of offline vertices (agents). However, little attention has been given to the concept of class fairness, where agents are categorized into different classes, and the matching algorithm must ensure equitable distribution across these classes. We here focus on randomized algorithms for the fair matching of indivisible items, subject to various definitions of fairness. Our main contribution is the first (randomized) non-wasteful algorithm that simultaneously achieves a $1/2$ approximation to class envy-freeness (CEF) while simultaneously ensuring an equivalent approximation to the class proportionality (CPROP) and utilitarian social welfare (USW) objectives. We supplement this result by demonstrating that no non-wasteful algorithm can achieve an $\alpha$-CEF guarantee for $\alpha > 0.761$. In a similar vein, we provide a novel input instance for deterministic divisible matching that demonstrates a nearly tight CEF approximation. Lastly, we define the ``price of fairness," which represents the trade-off between optimal and fair matching. We demonstrate that increasing the level of fairness in the approximation of the solution leads to a decrease in the objective of maximizing USW, following an inverse proportionality relationship.

In the field of computational advertising, the integration of ads into the outputs of large language models (LLMs) presents an opportunity to support these services without compromising content integrity. This paper introduces novel auction mechanisms for ad allocation and pricing within the textual outputs of LLMs, leveraging retrieval-augmented generation (RAG). We propose a \emph{segment auction} where an ad is probabilistically retrieved for each discourse segment (paragraph, section, or entire output) according to its bid and relevance, following the RAG framework, and priced according to competing bids. We show that our auction maximizes logarithmic social welfare, a new notion of welfare that balances allocation efficiency and fairness, and we characterize the associated incentive-compatible pricing rule. These results are extended to multi-ad allocation per segment. An empirical evaluation validates the feasibility and effectiveness of our approach over several ad auction scenarios, and exhibits inherent tradeoffs in metrics as we allow the LLM more flexibility to allocate ads.

We study the complexity of the problem of reaching agreement in a synchronous distributed system, also called consensus, by n autonomous parties, when the communication links from/to faulty parties can omit messages. The faulty parties are selected and controlled by an adaptive, full-information, computationally unbounded adversary. We design a randomized algorithm that works in [EQUATION] rounds and sends O(n2 log3 n) total number of communication bits, where the number of faulty parties can be Θ(n). When the number of faulty parties is linear in n, our result is simultaneously tight for both these measures within polylogarithmic factors: due to the Ω(n2) lower bound on the number of messages send by any Monte Carlo solution, by Abraham et al. (PODC'19), and due to the [EQUATION] lower bound on the number of rounds of any Las Vegas solution, by Bar-Joseph and Ben-Or (PODC'98). Thereby, this work settles the landscape of the consensus problem in the omission failures model, which stood as an open question since the work of Dolev and Strong (SICOMP'83).

Approximation algorithms for the prize-collecting Steiner forest problem (PCSF) have been a subject of research for over three decades, starting with the seminal works of Agrawal, Klein, and Ravi [1, 2] and Goemans and Williamson [14, 15] on Steiner forest and prize-collecting problems. In this paper, we propose and analyze a natural deterministic algorithm for PCSF that achieves a 2-approximate solution in polynomial time. This represents a significant improvement compared to the previously best known algorithm with a 2.54-approximation factor developed by Hajiaghayi and Jain [19] in 2006. Furthermore, Könemann, Olver, Pashkovich, Ravi, Swamy, and Vygen [24] have established an integrality gap of at least 9/4 for the natural LP relaxation for PCSF. However, we surpass this gap through the utilization of a combinatorial algorithm and a novel analysis technique. Since 2 is the best known approximation guarantee for Steiner forest problem [2] (see also [15]), which is a special case of PCSF, our result matches this factor and closes the gap between the Steiner forest problem and its generalized version, PCSF.

Submodular maximization under matroid and cardinality constraints are classical problems with a wide range of applications in machine learning, auction theory, and combinatorial optimization. In this paper, we consider these problems in the dynamic setting where (1) we have oracle access to a monotone submodular function f : 2V → ℝ+ and (2) we are given a sequence S of insertions and deletions of elements of an underlying ground set V.

We study the power of posted pricing mechanisms for Bayesian online optimization problems subject to combinatorial feasibility constraints. When the objective is to maximize social welfare, the problem is widely studied in the literature on prophet inequalities. While most (though not all) existing algorithms for prophet inequalities are implemented using a pricing mechanism, whether or not this can be done in general is unknown, and was formally left as an open question by Dutting, Feldman, Kesselheim, and Lucier (FOCS 2017, SICOMP 2020). Understanding the power and limitations of posted prices is important from a mechanism design perspective because any posted price mechanism is truthful, and is also interesting in its own right as it can guide future research on prophet inequalities.

In the Massively Parallel Computation (MPC) model, data is distributed across multiple processors, and we call an algorithm space-efficient if each machine has n^1-ε + o(1) memory with a machine count of Ømega(n^ε).

Prize-Collecting Steiner Tree (PCST) is a generalization of the Steiner Tree problem, a fundamental problem in computer science. In the classic Steiner Tree problem, we aim to connect a set of vertices known as terminals using the minimum-weight tree in a given weighted graph. In this generalized version, each vertex has a penalty, and there is flexibility to decide whether to connect each vertex or pay its associated penalty, making the problem more realistic and practical.

Abstract. The secretary and the prophet inequality problems are central to the field of stopping theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions. Kleinberg and Weinberg and Feldman, Gravin, and Lucier show that for adversarial arrival order of random variables the optimal prophet inequalities give a [Formula: see text]-approximation. For many settings, however, it is conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the [Formula: see text]-approximation and obtain [Formula: see text]-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan and of Esfandiari and colleagues who worked in the special cases where either we can fully control the arrival order or there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

Decision trees are widely used for their low computational cost, good predictive performance, and ability to assess the importance of features. Though often used in practice for feature selection, the theoretical guarantees of these methods are not well understood. We here obtain a tight finite sample bound for the feature selection problem in linear regression using single-depth decision trees. We examine the statistical properties of these "decision stumps" for the recovery of the s active features from p total features, where s

Maximizing a monotone submodular function under cardinality constraint $k$ is a core problem in machine learning and database with many basic applications, including video and data summarization, recommendation systems, feature extraction, exemplar clustering, and coverage problems. We study this classic problem in the fully dynamic model where a stream of insertions and deletions of elements of an underlying ground set is given and the goal is to maintain an approximate solution using a fast update time. A recent paper at NeurIPS’20 by Lattanzi, Mitrovic, Norouzi-Fard, Tarnawski, Zadimoghaddam claims to obtain a dynamic algorithm for this problem with a $(\frac{1}{2} -\epsilon)$ approximation ratio and a query complexity bounded by $\mathrm{poly}(\log(n),\log(k),\epsilon^{-1})$. However, as we explain in this paper, the analysis has some important gaps. Having a dynamic algorithm for the problem with polylogarithmic update time is even more important in light of a recent result by Chen and Peng at STOC’22 who show a matching lower bound for the problem – any randomized algorithm with a $\frac{1}{2}+\epsilon$ approximation ratio must have an amortized query complexity that is polynomial in $n$. In this paper, we develop a simpler algorithm for the problem that maintains a $(\frac{1}{2}-\epsilon)$-approximate solution for submodular maximization under cardinality constraint $k$ using a polylogarithmic amortized update time.

Clustering is a fundamental building block of modern statistical analysis pipelines. Fair clustering has seen much attention from the machine learning community in recent years. We are some of the first to study fairness in the context of hierarchical clustering, after the results of Ahmadian et al. from NeurIPS in 2020. We evaluate our results using Dasgupta's cost function, perhaps one of the most prevalent theoretical metrics for hierarchical clustering evaluation. Our work vastly improves the previous $O(n^{5/6}poly\log(n))$ fair approximation for cost to a near polylogarithmic $O(n^\delta poly\log(n))$ fair approximation for any constant $\delta\in(0,1)$. This result establishes a cost fairness tradeoff and extends to broader fairness constraints than the previous work. We also show how to alter existing hierarchical clusterings to guarantee fairness and cluster balance across any level in the hierarchy.

Maximizing submodular functions has been increasingly used in many applications of machine learning, such as data summarization, recommendation systems, and feature selection. Moreover, there has been a growing interest in both submodular maximization and dynamic algorithms. In 2020, Monemizadeh and Lattanzi, Mitrovic, Norouzi-Fard, Tarnawski, and Zadimoghaddam initiated developing dynamic algorithms for the monotone submodular maximization problem under the cardinality constraint $k$. In 2022, Chen and Peng studied the complexity of this problem and raised an important open question: "\emph{Can we extend [fully dynamic] results (algorithm or hardness) to non-monotone submodular maximization?}". We affirmatively answer their question by demonstrating a reduction from maximizing a non-monotone submodular function under the cardinality constraint $k$ to maximizing a monotone submodular function under the same constraint. Through this reduction, we obtain the first dynamic algorithms to solve the non-monotone submodular maximization problem under the cardinality constraint $k$. Our algorithms maintain an $(8+\epsilon)$-approximate of the solution and use expected amortized $O(\epsilon^{-3}k^3\log^3(n)\log(k))$ or $O(\epsilon^{-1}k^2\log^3(k))$ oracle queries per update, respectively. Furthermore, we showcase the benefits of our dynamic algorithm for video summarization and max-cut problems on several real-world data sets.

We study social learning dynamics motivated by reviews on online platforms. The agents collectively follow a simple multi-armed bandit protocol, but each agent acts myopically, without regards to exploration. We allow a wide range of myopic behaviors that are consistent with (parameterized) confidence intervals for the arms’ expected rewards. We derive stark exploration failures for any such behavior, and provide matching positive results. As a special case, we obtain the first general results on failure of the greedy algorithm in bandits, thus providing a theoretical foundation for why bandit algorithms should explore.

We present an oracle-efficient relaxation for the adversarial contextual bandits problem, where the contexts are sequentially drawn i.i.d from a known distribution and the cost sequence is chosen by an online adversary. Our algorithm has a regret bound of $O(T^{\frac{2}{3}}(K\log(|\Pi|))^{\frac{1}{3}})$ and makes at most $O(K)$ calls per round to an offline optimization oracle, where $K$ denotes the number of actions, $T$ denotes the number of rounds and $\Pi$ denotes the set of policies. This is the first result to improve the prior best bound of $O((TK)^{\frac{2}{3}}(\log(|\Pi|))^{\frac{1}{3}})$ as obtained by Syrgkanis et al. at NeurIPS 2016, and the first to match the original bound of Langford and Zhang at NeurIPS 2007 which was obtained for the stochastic case.

Research in fair machine learning, and particularly clustering, has been crucial in recent years given the many ethical controversies that modern intelligent systems have posed. Ahmadian et al. [2020] established the study of fairness in hierarchical clustering, a stronger, more structured variant of its well-known flat counterpart, though their proposed algorithm that optimizes for Dasgupta's [2016] famous cost function was highly theoretical. Knittel et al. [2023] then proposed the first practical fair approximation for cost, however they were unable to break the polynomial-approximate barrier they posed as a hurdle of interest. We break this barrier, proposing the first truly polylogarithmic-approximate low-cost fair hierarchical clustering, thus greatly bridging the gap between the best fair and vanilla hierarchical clustering approximations.

Fault-tolerant consensus is about reaching agreement on some of the input values in a limited time by non-faulty autonomous processes, despite of failures of processes or communication medium. This problem is particularly challenging and costly against an adaptive adversary with full information. Bar-Joseph and Ben-Or [7] (PODC'98) were the first who proved an absolute lower bound [EQUATION] on expected time complexity of consensus in any classic (i.e., randomized or deterministic) message-passing network with n processes succeeding with probability 1 against such a strong adaptive adversary crashing processes.

In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm observes a sequence of prices one after the other. At each time step, the online algorithm can decide to buy and pay the current price if it does not hold the item already; or it can decide to sell and collect the current price as a reward if it holds the item.

We consider a multi-agent delegation mechanism without money. In our model, given a set of agents, each agent has a fixed number of solutions which is exogenous to the mechanism, and privately sends a signal, e.g., a subset of solutions, to the principal. Then, the principal selects a final solution based on the agents' signals. In stark contrast to single-agent setting by Kleinberg and Kleinberg [2018] with an approximate Bayesian mechanism, we show that there exists efficient approximate prior-independent mechanisms with both information and performance gain, thanks to the competitive tension between the agents. Interestingly however, the amount of such a compelling power significantly varies with respect to the information available to the agents, and the degree of correlation between the principal's and the agent's utility. Technically, we conduct a comprehensive study on the multi-agent delegation problem and derive several results on the approximation factors of Bayesian/prior-independent mechanisms in complete/incomplete information settings. As a special case of independent interest, we obtain comparative statics regarding the number of agents which implies the dominance of the multi-agent setting (n ≥ 2) over the single-agent setting (n = 1) in terms of the principal's utility. We further extend our problem by considering an examination cost of the mechanism and derive some analogous results in the complete information setting.

Efficient computation on massive high-dimensional data greatly benefits from efficient embedding techniques into simpler metrics. Perhaps the most celebrated technique is the dimension reduction a-la Johnson and Lindenstrauss [46]. Another important method embeds the data into a tree metric space, first efficiently achieved by Bartal [15]. Both of these algorithmic tools are among the most general theorems with numerous applications.

Regular languages are some of the most widely studied languages in computer science history. Given a regular language L ⊆ {0, 1} ⋆ and string ω ∈ {0, 1} ⋆, two of the most fundamental regular language problems are recognition, the problem of determining if w is in L, and testing, the problem of determining if w is at most ε-far from L. In this paper we modernize regular language recognition and testing algorithms for the Massively Parallel Computations (MPC) model used everyday in big data engineering. First we give a regular language testing algorithm, which succeeds with high probability using Õ(1 over ε) queries to the input string. Following the testing algorithm, we give a simple dynamic programming solution for regular language recognition. Both algorithms run in constant communication rounds and O(n) total memory in MPC where n is the size of the input.

A suffix tree is a trie-like data structure that stores every suffix of an input string of length n. Finding the Suffix Tree of a given string is a well-studied and classic problem. A compressed suffix tree is constructible in O(n) time using the well-known algorithm of McCreight (JACM, 1976). Suffix trees alongside with hashing are two powerful tools in solving location-sensitive string problems. Many well-studied fundamental string problems such as String Matching, Longest Palindrome Substring (LPS), Longest Common Substring (LCS), and Longest Common Prefix (LCP) queries are location-sensitive and have linear time solutions via reductions to suffix tree.

Given two strings of length n over alphabet Σ, and an upper bound k on their edit distance, the algorithm of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88) from almost forty years back computes the unweighted string edit distance in O(n+k2) time. To date, it remains the fastest algorithm for exact edit distance computation, and it is optimal under the Strong Exponential Hypothesis (Backurs and Indyk; STOC’15). Over the years, this result has inspired many developments, including fast approximation algorithms for string edit distance as well as similar Õ(n+poly(k))-time algorithms for generalizations to tree and Dyck edit distances. Surprisingly, all these results hold only for unweighted instances.

The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximal matching either take polylogarithmic time which is considered inefficient, or require a strictly super-linear space of n 1+Ω (1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [ 15 ]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition. We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an O (log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved O (log log Δ) round algorithm for 1 + ε approximate matching. All these results can also be implemented in the congested clique model in the same number of rounds.

In this paper, we generalize the recently studied stochastic matching problem to more accurately model a significant medical process, kidney exchange, and several other applications. Up until now the stochastic matching problem that has been studied was as follows: given a graph G= (V,E), each edge is included in the realized sub-graph of G independently with probability pe, and the goal is to find a degree-bounded sub-graph Q of G that has an expected maximum matching that approximates the expected maximum matching of G. This model does not account for possibilities of vertex dropouts, which can be found in several applications, e.g. in kidney exchange when donors or patients opt out of the exchange process as well as in online freelancing and online dating when online profiles are found to be faked. Thus, we will study a more generalized model of stochastic matching in which vertices and edges are both realized independently with some probabilities pv, pe, respectively, which more accurately fits important applications than the previously studied model. We will discuss the first algorithms and analysis for this generalization of the stochastic matching model and prove that they achieve good approximation ratios. In particular, we show that the approximation factor of a natural algorithm for this problem is at least 0.6568 in unweighted graphs, and 1/2+ε in weighted graphs for some constant ε >0. We further improve our result for unweighted graphs to 2/3 using edge degree constrained sub-graphs (EDCS).

Given a graph, the densest subgraph problem asks for a set of vertices such that the average degree among these vertices is maximized. Densest subgraph has numerous applications in learning, e.g., community detection in social networks, link spam detection, correlation mining, bioinformatics, and so on. Although there are efficient algorithms that output either exact or approximate solutions to the densest subgraph problem, existing algorithms may violate the privacy of the individuals in the network, e.g., leaking the existence/non-existence of edges. In this paper, we study the densest subgraph problem in the framework of the differential privacy, and we derive the upper and lower bounds for this problem. We show that there exists a linear-time $\epsilon$-differentially private algorithm that finds a 2-approximation of the densest subgraph with an extra poly-logarithmic additive error. Our algorithm not only reports the approximate density of the densest subgraph, but also reports the vertices that form the dense subgraph. Our upper bound almost matches the famous 2-approximation by Charikar both in performance and in approximation ratio, but we additionally achieve differential privacy. In comparison with Charikar’s algorithm, our algorithm has an extra poly logarithmic additive error. We partly justify the additive error with a new lower bound, showing that for any differentially private algorithm that provides a constant-factor approximation, a sub-logarithmic additive error is inherent. We also practically study our differentially private algorithm on real-world graphs, and we show that in practice the algorithm finds a solution which is very close to the optimal.

Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of edit distance in which the task is to compute a measure of dissimilarity between two (unweighted) rooted trees with node labels. Perhaps the most notable recent application of tree edit distance is in NoSQL big databases, such as MongoDB, where each row of the database is a JSON document represented as a labeled rooted tree and finding dissimilarity between two rows is a basic operation. Until recently, the fastest algorithm for tree edit distance ran in cubic time (Demaine, Mozes, Rossman, Weimann; TALG’10); however, Mao (FOCS’21) broke the cubic barrier for the tree edit distance problem using fast matrix multiplication.Given a parameter k as an upper bound on the distance, an $\mathcal{O}(n+k^{2})$-time algorithm for edit distance has been known since the 1980s due to works of Myers (Algorithmica’86) and Landau and Vishkin (JCSS’88). The existence of an $\tilde{\mathcal{O}}(n+poly(k))$-time algorithm for tree edit distance has been posed as open question, e.g., by Akmal and Jin (ICALP’21), who give a stateof-the-art $O(nk^{2})$-time algorithm. In this paper, we answer this question positively.

Miller and Reif’s FOCS'85 [Gary L. Miller and John H. Reif, 1989] classic and fundamental tree contraction algorithm is a broadly applicable technique for the parallel solution of a large number of tree problems. Additionally it is also used as an algorithmic design technique for a large number of parallel graph algorithms. In all previously explored models of computation, however, tree contractions have only been achieved in Ω(log n) rounds of parallel run time. In this work, we not only introduce a generalized tree contraction method but also show it can be computed highly efficiently in O(1/ε³) rounds in the Adaptive Massively Parallel Computing (AMPC) setting, where each machine has O(n^ε) local memory for some 0 < ε < 1. AMPC is a practical extension of Massively Parallel Computing (MPC) which utilizes distributed hash tables [MohammadHossein Bateni et al., 2017; Behnezhad et al., 2019; Raimondas Kiveris et al., 2014]. In general, MPC is an abstract model for MapReduce, Hadoop, Spark, and Flume which are currently widely used across industry and has been studied extensively in the theory community in recent years. Last but not least, we show that our results extend to multiple problems on trees, including but not limited to maximum and maximal matching, maximum and maximal independent set, tree isomorphism testing, and more.

The Santa Claus problem is a fundamental problem in {\em fair division}: the goal is to partition a set of {\em heterogeneous} items among {\em heterogeneous} agents so as to maximize the minimum value of items received by any agent. In this paper, we study the online version of this problem where the items are not known in advance and have to be assigned to agents as they arrive over time. If the arrival order of items is arbitrary, then no good assignment rule exists in the worst case. However, we show that, if the arrival order is random, then for $n$ agents and any $\varepsilon > 0$, we can obtain a competitive ratio of $1-\varepsilon$ when the optimal assignment gives value at least $\Omega(\log n / \varepsilon^2)$ to every agent (assuming each item has at most unit value). We also show that this result is almost tight: namely, if the optimal solution has value at most $C \ln n / \varepsilon$ for some constant $C$, then there is no $(1-\varepsilon)$-competitive algorithm even for random arrival order.

We study the Weighted Min Cut problem in the Adaptive Massively Parallel Computation (AMPC) model. In 2019, Behnezhad et al. [3] introduced the AMPC model as an extension of the Massively Parallel Computation (MPC) model. In the past decade, research on highly scalable algorithms has had significant impact on many massive systems. The MPC model, introduced in 2010 by Karloff et al. [16], which is an abstraction of famous practical frameworks such as MapReduce, Hadoop, Flume, and Spark, has been at the forefront of this research. While great strides have been taken to create highly efficient MPC algorithms for a range of problems, recent progress has been limited by the 1-vs-2 Cycle Conjecture [20], which postulates that the simple problem of distinguishing between one and two cycles requires Ω(log n) MPC rounds. In the AMPC model, each machine has adaptive read access to a distributed hash table even when communication is restricted (i.e., in the middle of a round). While remaining practical [4], this gives algorithms the power to bypass limitations like the 1-vs-2 Cycle Conjecture.

Consensus is one of the most thoroughly studied problems in distributed computing, yet there are still complexity gaps that have not been bridged for decades. In particular, in the classical message-passing setting with processes’ crashes, since the seminal works of Bar-Joseph and Ben-Or [PODC 1998] and Aspnes and Waarts [SICOMP 1996, JACM 1998] in the previous century, there is still a fundamental unresolved question about communication complexity of fast randomized Consensus against a (strong) adaptive adversary crashing processes arbitrarily online. The best known upper bound on the number of communication bits is Θ(n3/2/√logn) per process, while the best lower bound is Ω(1). This is in contrast to randomized Consensus against a (weak) oblivious adversary, for which time-almost-optimal algorithms guarantee amortized O(1) communication bits per process. We design an algorithm against adaptive adversary that reduces the communication gap by nearly linear factor to O(√n· n) bits per process, while keeping almost-optimal (up to factor O(log3 n)) time complexity O(√n·log5/2 n).

Envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX) are two well-known extensions of envy-freeness for the case of indivisible items. It is shown that EF1 can always be guaranteed for agents with subadditive valuations. In sharp contrast, it is unknown whether or not an EFX allocation always exists, even for four agents and additive valuations. In addition, the best approximation guarantee for EFX is (φ − 1) ≃ 0.61 by Amanitidis et al.. In order to find a middle ground to bridge this gap, in this paper we suggest another fairness criterion, namely envy-freeness up to a random good or EFR, which is weaker than EFX, yet stronger than EF1. For this notion, we provide a polynomial-time 0.73-approximation allocation algorithm. For our algorithm we introduce Nash Social Welfare Matching which makes a connection between Nash Social Welfare and envy freeness.

We provide a polynomial-time, scalable algorithm for equilibrium computation in multi-agent influence games on networks, extending work of Bindel, Kleinberg, and Oren (2015) from the single-agent to the multi-agent setting. In games of influence, agents have limited advertising budget to influence the initial predisposition of nodes in some network towards their products, but the eventual decisions of the nodes are determined by the stationary state of DeGroot opinion dynamics on the network, which takes over after the seeding (Ahmadinejad et al. 2014, 2015). In multi-agent systems, how should agents spend their budgets to seed the network to maximize their utility in anticipation of other advertising agents and the network dynamics? We show that Nash equilibria of this game are pure and (under weak assumptions) unique, and can be computed in polynomial time; we test our model by computing equilibria using mirror descent for the two-agent case on random graphs.

The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we first consider these problems in the asymmetric streaming model introduced by Andoni, Krauthgamer and Onak [Andoni et al., 2010] (FOCS'10) and Saks and Seshadhri [Saks and Seshadhri, 2013] (SODA'13). In this model we have random access to one string and streaming access the other one. Our main contribution is a constant factor approximation algorithm for ED with memory Õ(n^δ) for any constant δ > 0. In addition to this, we present an upper bound of Õ _ε(√n) on the memory needed to approximate ED or LCS within a factor 1±ε. All our algorithms are deterministic and run in polynomial time in a single pass. We further study small-space approximation algorithms for ED, LCS, and longest increasing sequence (LIS) in the non-streaming setting. Here, we design algorithms that achieve 1 ± ε approximation for all three problems, where ε > 0 can be any constant and even slightly sub-constant. Our algorithms only use poly-logarithmic space while maintaining a polynomial running time. This significantly improves previous results in terms of space complexity, where all known results need to use space at least Ω(√n). Our algorithms make novel use of triangle inequality and carefully designed recursions to save space, which can be of independent interest.

We study distributed algorithms for string matching problem in presence of wildcard characters. Given a string T (a text), we look for all occurrences of another string P (a pattern) as a substring of string T. Each wildcard character in the pattern matches a specific class of strings based on its type. String matching is one of the most fundamental problems in computer science, especially in the fields of bioinformatics and machine learning. Persistent effort has led to a variety of algorithms for the problem since 1960s.

Suppose a customer is faced with a sequence of fluctuating prices, such as for airfare or a product sold by a large online retailer. Given distributional information about what price they might face each day, how should they choose when to purchase in order to maximize the likelihood of getting the best price in retrospect? This is related to the classical secretary problem, but with values drawn from known distributions. In their pioneering work, Gilbert and Mosteller [\textit{J. Amer. Statist. Assoc. 1966}] showed that when the values are drawn i.i.d., there is a thresholding algorithm that selects the best value with probability approximately 0.58010.5801. However, the more general problem with non-identical distributions has remained unsolved.In this paper, we provide an algorithm for the case of non-identical distributions that selects the maximum element with probability 1/e1/e, and we show that this is tight. We further show that if the observations arrive in a random order, this barrier of 1/e1/e can be broken using a static threshold algorithm, and we show that our success probability is the best possible for any single-threshold algorithm under random observation order. Moreover, we prove that one can achieve a strictly better success probability using more general multi-threshold algorithms, unlike the non-random-order case. Along the way, we show that the best achievable success probability for the random-order case matches that of the i.i.d. case, which is approximately 0.58010.5801, under a “no-superstars” condition that no single distribution is very likely ex ante to generate the maximum value. We also extend our results to the problem of selecting one of the kk best values.One of the main tools in our analysis is a suitable “Poissonization” of random order distributions, which uses Le Cam’s theorem to connect the Poisson binomial distribution with the discrete Poisson distribution. This approach may be of independent interest.

In this paper, we study the problem of finding a maximum matching in the semi-streaming model when edges arrive in a random order. In the semi-streaming model, an algorithm receives a stream of edges and it is allowed to have a memory of Õ(n)1 where n is the number of vertices in the graph. A recent inspiring work by Assadi et al. [1] shows that there exists a streaming algorithm with the approximation ratio of ⅔ that uses Õ(n1.5) memory. However, the memory of their algorithm is much larger than the memory constraint of the semi-streaming algorithms. In this work, we further investigate this problem in the semi-streaming model, and we present simple and clean algorithms for approximating maximum matching in the semi-streaming model. Our main results are as follows. We show that there exists a single-pass deterministic semi-streaming algorithm that finds a approximation of the maximum matching in bipartite graphs using Õ(n) memory. This result significantly outperforms the state-of-the-art result of Konrad [12] that finds a 0.539 approximation of the maximum matching using Õ(n) memory. By giving a black-box reduction from finding a matching in general graphs to finding a matching in bipartite graphs, we show there exists a single-pass deterministic semi-streaming algorithm that finds a (≈ 0.545) approximation of the maximum matching in general graphs, improving upon the state-of-art result 0.506 approximation by Gamlath et al. [8].

Suppose that we are given an arbitrary graph G=(V, E) and know that each edge in E is going to be realized independently with some probability p. The goal in the stochastic matching problem is to pick a sparse subgraph Q of G such that the realized edges in Q, in expectation, include a matching that is approximately as large as the maximum matching among the realized edges of G. The maximum degree of Q can depend on p, but not on the size of G. This problem has been subject to extensive studies over the years and the approximation factor has been improved gradually from 0.5 to eventually 2/3 which is a known barrier. In this work, we analyze a natural sampling-based algorithm and show that it can obtain a (1−є) approximation, for any constant є > 0. A key and of possible independent interest component of our analysis is an algorithm that constructs a matching on a stochastic graph, which among some other important properties, guarantees that each vertex is matched independently from the vertices that are sufficiently far. This allows us to bypass a previously known barrier towards achieving (1−є) approximation based on existence of dense Ruzsa-Szemerédi graphs.

Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=\{t_1, t_2, \ldots, t_k\}$ of $k$ terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set $H\subseteq V$ of minimum weight such that $G[H]$ contains a $t_{i}\rightarrow t_j$ path for each $i\neq j$. The problem is NP-hard, but Feldman and Ruhl [ SIAM J. Comput., 36 (2006), pp. 543--561] gave a novel $n^{O(k)}$ algorithm for the SCSS problem, where $n$ is the number of vertices in the graph and $k$ is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithm for planar SCSS, which is an improvement of a factor of $O(\sqrt{k})$ in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an $f(k)\cdot n^{o(\sqrt{k})}$ algorithm for any computable function $f$, unless the exponential time hypothesis (ETH) fails. To obtain our algorithm, we first show combinatorially that there is a minimal solution whose treewidth is $O(\sqrt{k})$, and then use the dynamic-programming based algorithm for finding bounded-treewidth solutions due to Feldmann and Marx [The Complexity Landscape of Fixed-Parameter Directed Steiner Network Problems, preprint, ŭlhttps://arxiv.org/abs/1707.06808]. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a gridlike fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: our $2^{O(k)}\cdot n^{O(\sqrt{k})}$ algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. Additionally, we can obtain this running time for the problem of finding an optimal planar solution even if the input graph is not planar. In general graphs, we cannot hope for such a dramatic improvement over the $n^{O(k)}$ algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an $f(k)\cdot n^{o(k/\log k)}$ algorithm for any computable function $f$. Feldman and Ruhl generalized their $n^{O(k)}$ algorithm to the more general Directed Steiner Network (DSN) problem; here the task is to find a subgraph of minimum weight such that for every source $s_i$ there is a path to the corresponding terminal $t_i$. We show that, assuming ETH, there is no $f(k)\cdot n^{o(k)}$ time algorithm for DSN on acyclic planar graphs. All our lower bounds hold for the integer weighted edge version, while the algorithm works for the more general unweighted vertex version.

Although most game theory models assume that payoff matrices are provided as input, getting payoff matrices in strategic games (e.g., corporate negotiations and counter-terrorism operations) has proven difficult. To tackle this challenge, we propose a payoff inference engine (PIE) that finds payoffs assuming that players in a game follow a myopic best response or a regret minimization heuristic. This assumption yields a set of constraints (possibly nonlinear) on the payoffs with a multiplicity of solutions. PIE finds payoffs by considering solutions of these constraints and their variants via three heuristics. First, we approximately compute a centroid of the resulting polytope of the constraints. Second, we use a soft constraint approach that allows violation of constraints by penalizing violations in the objective function. Third, we develop a novel approach to payoff inference based on support vector machines (SVMs). Unlike past work on payoff inference, PIE has the following advantages. PIE supports reasoning about multiplayer games, not just one or two players, it can use short histories, not long ones which may not be available in many real-world situations, it does not require all players to be fully rational, and it is one to two orders of magnitude more scalable than past work. We run experiments on a synthetic data set where we generate payoff functions for the players and see how well our algorithms can learn them, a real-world coarse-grained counter-terrorism data set about a set of different terrorist groups, and a real-world fine-grained data set about a specific terrorist group. As the ground truth about payoffs for the terrorist groups cannot be tested directly, we test PIE by using the payoffs to make predictions about the actions of the groups and corresponding governments (even though this is not the purpose of this article). We show that compared with recent work on payoff inference, PIE has both higher accuracy and much shorter runtime.

We consider online variations of the Pandora’s box problem (Weitzman 1979), a standard model for understanding issues related to the cost of acquiring information for decision-making. Our problem generalizes both the classic Pandora’s box problem and the prophet inequality framework. Boxes are presented online, each with a random value and cost drawn jointly from some known distribution. Pandora chooses online whether to open each box given its cost, and then chooses irrevocably whether to keep the revealed prize or pass on it. We aim for approximation algorithms against adversaries that can choose the largest prize over any opened box, and use optimal offline policies to decide which boxes to open (without knowledge of the value inside)1. We consider variations where Pandora can collect multiple prizes subject to feasibility constraints, such as cardinality, matroid, or knapsack constraints. We also consider variations related to classic multi-armed bandit problems from reinforcement learning. Our results use a reduction-based framework where we separate the issues of the cost of acquiring information from the online decision process of which prizes to keep. Our work shows that in many scenarios, Pandora can achieve a good approximation to the best possible performance.

A valid edge-coloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. (Note that the maximum degree, Delta, is a trivial lower bound.) In this paper, we revisit this fundamental problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model: - Massively Parallel Computation: We give a randomized MPC algorithm that with high probability returns a Delta+O~(Delta^(3/4)) edge coloring in O(1) rounds using O(n) space per machine and O(m) total space. The space per machine can also be further improved to n^(1-Omega(1)) if Delta = n^Omega(1). Our algorithm improves upon a previous result of Harvey et al. [SPAA 2018]. - Graph Streaming: Since the output of edge-coloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors. We give a one-pass O~(n)-space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors with high probability if the edges arrive in a random order. For adversarial order streams, we give another one-pass O~(n)-space algorithm that requires O(Delta^2) colors.

We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph-which undergoes both edge insertions and deletions-in polylogarithmic time. Our algorithm is randomized and, per update, takes O(log2Δ log2n) expected time. Furthermore, the algorithm can be adjusted to have O(log2Δ log4n) worst-case update-time with high probability. Here, n denotes the number of vertices and Δ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC'18] who presented an algorithm with O(m3/4) update-time (and thus broke the natural Ω(m) barrier) where m denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had Õ(min{√n, m1/3}) update-time [Assadi et al. SODA'19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.

The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far more limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximal matching either take polylogarithmic time which is considered inefficient, or require a strictly super-linear space of n1+Ω(1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm. This affirmatively resolves the conjecture of Czumaj et al. [STOC'18] that a variant of this algorithm might work. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition. We show that this algorithm drastically reduces the vertex degrees. This, among some other results, leads to an O(log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space. This is the best possible approximation factor under standard assumptions, culminating a long line of research. It also leads to an improved O(log log Δ) round algorithm for 1+ ε approximate matching. All these results can also be implemented in the congested clique model within the same number of rounds.

Search ads have evolved in recent years from simple text formats to rich ads that allow deep site links, rating, images and videos. In this paper, we consider a model where several slots are available on the search results page, as in the classic generalized second-price auction (GSP), but now a bidder can be allocated several consecutive slots, which are interpreted as a rich ad. As in the GSP, each bidder submits a bid-per-click, but the click-through rate (CTR) function is generalized from a simple CTR for each slot to a general CTR function over sets of consecutive slots. We study allocation and pricing in this model under subadditive and fractionally subadditive CTRs. We design and analyze a constant-factor approximation algorithm for the efficient allocation problem under fractionally subadditive CTRs, and a log-approximation algorithm for the subadditive case. Building on these results, we show that approximate competitive equilibrium prices exist and can be computed for subadditive and fractionally subadditive CTRs, with the same guarantees as for allocation.

The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. In this work, we mainly consider maximal matching and maximal independent set problems in the MPC model.

The k-cut problem asks, given a connected graph G and a positive integer k, to find a minimum-weight set of edges whose removal splits G into k connected components. We give the first polynomial-time algorithm with approximation factor 2 – ∊ (with constant ∊ > 0) for the k-cut problem in planar and minor-free graphs. Applying more complex techniques, we further improve our method and give a polynomial-time approximation scheme for the k-cut problem in both planar and minor-free graphs. Despite persistent effort, to the best of our knowledge, this is the first improvement for the k-cut problem over standard approximation factor of 2 in any major class of graphs.

We consider the following stochastic matching problem on both weighted and unweighted graphs: A graph G(V, E) along with a parameter p ∊ (0, 1) is given in the input. Each edge of G is realized independently with probability p. The goal is to select a degree bounded (dependent only on p) subgraph H of G such that the expected maximum realized matching of H is close to that of G. This model of stochastic matching has attracted significant attention over the recent years due to its various applications in kidney exchange, online labor markets, and other matching markets. The most fundamental open question is the best approximation factor achievable for such algorithms that, in the literature, are referred to as non-adaptive algorithms. Prior work has identified breaking (near) half-approximation as a barrier for both weighted and unweighted graphs. Our main results are as follows: We analyze a simple and clean algorithm and show that for unweighted graphs, it finds an (almost) (≈ 0.6568) approximation by querying Õ(1/p) edges per vertex. This improves over the state-of-the-art 0.5001 approximation of Assadi et al. [EC’17]. We show that the same algorithm achieves a 0.501 approximation for weighted graphs by querying Õ(1/p) edges per vertex. This improves both, the approximation factor and the per-vertex queries of the 0.5 – ∊ approximations of Yamaguchi and Maehara [SODA’18] and Behnezhad and Reyhani [EC’18] which respectively required up to O(W log n/∊p) and O(1/p4/∊) queries.1 Interestingly, prior results were all based on similar algorithms and differed only in the analysis. Our algorithms are fundamentally different, yet very simple and natural. For the analysis, we introduce a number of procedures that construct heavy fractional matchings. We consider the new algorithms and our analytical tools to be the main contributions of this paper.

String similarity measures are among the most fundamental problems in computer science. The notable examples are edit distance (ED) and longest common subsequence (LCS). These problems find their applications in various contexts such as computational biology, text processing, compiler optimization, data analysis, image analysis, etc. In this work, we revisit edit distance and longest common subsequence in the parallel settings. We present massively parallel algorithms for both problems that are optimal in the following senses: The approximation factor of our algorithms is 1 + ∊. The round complexity of our algorithms is constant. The total running time of our algorithms over all machines is Õ(n2). This matches the running time of the best-known solutions for approximating edit distance and longest common subsequence within a 1 + ∊ factor in the sequential setting. Our result for edit distance substantially improves the massively parallel algorithm of [15] in terms of approximation factor, round complexity, number of machines, and total running time. Our unified approach to tackle both problems is to divide one of the strings into smaller blocks and try to locally predict which intervals of the other string correspond to each block in an optimal solution. Our main technical contribution is a novel parallel algorithm for computing a set of compositions, and recursively decomposing each function into a set of smaller iterative compositions (in terms of memory needed to solve the problem). These two methods together give us a strong tool for approximating combinatorial problems. For instance, LCS can be formulated as a recursive composition of functions and therefore this tool enables us to approximate LCS within a factor 1 + ∊. Indeed, we recursively decompose the problem until we are able to compute the solution on a single machine. Since our methods are quite general, we expect this technique to find its applications in other combinatorial problems as well.

Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinformatics, revision control systems, and data comparison programs1. Although a simple dynamic program computes LCS in quadratic time, it has been recently proven that the problem admits a conditional lower bound and may not be solved in truly subquadratic time [2]. In addition to this, LCS is notoriously hard with respect to approximation algorithms. Apart from a trivial sampling technique that obtains a nx approximation solution in time O(n2–2x) nothing else is known for LCS. This is in sharp contrast to its dual problem edit distance for which several linear time solutions are obtained in the past two decades [4, 5, 9, 10, 16]. In this work, we present the first nontrivial algorithm for approximating LCS in linear time. Our main result is a linear time algorithm for the longest common subsequence which has an approximation factor of O(n0.497956). This beats the barrier for approximating LCS in linear time.

Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usually much larger than the computer’s main memory; thus external memory sorting algorithms, first introduced by Aggarwal and Vitter (1988), are often used. The complexity of comparison based external memory sorting has been understood for decades by now, however the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of n integer keys of Θ(lgn) bits each in O(n) time using the classic Radix Sort algorithm, however in external memory, there are no faster integer sorting algorithms known than the simple comparison based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades.

Edit distance is one of the most fundamental problems in computer science. Tree edit distance is a natural generalization of edit distance to ordered rooted trees. Such a generalization extends the applications of edit distance to areas such as computational biology, structured data analysis (e.g., XML), image analysis, and compiler optimization. Perhaps the most notable application of tree edit distance is in the analysis of RNA molecules in computational biology where the secondary structure of RNA is typically represented as a rooted tree.

A valid edge-coloring of a graph is an assignment of "colors" to its edges such that no two incident edges receive the same color. The goal is to find a proper coloring that uses few colors. In this paper, we revisit this problem in two models of computation specific to massive graphs, the Massively Parallel Computations (MPC) model and the Graph Streaming model: Massively Parallel Computation. We give a randomized MPC algorithm that w.h.p., returns a (1+o(1))Delta edge coloring in O(1) rounds using O~(n) space per machine and O(m) total space. The space per machine can also be further improved to n^{1-Omega(1)} if Delta = n^{Omega(1)}. This is, to our knowledge, the first constant round algorithm for a natural graph problem in the strongly sublinear regime of MPC. Our algorithm improves a previous result of Harvey et al. [SPAA 2018] which required n^{1+Omega(1)} space to achieve the same result. Graph Streaming. Since the output of edge-coloring is as large as its input, we consider a standard variant of the streaming model where the output is also reported in a streaming fashion. The main challenge is that the algorithm cannot "remember" all the reported edge colors, yet has to output a proper edge coloring using few colors. We give a one-pass O~(n)-space streaming algorithm that always returns a valid coloring and uses 5.44 Delta colors w.h.p., if the edges arrive in a random order. For adversarial order streams, we give another one-pass O~(n)-space algorithm that requires O(Delta^2) colors.

We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.

Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main memory; thus external memory sorting algorithms, first introduced by Aggarwal and Vitter [ Commun. ACM, 31 (1988), pp. 1116--1127], are often used. The complexity of comparison based external memory sorting has been understood for decades by now, but the situation remains elusive if we assume the keys to be sorted are integers. In internal memory, one can sort a set of $n$ integer keys of $\Theta({lg} n)$ bits each in $O(n)$ time using the classic radix sort algorithm, but in external memory, there are no faster integer sorting algorithms known than the simple comparison based ones. Whether such algorithms exist has remained a central open problem in external memory algorithms for more than three decades. In this paper, we present a tight conditional lower bound on the complexity of external memory sorting of integers. Our lower bound is based on a famous conjecture in network coding by Li and Li [ Proceedings of the 42nd Allerton Annual Conference on Communication, Control and Computing, 2004], who conjectured that network coding cannot help anything beyond the standard multicommodity flow rate in undirected graphs. The only previous work connecting the Li and Li conjecture to lower bounds for algorithms is due to Adler et al. [ Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, 2006, pp. 241--250]. Adler et al. indeed obtain relatively simple lower bounds for oblivious algorithms (the memory access pattern is fixed and independent of the input data). Unfortunately obliviousness is a strong limitation, especially for integer sorting: we show that the Li and Li conjecture implies an $\Omega(n \log n)$ lower bound for internal memory oblivious sorting when the keys are $\Theta({lg} n)$ bits. This is in sharp contrast to the classic (nonoblivious) radix sort algorithm. Indeed going beyond obliviousness is highly nontrivial; we need to introduce several new methods and involved techniques, which are of their own interest, to obtain our tight lower bound for external memory integer sorting.

Solving large-scale graph problems is a fundamental task in many real-world applications, and it is an increasingly important problem in data analysis. Despite the large effort in designing scalable graph algorithms, many classic graph problems lack algorithms that require only a sublinear number of machines and space in the input size. Specifically when the input graph is large and sparse, which is indeed the case for many real-world graphs, it becomes impossible to store and access all the vertices in one machine - something that is often taken for granted in designing algorithms for massive graphs. The theoretical model that we consider is the Massively Parallel Communications (MPC) model which is a popular theoretical model of MapReduce-like systems. In this paper, we give an algorithmic framework to adapt a large family of dynamic programs on MPC. We start by introducing two classes of dynamic programming problems, namely "(poly log)-expressible" and "linear-expressible" problems. We show that both classes can be solved efficiently using a sublinear number of machines and a sublinear memory per machine. To achieve this result, we introduce a series of techniques that can be plugged together. To illustrate the generality of our framework, we implement in O(log n) rounds of MPC, the dynamic programming solution of fundamental problems such as minimum bisection, k-spanning tree, maximum independent set, longest path, etc., when the input graph is a tree.

In an instance of the network design problem, we are given a graph G=(V,E), an edge-cost function c:E -> R^{>= 0}, and a connectivity criterion. The goal is to find a minimum-cost subgraph H of G that meets the connectivity requirements. An important family of this class is the survivable network design problem (SNDP): given non-negative integers r_{u v} for each pair u,v in V, the solution subgraph H should contain r_{u v} edge-disjoint paths for each pair u and v. While this problem is known to admit good approximation algorithms in the offline case, the problem is much harder in the online setting. Gupta, Krishnaswamy, and Ravi [Gupta et al., 2012] (STOC'09) are the first to consider the online survivable network design problem. They demonstrate an algorithm with competitive ratio of O(k log^3 n), where k=max_{u,v} r_{u v}. Note that the competitive ratio of the algorithm by Gupta et al. grows linearly in k. Since then, an important open problem in the online community [Naor et al., 2011; Gupta et al., 2012] is whether the linear dependence on k can be reduced to a logarithmic dependency. Consider an online greedy algorithm that connects every demand by adding a minimum cost set of edges to H. Surprisingly, we show that this greedy algorithm significantly improves the competitive ratio when a congestion of 2 is allowed on the edges or when the model is stochastic. While our algorithm is fairly simple, our analysis requires a deep understanding of k-connected graphs. In particular, we prove that the greedy algorithm is O(log^2 n log k)-competitive if one satisfies every demand between u and v by r_{uv}/2 edge-disjoint paths. The spirit of our result is similar to the work of Chuzhoy and Li [Chuzhoy and Li, 2012] (FOCS'12), in which the authors give a polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. Moreover, we study the greedy algorithm in the online stochastic setting. We consider the i.i.d. model, where each online demand is drawn from a single probability distribution, the unknown i.i.d. model, where every demand is drawn from a single but unknown probability distribution, and the prophet model in which online demands are drawn from (possibly) different probability distributions. Through a different analysis, we prove that a similar greedy algorithm is constant competitive for the i.i.d. and the prophet models. Also, the greedy algorithm is O(log n)-competitive for the unknown i.i.d. model, which is almost tight due to the lower bound of [Garg et al., 2008] for single connectivity.

We study the proportional chore division problem where a protocol wants to divide an undesirable object, called chore, among n different players. This problem is the dual variant of the cake cutting problem in which we want to allocate a desirable object. In this paper, we show that chore division and cake cutting problems are closely related to each other and provide a tight lower bound for proportional chore division.

Protecting valuable \em targets from an adversary is an ever-important international concern with far-reaching applications in wildlife protection, border protection, counter-terrorism, protection of ships from piracy, etc. As a successful recent approach, \em security games cast these issues as two-player games between a \em defender and an \em attacker. The defender decides on how to allocate the available \em resources to protect targets against the attacker who strives to inflict damage on them. The main question of interest here is equilibrium computation. Our focus in this paper is on \em spatio-temporal security games. However, inspired by the paper of Xu [EC'16], we start with a general model of security games and show that any approximation (of any factor) for the defender's best response (DBR) problem leads to an approximation of the same factor for the actual game. In most applications of security games, the targets are mobile. This leads to a well-studied class of succinct games, namely \em spatio-temporal security games, that is played in space and time. In such games, the defender has to specify a time-dependent patrolling strategy over a spatial domain to protect a set of moving targets. We give a generalized model of prior spatio-temporal security games that is played on a base graph G . That is, the patrols can be placed on the vertices of G and move along its edges over time. This unifies and generalizes prior spatio-temporal models that only consider specific spatial domains such as lines or grids. Graphs can further model many other domains of practical interest such as roads, internal maps of buildings, etc. Finding an optimal defender strategy becomes NP-hard on general graphs. To overcome this, we give an LP relaxation of the DBR problem and devise a rounding technique to obtain an almost optimal integral solution. More precisely, we show that one can achieve a $(1-ε)$-approximation in polynomial time if we allow the defender to use $łceil łn(1/ε)\rceil$ times more patrols. We later show that this result is in some sense the best possible polynomial time algorithm (unless P=NP). Furthermore, we show that by using a novel \em dependent rounding technique, the same LP relaxation gives an optimal solution for specific domains of interest, such as one-dimensional spaces. This result simplifies and improves upon the prior algorithm of Behnezhad et al. ~[EC'17] on several aspects and can be generalized to other graphs of interest such as cycles. Lastly, we note that most prior algorithms for security games assume that the attacker attacks only once and become intractable for a super-constant number of attacks. Our algorithms are fully polynomial in the input size and work for any given number of attacks.

We study the problem of fair allocation for indivisible goods. We use the maxmin share paradigm introduced by Budish~\citeBudish:first as a measure for fairness. \procacciafirst ~\citeProcaccia:first were the first to investigate this fundamental problem in the additive setting. They show that a maxmin guarantee (1-$\MMS$ allocation) is not always possible even when the number of agents is limited to 3. While the existence of an approximation solution (e.g. a $1/2$-$\MMS$ allocation) is quite straightforward, improving the guarantee becomes subtler for larger constants. \sprocacciafirst ~\citeProcaccia:first provide a proof for the existence of a $2/3$-$\MMS$ allocation and leave the question open for better guarantees. Our main contribution is an answer to the above question. We improve the result of \sprocacciafirst~to a $3/4$ factor in the additive setting. The main idea for our $3/4$-$\MMS$ allocation method is clustering the agents. To this end, we introduce three notions and techniques, namely reducibility, matching allocation, and cycle-envy-freeness, and prove the approximation guarantee of our algorithm via non-trivial applications of these techniques. Our analysis involves coloring and double counting arguments that might be of independent interest. One major shortcoming of the current studies on fair allocation is the additivity assumption on the valuations. We alleviate this by extending our results to the case of submodular, fractionally subadditive, and subadditive settings. More precisely, we give constant approximation guarantees for submodular and XOS agents, and a logarithmic approximation for the case of subadditive agents. Furthermore, we complement our results by providing close upper bounds for each class of valuation functions. Finally, we present algorithms to find such allocations for additive, submodular, and XOS settings in polynomial time. The reader can find a summary of our results in Table \refresultstable.

We study mechanism design for procurement auctions in which the goal is to buy a subset of items or hire a team of providers. In order to measure the efficiency of a mechanism, one defines an appropriate benchmark which denotes a reasonable expectation of the payments and defines the overpayment of a mechanism based on the benchmark. This ratio is called the \em frugality ratio of the mechanism. Procurement auctions are well-studied and benchmarks proposed for these auctions have evolved over a sequence of papers ~\citearcher2007frugal,chen2010frugal,elkind2007frugality,karlinbeyond,kempe2010frugal. In this work, we introduce a newer benchmark, and based on that, study classic procurement auctions. Our benchmark addresses critical issues raised by the unintuitive behavior of the previous benchmarks. We show two attractive properties for our benchmark which have been lacking in the previous proposals: \em monotonicity and \em smoothness. Based on our benchmark, we provide positive results for vertex cover and knapsack auctions. Prior to this work, \kempefrugal\citekempe2010frugal propose a constant approximation mechanism for vertex cover auctions. However, their analysis suffers from an error. We give a correct analysis to the mechanism of \kempefrugal\citekempe2010frugal with respect to our benchmark. In particular, we prove their mechanism is optimal up to a constant factor. Our analysis is different from what \kempefrugal\citekempe2010frugal propose. We also study the knapsack auctions and give a truthful mechanism for such auctions with a bounded frugality ratio. We show that this is almost tight by presenting a lower bound on the frugality ratio of any truthful mechanism for such auctions. All our results depend on both properties of the benchmark.

Mixed strategies are often evaluated based on the expected payoff that they guarantee. This is not always desirable. In this paper, we consider games for which maximizing the expected payoff deviates from the actual goal of the players. To address this issue, we introduce the notion of a (u,p)-maxmin strategy which ensures receiving a minimum utility of u with probability at least p. We then give approximation algorithms for the problem of finding a (u, p)-maxmin strategy for these games. The first game that we consider is Colonel Blotto, a well-studied game that was introduced in 1921. In the Colonel Blotto game, two colonels divide their troops among a set of battlefields. Each battlefield is won by the colonel that puts more troops in it. The payoff of each colonel is the weighted number of battlefields that she wins. We show that maximizing the expected payoff of a player does not necessarily maximize her winning probability for certain applications of Colonel Blotto. For example, in presidential elections, the players’ goal is to maximize the probability of winning more than half of the votes, rather than maximizing the expected number of votes that they get. We give an exact algorithm for a natural variant of continuous version of this game. More generally, we provide constant and logarithmic approximation algorithms for finding (u, p)-maxmin strategies. We also introduce a security game version of Colonel Blotto which we call auditing game. It is played between two players, a defender and an attacker. The goal of the defender is to prevent the attacker from changing the outcome of an instance of Colonel Blotto. Again, maximizing the expected payoff of the defender is not necessarily optimal. Therefore we give a constant approximation for (u, p)-maxmin strategies.

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is “one of the biggest unsolved problems in the field of combinatorial pattern matching” [21]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n1.858) quantum algorithm that approximates the edit distance within a factor of 7. We further extend this result to an O(n1.781) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 3, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

Chore division, introduced by Gardner in 1970s [10], is the problem of fairly dividing a chore among n different agents. In particular, in an envy-free chore division, we would like to divide a negatively valued heterogeneous object among a number of agents who have different valuations for different parts of the object, such that no agent envies another agent. It is the dual variant of the celebrated cake cutting problem, in which we would like to divide a desirable object among agents. There has been an extensive amount of study and effort to design bounded and envy-free protocols/algorithms for fair division of chores and goods, such that envy-free cake cutting became one of the most important open problems in 20-th century mathematics according to Garfunkel [11]. However, despite persistent efforts, due to delicate nature of the problem, there was no bounded protocol known for cake cutting even among four agents, until the breakthrough of Aziz and Mackenzie [2], which provided the first discrete and bounded envy-free protocol for cake cutting for four agents. Afterward, Aziz and Mackenzie [3], generalized their work and provided an envy-free cake cutting protocol for any number of agents to settle a significant and longstanding open problem. However, there is much less known for chore division. Unfortunately, there is no general method known to apply cake cutting techniques to chore division. Thus, it remained an open problem to find a discrete and bounded envy-free chore division protocol even for four agents. In this paper, we provide the first discrete and bounded envy-free protocol for chore division for an arbitrary number of agents. We produce major and powerful tools for designing protocols for the fair division of negatively valued objects. These tools are based on structural results and important observations. In general, we believe these structures and techniques may be useful not only in chore division but also in other fairness problems. Interestingly, we show that applying these techniques simplifies Core Protocol provided in Aziz and Mackenzie [3].

The secretary and the prophet inequality problems are central to the field of Stopping Theory. Recently, there has been a lot of work in generalizing these models to multiple items because of their applications in mechanism design. The most important of these generalizations are to matroids and to combinatorial auctions (extends bipartite matching). Kleinberg-Weinberg [33] and Feldman et al. [17] show that for adversarial arrival order of random variables the optimal prophet inequalities give a 1/2-approximation. For many settings, however, it's conceivable that the arrival order is chosen uniformly at random, akin to the secretary problem. For such a random arrival model, we improve upon the 1/2-approximation and obtain (1 – 1/e)-approximation prophet inequalities for both matroids and combinatorial auctions. This also gives improvements to the results of Yan [45] and Esfandiari et al. [15] who worked in the special cases where we can fully control the arrival order or when there is only a single item. Our techniques are threshold based. We convert our discrete problem into a continuous setting and then give a generic template on how to dynamically adjust these thresholds to lower bound the expected total welfare.

The knapsack problem is a fundamental problem in combinatorial optimization. It has been studied extensively from theoretical as well as practical perspectives as it is one of the most well-known NP-hard problems. The goal is to pack a knapsack of size t with the maximum value from a collection of n items with given sizes and values.

Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each node, namely, cost and prize (or penalty). They give an $O(\log n)$-approximation algorithm for the node-weighted prize-collecting Steiner tree problem (PCST)---where the goal is to minimize the cost of a tree plus the penalty of vertices not covered by the tree. They use the algorithm for PCST to obtain a bicriteria $(2, O(\log n))$-approximation algorithm for the budgeted node-weighted Steiner tree problem---where the goal is to maximize the prize of a tree with a given budget for its cost. Their solution may cost up to twice the budget, but collects a factor $\Omega(\frac{1}{\log n})$ of the optimal prize. We improve these results from at least two aspects. Our first main result is a primal-dual $O(\log h)$-approximation algorithm for a more general problem, node-weighted prize-collecting Steiner forest (PCSF), where we have $h$ demands each requesting the connectivity of a pair of vertices. Our algorithm can be seen as a greedy algorithm which reduces the number of demands by choosing a structure with minimum cost-to-reduction ratio. This natural style of argument leads to a much simpler algorithm than that of Moss and Rabani for PCST. Our second main contribution is for the budgeted node-weighted Steiner tree problem, which is also an improvement to the work of Moss and Rabani. In the unrooted case, we improve upon an existing $O(\log^2 n)$-approximation by Guha et al., and present an $O(\log n)$-approximation algorithm without any budget violation. For the rooted case, where a specified vertex has to appear in the solution tree, we improve the bicriteria result of Moss and Rabani to the bicriteria approximation ratio of $(1+\epsilon, O(\log n)/\epsilon^2)$ for any positive (possibly subconstant) $\epsilon$. That is, for any permissible budget violation $1+\epsilon$, we present an algorithm achieving a trade off in the guarantee for the prize. Indeed, we show that this is almost tight for the natural linear-programming relaxation used by us as well as in the previous works.

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that, with high probability, estimates the size of a maximum matching within a constant factor using Õ( n 2/3 ) space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model) in o ( n ) space. We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We further reduce the required memory size to Õ(√ n ) for three restricted settings: (i) when the input graph is a forest; (ii) when we have 2-passes and the input graph has bounded arboricity; and (iii) when the edges arrive in random order and the input graph has bounded arboricity. Finally, we design a reduction from the Boolean Hidden Matching Problem to show that there is no randomized streaming algorithm that estimates the size of the maximum matching to within a factor better than 3/2 and uses only o ( n 1/2 ) bits of space. Using the same reduction, we show that there is no deterministic algorithm that computes this kind of estimate in o ( n ) bits of space. The lower bounds hold even for graphs that are collections of paths of constant length.

Internet-enabled marketplaces such as Amazon deal with huge datasets registering transaction of merchandises between lots of buyers and sellers. It is important that algorithms become more time and space efficient as the size of datasets increase. An algorithm that runs in polynomial time may not have a reasonable running time for such large datasets. Here, we study the development of pricing algorithms that are appropriate for use with massive datasets. We especially focus on the streaming setting, the common model for big data analysis. We present an envy-free mechanism for social welfare maximization problem in the streaming setting using O(k2 l) space, where k is the number of different goods and l is the number of available items of each good. We also provide an α-approximation mechanism for revenue maximization in this setting given an α-approximation mechanism for the corresponding offline problem exists. Moreover, we provide mechanisms to approximate the optimum social welfare (or revenue) within 1 – ε factor, in space independent of l which would be favorable in case l is large compared to k. Finally, we present hardness results showing approximation of optimal prices that maximize social welfare (or revenue) in the streaming setting needs Ω(l) space. We achieve our results by developing a powerful sampling technique for bipartite networks. The simplicity of our sampling technique empowers us to maintain the sample over the input sequence. Indeed, one can construct this sample in the distributed setting (a.k.a, MapReduce) and get the same results in two rounds of computations, or one may simply apply this sampling technique to provide faster offline algorithms.

In the Colonel Blotto game, which was initially introduced by Borel in 1921, two colonels simultaneously distribute their troops across different battlefields.The winner of each battlefield is determined independently by a winner-take-all rule. The ultimate payoff of each colonel is the number of battlefields he wins. This game is commonly used for analyzing a wide range of applications such as the U.S presidential election, innovative technology competitions, advertisements, etc. There have been persistent efforts for finding the optimal strategies for the Colonel Blotto game. After almost a century Ahmadinejad, Dehghani, Hajiaghayi, Lucier, Mahini, and Seddighin provided a poly-time algorithm for finding the optimal strategies. They first model the problem by a Linear Program (LP) with exponential number of constraints and use Ellipsoid method to solve it. However, despite the theoretical importance of their algorithm, it ishighly impractical. In general, even Simplex method (despite its exponential running-time) performs better than Ellipsoid method in practice. In this paper, we provide the first polynomial-size LP formulation of the optimal strategies for the Colonel Blotto game. We use linear extension techniques. Roughly speaking, we project the strategy space polytope to a higher dimensional space, which results in a lower number of facets for the polytope.We use this polynomial-size LP to provide a novel, simpler and significantly faster algorithm for finding the optimal strategies for the Colonel Blotto game. We further show this representation is asymptotically tight in terms of the number of constraints. We also extend our approach to multi-dimensional Colonel Blotto games, and implement our algorithm to observe interesting properties of Colonel Blotto; for example, we observe the behavior of players in the discrete model is very similar to the previously studied continuous model.

In this paper we study a stochastic variant of the celebrated $k$-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are serving an online sequence of $t$ requests in a metric. In the stochastic setting we are given t independent distributions in advance, and at every time step i a request is drawn from P_i. Designing the optimal online algorithm in such setting is NP-hard, therefore the emphasis of our work is on designing an approximately optimal online algorithm. We first show a structural characterization for a certain class of non-adaptive online algorithms. We prove that in general metrics, the best of such algorithms has a cost of no worse than three times that of the optimal online algorithm. Next, we present an integer program that finds the optimal algorithm of this class for any arbitrary metric. Finally by rounding the solution of the linear relaxation of this program, we present an online algorithm for the stochastic k-server problem with an approximation factor of $3$ in the line and circle metrics and factor of O(log n) in general metrics. In this way, we achieve an approximation factor that is independent of k, the number of servers. Moreover, we define the Uber problem, motivated by extraordinary growth of online network transportation services. In the Uber problem, each demand consists of two points -a source and a destination- in the metric. Serving a demand is to move a server to its source and then to its destination. The objective is again minimizing the total movement of the k given servers. It is not hard to show that given an alpha-approximation algorithm for the k-server problem, we can obtain a max{3,alpha}-approximation algorithm for the Uber problem. Motivated by the fact that demands are usually highly correlated with the time (e.g. what day of the week or what time of the day the demand is arrived), we study the stochastic Uber problem. Using our results for stochastic k-server we can obtain a 3-approximation algorithm for the stochastic Uber problem in line and circle metrics, and a O(log n)-approximation algorithm for a general metric of size n. Furthermore, we extend our results to the correlated setting where the probability of a request arriving at a certain point depends not only on the time step but also on the previously arrived requests.

Graph clustering is a fundamental task in many data-mining and machine-learning pipelines. In particular, identifying a good hierarchical structure is at the same time a fundamental and challenging problem for several applications. The amount of data to analyze is increasing at an astonishing rate each day. Hence there is a need for new solutions to efficiently compute effective hierarchical clusterings on such huge data. The main focus of this paper is on minimum spanning tree (MST) based clusterings. In particular, we propose affinity, a novel hierarchical clustering based on Boruvka's MST algorithm. We prove certain theoretical guarantees for affinity (as well as some other classic algorithms) and show that in practice it is superior to several other state-of-the-art clustering algorithms. Furthermore, we present two MapReduce implementations for affinity. The first one works for the case where the input graph is dense and takes constant rounds. It is based on a Massively Parallel MST algorithm for dense graphs that improves upon the state-of-the-art algorithm of Lattanzi et al. (SPAA 2011). Our second algorithm has no assumption on the density of the input graph and finds the affinity clustering in $O(\log n)$ rounds using Distributed Hash Tables (DHTs). We show experimentally that our algorithms are scalable for huge data sets, e.g., for graphs with trillions of edges.

An ever-important issue is protecting infrastructure and other valuable targets from a range of threats from vandalism to theft to piracy to terrorism. The "defender" can rarely afford the needed resources for a 100% protection. Thus, the key question is, how to provide the best protection using the limited available resources.

Hill and Kertz studied the prophet inequality on iid distributions [The Annals of Probability 1982]. They proved a theoretical bound of 1 - 1/e on the approximation factor of their algorithm. They conjectured that the best approximation factor for arbitrarily large n is 1/1+1/e ≃ 0.731. This conjecture remained open prior to this paper for over 30 years. In this paper we present a threshold-based algorithm for the prophet inequality with n iid distributions. Using a nontrivial and novel approach we show that our algorithm is a 0.738-approximation algorithm. By beating the bound of 1/1+1/e, this refutes the conjecture of Hill and Kertz. Moreover, we generalize our results to non-uniform distributions and discuss its applications in mechanism design.

We give the first polynomial-time online algorithm for the node-weighted Steiner forest problem with a poly-logarithmic competitive ratio. The competitive ratio of our algorithm is optimal up to a logarithmic factor. For the special case of graphs with an excluded fixed minor (e.g., planar graphs), we obtain a logarithmic competitive ratio, which is optimal up to a constant, using a different online algorithm. Both these results are obtained as special cases of generic results for a large class of problems that can be encoded as online $\{0, 1\}$- proper functions. Our results are obtained by using a new framework for online network design problems that we call disk paintings. The central idea in this technique is to amortize the cost of primal updates to a set of carefully selected mutually disjoint fixed-radius dual disks centered at a subset of terminals. We hope that this framework will be useful for other online network design problems.

We study the following basic problem called Bi-Covering. Given a graph $G(V,E)$, find two (not necessarily disjoint) sets $A\subseteq V$ and $B\subseteq V$ such that $A\cup B = V$ and such that every edge $e$ belongs to either the graph induced by $A$ or the graph induced by $B$. The goal is to minimize $\max\{|A|,|B|\}$. This is the most simple case of the Channel Allocation problem [R. Gandhi et al., Networks, 47 (2006), pp. 225--236]. A solution that outputs $V,\emptyset$ gives ratio at most 2. We show that under a similar strong Unique Games Conjecture by Bansal and Khot [ Optimal long code test with one free bit, in Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS'09, IEEE, 2009, pp. 453--462] there is no $2-\epsilon$ ratio algorithm for the problem, for any constant $\epsilon>0$. Given a bipartite graph, Max-Bi-Clique is a problem of finding the largest $k\times k$ complete bipartite subgraph. For the Max-Bi-Clique problem, a constant factor hardness was known under a random 3-SAT hypothesis of Feige [ Relations between average case complexity and approximation complexity, in Proceedings of the 34th Annual ACM Symposium on Theory of Computing, ACM, 2002, pp. 534--543] and also under the assumption that ${{\sc NP}}\nsubseteq \mathop{\cap}_{\epsilon>0} \mathsf{DTIME}(2^{n^\epsilon})$ [S. Khot, SIAM J. Comput., 36 (2006), pp. 1025--1071]. It was an open problem in [C. Ambühl, M. Mastrolilli, and O. Svensson, SIAM J. Comput., 40 (2011), pp. 567--596] to prove inapproximability of Max-Bi-Clique assuming weaker conjecture. Our result implies a similar hardness result assuming the Strong Unique Games Conjecture. On the algorithmic side, we also give better than 2 approximation for Bi-Covering on numerous special graph classes. In particular, we get 1.876 approximation for chordal graphs, an exact algorithm for interval graphs, $1+o(1)$ for minor free graphs, $2-4\delta/3$ for graphs with minimum degree $\delta n$, $2/(1+\delta^2/8)$ for $\delta$-vertex expander, $8/5$ for split graphs, $2-(6/5)\cdot 1/d$ for graphs with minimum constant degree $d$, etc. Our algorithmic results are quite nontrivial. In achieving these results, we use various known structural results about the graphs combined with the techniques that we develop tailored to getting better than 2 approximation.

Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of $0.5$. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of $1/e\approx 0.36$ In this paper, we introduce prophet secretary, a natural combination of the prophet inequality and the secretary problems. In the prophet secretary problem we are given a set $\{D_1,\ldots,D_n\}$ of (not necessarily identical) distributions. A number $X_i$ is drawn from each distribution $D_i$ and then, after applying a random permutation $\pi_1,\ldots, \pi_n$, the numbers are given to us in an online fashion, i.e., at step $k$, $X_{\pi_k}$ is revealed. We are allowed to choose only one number, which can be done only upon receiving that number. The goal is to maximize the expectation of the chosen value, compared to the expectation of the optimum offline solution that knows the drawn values in advance. In particular, we show that by using a single uniform threshold one cannot break the 0.5 barrier of the prophet inequality for the prophet secretary problem. However, we show that $\bullet$ using $n$ distinct nonadaptive thresholds one can obtain a competitive ratio that goes to $(1-1/e \approx 0.63)$ as $n$ grows, and $\bullet$ no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to $(1-1/e)$ when the order of agents (customers) is chosen randomly. We also consider the minimization variants of stopping theory problems and, in particular, the prophet secretary problem. Interestingly, we show that, even for the simple case in which the input elements are drawn from identical and independent distributions, there is no constant competitive online algorithm for the minimization variant of the prophet secretary problems. We extend this hardness result to the minimization variants of both the prophet inequality and the secretary problem as well.

We study the problem of computing Nash equilibria of zero-sum games.Many natural zero-sum games have exponentially many strategies, but highly structured payoffs. For example, in the well-studied Colonel Blotto game (introduced by Borel in 1921), players must divide a pool of troops among a set of battlefields with the goal of winning (i.e., having more troops in) a majority. The Colonel Blotto game is commonly used for analyzing a wide range of applications from the U.S presidential election, to innovative technology competitions, toadvertisement, to sports.However, because of the size of the strategy space, standard methods for computing equilibria of zero-sum games fail to be computationally feasible.Indeed, despite its importance, only few solutions for special variants of the problem are known. In this paper we show how to compute equilibria of Colonel Blotto games. Moreover, our approach takes the form of a general reduction: to find a Nash equilibrium of a zero-sum game, it suffices to design a separation oracle for the strategy polytope of any bilinear game that is payoff-equivalent. We then apply this technique to obtain the first polytime algorithms for a variety of games. In addition to Colonel Blotto, we also show how to compute equilibria in an infinite-strategy variant called the General Lotto game; this involves showing how to prune the strategy space to a finite subset before applying our reduction. We also consider the class of dueling games, first introduced by Immorlica et al. (2011). We show that our approach provably extends the class of dueling games for which equilibria can be computed: we introduce a new dueling game, the matching duel, on which prior methods fail to be computationally feasible but upon which our reduction can be applied.

We prove the first non-trivial performance ratios strictly above 0.5 for weighted versions of the oblivious matching problem. Even for the unweighted version, since Aronson, Dyer, Frieze, and Suen first proved a non-trivial ratio above 0.5 in the mid-1990s, during the next twenty years several attempts have been made to improve this ratio, until Chan, Chen, Wu and Zhao successfully achieved a significant ratio of 0.523 very recently (SODA 2014). To the best of our knowledge, our work is the first in the literature that considers the node-weighted and edge-weighted versions of the problem in arbitrary graphs (as opposed to bipartite graphs). (1) For arbitrary node weights, we prove that a weighted version of the Ranking algorithm has ratio strictly above 0.5. We have discovered a new structural property of the ranking algorithm: if a node has two unmatched neighbors at the end of algorithm, then it will still be matched even when its rank is demoted to the bottom. This property allows us to form LP constraints for both the node-weighted and the unweighted oblivious matching problems. As a result, we prove that the ratio for the node-weighted case is at least 0.501512. Interestingly via the structural property, we can also improve slightly the ratio for the unweighted case to 0.526823 (from the previous best 0.523166 in SODA 2014). (2) For a bounded number of distinct edge weights, we show that ratio strictly above 0.5 can be achieved by partitioning edges carefully according to the weights, and running the (unweighted) Ranking algorithm on each part. Our analysis is based on a new primal-dual framework known as \emph{matching coverage}, in which dual feasibility is bypassed. Instead, only dual constraints corresponding to edges in an optimal matching are satisfied. Using this framework we also design and analyze an algorithm for the edge-weighted online bipartite matching problem with free disposal. We prove that for the case of bounded online degrees, the ratio is strictly above 0.5.

We study the following basic problem called Bi-Covering. Given a graph G(V, E), find two (not necessarily disjoint) sets A subseteq V and B subseteq V such that A union B = V and that every edge e belongs to either the graph induced by A or to the graph induced by B. The goal is to minimize max{|A|, |B|}. This is the most simple case of the Channel Allocation problem [Gandhi et al., Networks, 2006]. A solution that outputs V,emptyset gives ratio at most 2. We show that under the similar Strong Unique Game Conjecture by [Bansal-Khot, FOCS, 2009] there is no 2 - epsilon ratio algorithm for the problem, for any constant epsilon > 0. Given a bipartite graph, Max-bi-clique is a problem of finding largest k*k complete bipartite sub graph. For Max-bi-clique problem, a constant factor hardness was known under random 3-SAT hypothesis of Feige [Feige, STOC, 2002] and also under the assumption that NP !subseteq intersection_{epsilon > 0} BPTIME(2^{n^{epsilon}}) [Khot, SIAM J. on Comp., 2011]. It was an open problem in [Ambühl et. al., SIAM J. on Comp., 2011] to prove inapproximability of Max-bi-clique assuming weaker conjecture. Our result implies similar hardness result assuming the Strong Unique Games Conjecture. On the algorithmic side, we also give better than 2 approximation for Bi-Covering on numerous special graph classes. In particular, we get 1.876 approximation for Chordal graphs, exact algorithm for Interval Graphs, 1 + o(1) for Minor Free Graph, 2 - 4*delta/3 for graphs with minimum degree delta*n, 2/(1+delta^2/8) for delta-vertex expander, 8/5 for Split Graphs, 2 - (6/5)*1/d for graphs with minimum constant degree d etc. Our algorithmic results are quite non-trivial. In achieving these results, we use various known structural results about the graphs, combined with the techniques that we develop tailored to getting better than 2 approximation.

We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest (EW-DB-SF) problem and its generalized variant. We obtain our result by demonstrating a new generic approach for solving mixed packing/covering integer programs in the online paradigm. In EW-DB-SF, we are given an edge-weighted graph with a degree bound for every vertex. Given a root vertex in advance, we receive a sequence of terminal vertices in an online manner. Upon the arrival of a terminal, we need to augment our solution subgraph to connect the new terminal to the root. The goal is to minimize the total weight of the solution while respecting the degree bounds on the vertices. In the offline setting, edge-weighted degree-bounded Steiner tree (EW-DB-ST) and its many variations have been extensively studied since early eighties. Unfortunately, the recent advancements in the online network design problems are inherently difficult to adapt for degree-bounded problems. In particular, it is not known whether the fractional solution obtained by standard primal-dual techniques for mixed packing/covering LPs can be rounded online. In contrast, in this paper we obtain our result by using structural properties of the optimal solution, and reducing the EW-DB-SF problem to an exponential-size mixed packing/covering integer program in which every variable appears only once in covering constraints. We then design a generic integral algorithm for solving this restricted family of IPs. As mentioned above, we demonstrate a new technique for solving mixed packing/covering integer programs. Define the covering frequency k of a program as the maximum number of covering constraints in which a variable can participate. Let m denote the number of packing constraints. We design an online deterministic integral algorithm with competitive ratio of O(k*log(m)) for the mixed packing/covering integer programs. We prove the tightness of our result by providing a matching lower bound for any randomized algorithm. We note that our solution solely depends on m and k. Indeed, there can be exponentially many variables. Furthermore, our algorithm directly provides an integral solution, even if the integrality gap of the program is unbounded. We believe this technique can be used as an interesting alternative for the standard primal-dual techniques in solving online problems.

We study competition in a general framework introduced by Immorlica, Kalai, Lucier, Moitra, Postlewaite, and Tennenholtz and answer their main open question. Immorlica et al. considered classic optimization problems in terms of competition and introduced a general class of games called dueling games. They model this competition as a zero-sum game, where two players are competing for a user’s satisfaction. In their main and most natural game, the ranking duel, a user requests a webpage by submitting a query and players output an ordering over all possible webpages based on the submitted query. The user tends to choose the ordering which displays her requested webpage in a higher rank. The goal of both players is to maximize the probability that her ordering beats that of her opponent and gets the user's attention. Immorlica et al. show this game directs both players to provide suboptimal search results. However, they leave the following as their main open question: "does competition between algorithms improve or degrade expected performance?" (see the introduction for more quotes) In this paper, we resolve this question for the ranking duel and a more general class of dueling games. More precisely, we study the quality of orderings in a competition between two players. This game is a zero-sum game, and thus any Nash equilibrium of the game can be described by minimax strategies. Let the value of the user for an ordering be a function of the position of her requested item in the corresponding ordering, and the social welfare for an ordering be the expected value of the corresponding ordering for the user. We propose the price of competition which is the ratio of the social welfare for the worst minimax strategy to the social welfare obtained by asocial planner. Finding the price of competition is another approach to obtain structural results of Nash equilibria. We use this criterion for analyzing the quality of orderings in the ranking duel. Although Immorlica et al. show that the competition leads to suboptimal strategies, we prove the quality of minimax results is surprisingly close to that of the optimum solution. In particular, via a novel factor-revealing LP for computing price of anarchy, we prove if the value of the user for an ordering is a linear function of its position, then the price of competition is at least 0.612 and bounded above by 0.833. Moreover we consider the cost minimization version of the problem. We prove, the social cost of the worst minimax strategy is at most 3 times the optimal social cost. Last but not least, we go beyond linear valuation functions and capture the main challenge for bounding the price of competition for any arbitrary valuation function. We present a principle which states that the lower bound for the price of competition for all 0-1 valuation functions is the same as the lower bound for the price of competition for all possible valuation functions. It is worth mentioning that this principle not only works for the ranking duel but also for all dueling games. This principle says, in any dueling game, the most challenging part of bounding the price of competition is finding a lower bound for 0-1 valuation functions. We leverage this principle to show that the price of competition is at least 0.25 for the generalized ranking duel.

In this paper we present a simple but powerful subgraph sampling primitive that is applicable in a variety of computational models including dynamic graph streams (where the input graph is defined by a sequence of edge/hyperedge insertions and deletions) and distributed systems such as MapReduce. In the case of dynamic graph streams, we use this primitive to prove the following results: Matching: Our main result for matchings is that there exists an Õ(k2) space algorithm that returns the edges of a maximum matching on the assumption the cardinality is at most k. The best previous algorithm used Õ(kn) space where n is the number of vertices in the graph and we prove our result is optimal up to logarithmic factors. Our algorithm has Õ(1) update time. We also show that there exists an Õ(n2/α3) space algorithm that returns an α-approximation for matchings of arbitrary size. In independent work, Assadi et al. (SODA 2016) proved this approximation algorithm is optimal and provided an alternative algorithm. We generalize our exact and approximate algorithms to weighted matching. For graphs with low arboricity such as planar graphs, the space required for constant approximation can be further reduced. While there has been a substantial amount of work on approximate matching in insert-only graph streams, these are the first nontrivial results in the dynamic setting. Vertex Cover and Hitting Set: There exists an Õ(kd) space algorithm that solves the minimum hitting set problem where d is the cardinality of the input sets and k is an upper bound on the size of the minimum hitting set. We prove this is optimal up to logarithmic factors. Our algorithm has Õ(1) update time. The case d = 2 corresponds to minimum vertex cover. Finally, we consider a larger family of parameterized problems (including b-matching, disjoint paths, vertex coloring among others) for which our subgraph sampling primitive yields fast, small-space dynamic graph stream algorithms. We then show lower bounds for natural problems outside this family.

We initiate the study of degree-bounded network design problems in the online setting. The degree-bounded Steiner tree problem – which asks for a subgraph with minimum degree that connects a given set of vertices – is perhaps one of the most representative problems in this class. This paper deals with its well-studied generalization called the degree-bounded Steiner forest problem where the connectivity demands are represented by vertex pairs that need to be individually connected. In the classical online model, the input graph is given offline but the demand pairs arrive sequentially in online steps. The selected subgraph starts off as the empty subgraph, but has to be augmented to satisfy the new connectivity constraint in each online step. The goal is to be competitive against an adversary that knows the input in advance. The standard techniques for solving degree-bounded problems often fall in the category of iterative and dependent rounding techniques. Unfortunately, these rounding methods are inherently difficult to adapt to an online settings since the underlying fractional solution may change dramatically in between the rounding steps. Indeed, this might be the very reason that despite many advances in the online network design paradigm in the past two decades, the natural family of degree-bounded problems has remained widely open. In this paper, we design an intuitive greedy-like algorithm that achieves a competitive ratio of O(log n) where n is the number of vertices. We show that no (randomized) algorithm can achieve a (multiplicative) competitive ratio o(log n); thus our result is asymptotically tight. We further show strong hardness results for the group Steiner tree and the edge-weighted variants of degree-bounded connectivity problems. Fürer and Raghavachari resolved the offline variant of degree-bounded Steiner forest in their paper in SODA'92. Since then, the family of degree-bounded network design problems has been extensively studied in the literature resulting in the development of many interesting tools and numerous papers on the topic. We hope that our approach and its dual analysis, paves the way for solving the online variants of the classical problems in this family of problems.

In this paper we provide a framework to analyze the effect of uniform sampling on graph optimization problems. Interestingly, we apply this framework to a general class of graph optimization problems that we call heavy subgraph problems, and show that uniform sampling preserves a 1-ε approximate solution to these problems. This class contains many interesting problems such as densest subgraph, directed densest subgraph, densest bipartite subgraph, d-max cut, and d-sum-max clustering. As an immediate impact of this result, one can use uniform sampling to solve these problems in streaming, turnstile or Map-Reduce settings. Indeed, our results by characterizing heavy subgraph problems address Open Problem 13 at the IITK Workshop on Algorithms for Data Streams in 2006 regarding the effects of subsampling, in the context of graph streams.

We present the first polynomial-time approximation scheme (PTAS), i.e., (1+ε)-approximation algorithm for any constant ε> 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O(logn (loglogn)O(1)). We achieve this result via a novel and powerful technique called spanner bootstrapping, which allows one to bootstrap from a superconstant approximation factor (even superpolynomial in the input size) all the way down to a PTAS. This is in contrast with the popular existing approach for planar PTASs of constructing light-weight spanners in one iteration, which notably requires a constant-factor approximate solution to start from. Spanner bootstrapping removes one of the main barriers for designing PTASs for problems which have no known constant-factor approximation (even on planar graphs), and thus can be used to obtain PTASs for several difficult-to-approximate problems.

We introduce a new technique for designing fixed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the first fixed-parameter algorithms (FPT algorithms) with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in $2^{O(k^2\log |\Sigma|)}n^4\log n$ deterministic time (even in the stronger, vertex-deletion variant), where $k$ is the number of unsatisfied edges and $|\Sigma|$ is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satisfied is upper bounded by $O(\sqrt{\log n})$ to optimality, which improves over the trivial $O(1)$ upper bound. We prove that the Steiner Cut problem can be solved in $2^{O(k^2\log k)}n^4\log n$ deterministic time and $\tilde{O}(2^{O(k^2\log k)}n^2)$ randomized time, where $k$ is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering “cut” and “uncut” constraints at the same time. More precisely, we define a robust problem, Node Multiway Cut-Uncut, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in $2^{O(k^2\log k)}n^4\log n$ deterministic time, where $k$ is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights.

In this article, we consider the fault-tolerant k -median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of the classical k -median problem, each client j needs to be assigned to at least r j ⩾ 1 distinct open facilities. The service cost of j is the sum of its distances to the r j facilities, and the k -median constraint restricts the number of open facilities to at most k . Previously, a constant factor was known only for the special case when all r j s are the same, and alogarithmic approximation ratio was known for the general case. In addition, we present the first polynomial time algorithm for the fault-tolerant k -median problem on a path or an HST by showing that the corresponding LP always has an integral optimal solution. We also consider the fault-tolerant facility location problem, in which the service cost of j can be a weighted sum of its distance to the r j facilities. We give a simple constant factor approximation algorithm, generalizing several previous results that work only for nonincreasing weight vectors.

In the Movement Repairmen (MR) problem, we are given a metric space ( V , d ) along with a set R of k repairmen r 1 , r 2 , …, r k with their start depots s 1 , s 2 , …, s k ∈ V and speeds v 1 , v 2 , …, v k ⩾ 0, respectively, and a set C of m clients c 1 , c 2 , …, c m having start locations s ′ 1 , s ′ 2 , …, s ′ m ∈ V and speeds v ′ 1 , v ′ 2 , …, v ′ m ⩾ 0, respectively. If t is the earliest time a client c j is collocated with any repairman (say, r i ) at a node u , we say that the client is served by r i at u and that its latency is t . The objective in the (S um -MR) problem is to plan the movements for all repairmen and clients to minimize the sum (average) of the clients’ latencies. The motivation for this problem comes, for example, from Amazon Locker Delivery [Amazon 2010] and USPS gopost [Service 2010]. We give the first O (log n )-approximation algorithm for the S um -MR problem. In order to approximate S um -MR, we formulate an LP for the problem and bound its integrality gap. Our LP has exponentially many variables; therefore, we need a separation oracle for the dual LP. This separation oracle is an instance of the Neighborhood Prize Collecting Steiner Tree (NPCST) problem in which we want to find a tree with weight at most L collecting the maximum profit from the clients by visiting at least one node from their neighborhoods. The NPCST problem, even with the possibility to violate both the tree weight and neighborhood radii, is still very hard to approximate. We deal with this difficulty by using LP with geometrically increasing segments of the timeline, and by giving a tricriteria approximation for the problem. The rounding needs a relatively involved analysis. We give a constant approximation algorithm for S um -MR in Euclidean Space where the speed of the clients differs by a constant factor. We also give a constant approximation for the makespan variant.

Advertising activity on SNS has grown rapidly and is now a billion dollar business. In the SNS advertising model, the SNS serves as the advertising agent, and takes the advantage of network diffusion to attract advertisers and charges for the cascading impressions. The optimal ad allocation task is to choose the ad allocation plan that maximizes the revenue. Each user has different diffusion ability, limited daily impressions and the advertisers have various bidding prices and budget concerns. A feasible plan that obeys the constraints is difficult to find. The solution of this problem lies in the space of N |Ads|× |user|, which makes direct optimization unattractive. In this paper, we study SNS advertising business models, formulate the SNS ad allocation problem and show their connections with hyperbolic embedding. We develop a new embedding algorithm Hyper Cube Map that allows for dimension reduction. Our proposed method reduces the dimensionality of the original problem significantly, runs two to four orders of magnitude faster, and reaches 95% of the optimum.

People make decisions and express their opinions according to their communities. A natural idea for controlling the diffusion of a behavior is to find influential people, and employ them to spread a desired behavior. We investigate an influencing problem when individuals' behaviors are affected by their friends in an opinion formation process. Our goal is to design efficient algorithms for finding opinion leaders such that changing their opinions has a great impact on the overall external behaviors in the society. We study directed social networks and define a set of problems like maximizing the sum of individuals' behaviors or maximizing the number of individuals whose external behaviors are above a threshold. We discuss the complexity of the defined problems and design polynomial-time optimum algorithms for the non NP-hard variants of them. We also propose polynomial-time approximation algorithms with guaranteed performances and prove inapproximability results for the NP-hard variants of these problems. Furthermore, we run simulations on real-world social networks and show our proposed algorithm outperforms the classical algorithms such as degree-based algorithm, closeness-based algorithm, and pagerank-based algorithm.

As graphs continue to grow in size, we seek ways to effectively process such data at scale. The model of streaming graph processing, in which a compact summary is maintained as each edge insertion/deletion is observed, is an attractive one. However, few results are known for optimization problems over such dynamic graph streams. In this paper, we introduce a new approach to handling graph streams, by instead seeking solutions for the parameterized versions of these problems. Here, we are given a parameter k and the objective is to decide whether there is a solution bounded by k. By combining kernelization techniques with randomized sketch structures, we obtain the first streaming algorithms for the parameterized versions of Maximal Matching and Vertex Cover. We consider various models for a graph stream on n nodes: the insertion-only model where the edges can only be added, and the dynamic model where edges can be both inserted and deleted. More formally, we show the following results: In the insertion only model, there is a one-pass deterministic algorithm for the parameterized Vertex Cover problem which computes a sketch using Õ(k2) space1 such that at each timestamp in time Õ(2k) it can either extract a solution of size at most k for the current instance, or report that no such solution exists. We also show a tight lower bound of Ω(k2) for the space complexity of any (randomized) streaming algorithms for the parameterized Vertex Cover, even in the insertion-only model. In the dynamic model, and under the promise that at each timestamp there is a maximal matching of size at most k, there is a one-pass Õ(k2)-space (sketch-based) dynamic algorithm that maintains a maximal matching with worst-case update time Õ(k2). This algorithm partially solves Open Problem 64 from [1]. An application of this dynamic matching algorithm is a one-pass Õ(k2)-space streaming algorithm for the parameterized Vertex Cover problem that in time Õ(2k) extracts a solution for the final instance with probability 1 – δ/no(1), where δ < 1. To the best of our knowledge, this is the first graph streaming algorithm that combines linear sketching with sequential operations that depend on the graph at the current time. In the dynamic model without any promise, there is a one-pass randomized algorithm for the parameterized Vertex Cover problem which computes a sketch using Õ(nk) space such that in time Õ(nk + 2k) it can either extract a solution of size at most k for the final instance, or report that no such solution exists.

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that with high probability estimates the size of a maximum matching within a constant factor using space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model (as opposed to the random-order streaming model) in o(n) space. We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We further reduce the required memory size to for three restricted settings: (i) when the input graph is a forest; (ii) when we have 2-passes and the input graph has bounded arboricity; and (iii) when the edges arrive in random order and the input graph has bounded arboricity. Finally, we design a reduction from the Boolean Hidden Matching Problem to show that there is no randomized streaming algorithm that estimates the size of the maximum matching to within a factor better than 3/2 and uses only o(n1/2) bits of space. Using the same reduction, we show that there is no deterministic algorithm that computes this kind of estimate in o(n) bits of space. The lower bounds hold even for graphs that are collections of paths of constant length.

Very recently at SODA'15 [2], we studied maximal matching via the framework of parameterized streaming, where we sought solutions under the promise that no maximal matching exceeds k in size. In this paper, we revisit this problem and provide a much simpler algorithm for this problem. We are also able to apply the same technique to the Point Line Cover problem [3].

Given a graphGand an integerk, theFeedback Vertex Set(FVS) problem asks if there is a vertex setTof size at mostkthat hits all cycles in the graph. The first fixed-parameter algorithm for FVS in undirected graphs appeared in a monograph of Mehlhorn in 1984. The fixed-parameter tractability (FPT) status of FVS in directed graphs was a long-standing open problem until Chen et al. (STOC ’08, JACM ’08) showed that it is fixed-parameter tractable by giving a 4kk! ·nO(1)time algorithm. There are two subset versions of this problems: We are given an additional subsetSof vertices (resp., edges), and we want to hit all cycles passing through a vertex ofS(resp., an edge ofS); the two variants are known to be equivalent in the parameterized sense. Recently, theSubsetFVS problem in undirected graphs was shown to be FPT by Cygan et al. (ICALP’11, SIDMA’13) and independently by Kakimura et al. (SODA ’12). We generalize the result of Chen et al. (STOC ’08, JACM ’08) by showing that aSubsetFVS in directed graphs can be solved in time 2O(k3)ċnO(1)(i.e., FPT parameterized by sizekof the solution). By our result, we complete the picture for FVS problems and their subset versions in undirected and directed graphs. The technique of random sampling of important separators was used by Marx and Razgon (STOC ’11, SICOMP ’14) to show thatUndirected Multicutis FPT, and it was generalized by Chitnis et al. (SODA ’12, SICOMP ’13) to directed graphs to show thatDirected Multiway Cutis FPT. In addition to proving the FPT of aDirected SubsetFVS, we reformulate the random sampling of important separators technique in an abstract way that can be used with a general family of transversal problems. We believe this general approach will be useful for showing the FPT of other problems in directed graphs. Moreover, we modify the probability distribution used in the technique to achieve better running time; in particular, this gives an improvement from 22O(k)to 2O(k2)in the parameter dependence of theDirected Multiway Cutalgorithm of Chitnis et al. (SODA ’12, SICOMP ’13).

The use of game theory to model conflict has been studied by several researchers, spearheaded by Schelling. Most of these efforts assume a single payoff matrix that captures players’ utilities under different assumptions about what the players will do. Our experience in counterterrorism applications is that experts disagree on these payoffs. We leverage Shapley’s notion of vector equilibria, which formulates games where there are multiple payoff matrices, but note that they are very hard to compute in practice. To effectively enumerate large numbers of equilibria with payoffs provided by multiple experts, we propose a novel combination of vector payoffs and well-supported ϵ-approximate equilibria. We develop bounds related to computation of these equilibria for some special cases and give a quasipolynomial time approximation scheme (QPTAS) for the general case when the number of players is small (which is true in many real-world applications). Leveraging this QPTAS, we give efficient algorithms to find such equilibria and experimental results showing that they work well on simulated data. We then built a policy recommendation engine based on vector equilibria, called PREVE . We use PREVE to model the terrorist group Lashkar-e-Taiba (LeT), responsible for the 2008 Mumbai attacks, as a five-player game. Specifically, we apply it to three payoff matrices provided by experts in India--Pakistan relations, analyze the equilibria generated by PREVE, and suggest counterterrorism policies that may reduce attacks by LeT. We briefly discuss these results and identify their strengths and weaknesses from a policy point of view.

In social networks, opinions and behaviors tend to spread quickly. When an idea seeks to gain attention, success requires both attracting individual users and a careful understanding of cascading behavior -- an idea that attracts a small set of highly influential individuals can easily overwhelm an idea with a much larger, but less influential, support base. Understanding exactly how the choices of individuals propagate through a network, however, poses significant challenges. In this work, we consider a model recently studied by Chierichetti, Kleinberg, and Panconesi (EC 2012) to model cascading behavior when members of a social network must each choose one of two opposing ideas. The model captures the struggle between a desire to follow personal preferences and to match the choices of those you interact with.

Given a vertex-weighted directed graph G = (V, E) and a set T = {t1, t2, … tk} of k terminals, the objective of the Strongly Connected Steiner Subgraph (SCSS) problem is to find a vertex set H ⊆ V of minimum weight such that G[H] contains a ti → tj path for each i = j. The problem is NP-hard, but Feldman and Ruhl (FOCS '99; SICOMP '06) gave a novel nO(k) algorithm for the SCSS problem, where n is the number of vertices in the graph and k is the number of terminals. We explore how much easier the problem becomes on planar directed graphs. Our main algorithmic result is a algorithm for planar SCSS, which is an improvement of a factor of in the exponent over the algorithm of Feldman and Ruhl. Our main hardness result is a matching lower bound for our algorithm: we show that planar SCSS does not have an algorithm for any computable function f, unless the Exponential Time Hypothesis (ETH) fails. The algorithm eventually relies on the excluded grid theorem for planar graphs, but we stress that it is not simply a straightforward application of treewidth-based techniques: we need several layers of abstraction to arrive to a problem formulation where the speedup due to planarity can be exploited. To obtain the lower bound matching the algorithm, we need a delicate construction of gadgets arranged in a grid-like fashion to tightly control the number of terminals in the created instance. The following additional results put our upper and lower bounds in context: Our algorithm for planar directed graphs can be generalized to graphs excluding a fixed minor. In general graphs, we cannot hope for such a dramatic improvement over the nO(k) algorithm of Feldman and Ruhl: assuming ETH, SCSS in general graphs does not have an f(k) · no(k/logk) algorithm for any computable function f. Feldman and Ruhl generalized their nO(k) algorithm to the more general Directed Steiner Forest (DSF) problem; here the task is to find a subgraph of minimum weight such that for every source si there is a path to the corresponding terminal ti. We show that that, assuming ETH, there is no f(k) · no(k) time algorithm for DSF on acyclic planar graphs.

In this paper, we consider the fault-tolerant k-median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of classical k-median problem, each client j needs to be assigned to at least rj ≥ 1 distinct open facilities. The service cost of j is the sum of its distances to the rj facilities, and the k-median constraint restricts the number of open facilities to at most k. Previously, a constant factor was known only for the special case when all rjs are the same, and a logarithmic approximation ratio was known for the general case. In addition, we present the first polynomial time algorithm for the fault-tolerant k-median problem on a path or a HST by showing that the corresponding LP always has an integral optimal solution. We also consider the fault-tolerant facility location problem, where the service cost of j can be a weighted sum of its distance to the rj facilities. We give a simple constant factor approximation algorithm, generalizing several previous results which only work for nonincreasing weight vectors.

One of the important optimization questions in highly parallel systems is the problem of assigning computational resources to communicating tasks. While scheduling tasks/operators, tasks assigned to nearby resources (e.g. on the same CPU core) have low communication costs, whereas tasks assigned to distant resources (e.g. on different server racks) have high communication costs. An optimal solution of task to resource assignment minimizes the communication cost of the task ensemble while satisfying the load balancing requirements. We model such an optimization question of minimizing communication cost as a new class of graph partitioning problems called hierarchical graph partitioning.

We study the power of fractional allocations of resources to maximize our influence in a network. This work extends in a natural way the well-studied model by Kleinberg, Kempe, and Tardos (2003), where a designer selects a (small) seed set of nodes in a social network to influence directly, this influence cascades when other nodes reach certain thresholds of neighbor influence, and the goal is to maximize the final number of influenced nodes. Despite extensive study from both practical and theoretical viewpoints, this model limits the designer to a binary choice for each node, with no chance to apply intermediate levels of influence. This model captures some settings precisely, such as exposure to an idea or pathogen, but it fails to capture very relevant concerns in others, for example, a manufacturer promoting a new product by distributing five "20% off" coupons instead of giving away a single free product.

We prove a previously stated but incorrectly proved theorem: there is a diameter-3 graph in which replacing any edge $\{v, w\}$ of the graph with $\{v, w'\}$, for any vertex $w'$, does not decrease the total sum of distances from $v$ to all other nodes (a property called sum equilibrium).

We improve the approximation ratios for two optimization problems in planar graphs. For node-weighted Steiner tree, a classical network-optimization problem, the best achievable approximation ratio in general graphs is Θ (log n ), and nothing better was previously known for planar graphs. We give a constant-factor approximation for planar graphs. Our algorithm generalizes to allow as input any nontrivial minor-closed graph family, and also generalizes to address other optimization problems such as Steiner forest, prize-collecting Steiner tree, and network-formation games. The second problem we address is group Steiner tree: given a graph with edge weights and a collection of groups (subsets of nodes), find a minimum-weight connected subgraph that includes at least one node from each group. The best approximation ratio known in general graphs is O (log 3 n ), or O (log 2 n ) when the host graph is a tree. We obtain an O (log n polyloglog n ) approximation algorithm for the special case where the graph is planar embedded and each group is the set of nodes on a face. We obtain the same approximation ratio for the minimum-weight tour that must visit each group.

We study an extensive class of movement minimization problems that arise from many practical scenarios but so far have little theoretical study. In general, these problems involve planning the coordinated motion of a collection of agents (representing robots, people, map labels, network messages, etc.) to achieve a global property in the network while minimizing the maximum or average movement (expended energy). The only previous theoretical results about this class of problems are about approximation and are mainly negative: many movement problems of interest have polynomial inapproximability. Given that the number of mobile agents is typically much smaller than the complexity of the environment, we turn to fixed-parameter tractability. We characterize the boundary between tractable and intractable movement problems in a very general setup: it turns out the complexity of the problem fundamentally depends on the treewidth of the minimal configurations. Thus, the complexity of a particular problem can be determined by answering a purely combinatorial question. Using our general tools, we determine the complexity of several concrete problems and fortunately show that many movement problems of interest can be solved efficiently.

We consider the problem of dealing with the terrorist group Lashkar-e-Taiba (LeT), responsible for the 2008 Mumbai attacks, as a five-player game. However, as different experts vary in their assessment of players' payoffs in this game (and other games), we identify multi-payoff equilibria through a novel combination of vector payoffs and well-supported ∈-approximate equilibria. We develop a grid search algorithm for computing such equilibria, and provide experimental validation using three payoff matrices filled in by experts in India-Pakistan relations. The resulting system, called PREVE, allows us to analyze the equilibria thus generated and suggest policies to reduce attacks by LeT. We briefly discuss the suggested policies and identify their strengths and weaknesses.

We give the first polynomial-time online algorithm for the node-weighted Steiner forest problem with a poly-logarithmic competitive ratio. The competitive ratio of our algorithm is optimal up to a logarithmic factor. For the special case of graphs with an excluded fixed minor (e.g., planar graphs), we obtain a logarithmic competitive ratio, which is optimal up to a constant, using a different online algorithm. Both these results are obtained as special cases of generic results for a large class of problems that can be encoded as online 0, 1-proper functions. Our results are obtained by using a new framework for online network design problems that we call disk paintings. The central idea in this technique is to amortize the cost of primal updates to a set of carefully selected mutually disjoint fixed-radius dual disks centered at a subset of terminals. We hope that this framework will be useful for other online network design problems.

The emergence of new capabilities such as virtualization and elastic (private or public) cloud computing infrastructures has made it possible to deploy multiple applications, on demand, on the same cloud infrastructure. A major challenge to achieve this possibility, however, is that modern applications are typically distributed, structured systems that include not only computational and storage entities, but also policy entities (e.g., load balancers, firewalls, intrusion prevention boxes). Deploying applications on a cloud infrastructure without the policy entities may introduce substantial policy violations and/or security holes. In this paper, we present PACE: the first systematic framework for Policy-Aware Application Cloud Embedding. We precisely define the policy-aware, cloud application embedding problem, study its complexity and introduce simple, efficient, online primal-dual algorithms to embed applications in cloud data centers. We conduct evaluations using data from a real, large campus network and a realistic data center topology to evaluate the feasibility and performance of PACE. We show that deployment in a cloud without considering in-network policies may lead to a large number of policy violations (e.g., using tree routing as a way to enforce in-network policies may observe up to 91% policy violations). We also show that our embedding algorithms are very efficient by comparing with a good online fractional embedding algorithm.

In this paper we propose a game-theoretic model to analyze events similar to the 2009 DARPA Network Challenge, which was organized by the Defense Advanced Research Projects Agency (DARPA) for exploring the roles that the Internet and social networks play in incentivizing wide-area collaborations. The challenge was to form a group that would be the first to find the locations of ten moored weather balloons across the United States. We consider a model in which N people (who can form groups) are located in some topology with a fixed coverage volume around each person's geographical location. We consider various topologies where the players can be located such as the Euclidean d-dimension space and the vertices of a graph. A balloon is placed in the space and a group wins if it is the first one to report the location of the balloon. A larger team has a higher probability of finding the balloon, but we assume that the prize money is divided equally among the team members. Hence there is a competing tension to keep teams as small as possible.

Given a directed graph $G$, a set of $k$ terminals, and an integer $p$, the Directed Vertex Multiway Cut problem asks whether there is a set $S$ of at most $p$ (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge Multiway Cut is the analogous problem where $S$ is a set of at most $p$ edges. These two problems are indeed known to be equivalent. A natural generalization of the multiway cut is the Multicut problem, in which we want to disconnect only a set of $k$ given pairs instead of all pairs. Marx [Theoret. Comput. Sci., 351 (2006), pp. 394--406] showed that in undirected graphs Vertex/Edge Multiway cut is fixed-parameter tractable (FPT) parameterized by $p$. Marx and Razgon [Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011, pp. 469--478] showed that undirected Multicut is FPT and Directed Multicut is W[1]-hard parameterized by $p$. We complete the picture here by our main result, which is that both Directed Vertex Multiway Cut and Directed Edge Multiway Cut can be solved in time $2^{2^{O(p)}}n^{O(1)}$, i.e., FPT parameterized by size $p$ of the cutset of the solution. This answers an open question raised by the aforementioned papers. It follows from our result that Directed Edge/Vertex Multicut is FPT for the case of $k=2$ terminal pairs, which answers another open problem raised by Marx and Razgon.

We study a natural network creation game, in which each node locally tries to minimize its local diameter or its local average distance to other nodes by swapping one incident edge at a time. The central question is what structure the resulting equilibrium graphs have, in particular, how well they globally minimize diameter. For the local-average-distance version, we prove an upper bound of $2^{O(\sqrt{\lg n})}$, a lower bound of 3, and a tight bound of exactly 2 for trees, and give evidence of a general polylogarithmic upper bound. For the local-diameter version, we prove a lower bound of $\Omega(\sqrt{n})$ and a tight upper bound of 3 for trees. The same bounds apply, up to constant factors, to the price of anarchy. Our network creation games are closely related to the previously studied unilateral network creation game. The main difference is that our model has no parameter $\alpha$ for the link creation cost, so our results effectively apply for all values of $\alpha$ without additional effort; furthermore, equilibrium can be checked in polynomial time in our model, unlike in previous models. Our perspective enables simpler proofs that get at the heart of network creation games.

Online auction is the essence of many modern markets, particularly networked markets, in which information about goods, agents, and outcomes is revealed over a period of time, and the agents must make irrevocable decisions without knowing future information. Optimal stopping theory, especially the classic secretary problem , is a powerful tool for analyzing such online scenarios which generally require optimizing an objective function over the input. The secretary problem and its generalization the multiple-choice secretary problem were under a thorough study in the literature. In this article, we consider a very general setting of the latter problem called the submodular secretary problem , in which the goal is to select k secretaries so as to maximize the expectation of a (not necessarily monotone) submodular function which defines efficiency of the selected secretarial group based on their overlapping skills. We present the first constant-competitive algorithm for this case. In a more general setting in which selected secretaries should form an independent (feasible) set in each of l given matroids as well, we obtain an O ( l log 2 r )-competitive algorithm generalizing several previous results, where r is the maximum rank of the matroids. Another generalization is to consider l knapsack constraints (i.e., a knapsack constraint assigns a nonnegative cost to each secretary, and requires that the total cost of all the secretaries employed be no more than a budget value) instead of the matroid constraints, for which we present an O ( l )-competitive algorithm. In a sharp contrast, we show for a more general setting of subadditive secretary problem , there is no õ (√ n )-competitive algorithm and thus submodular functions are the most general functions to consider for constant-competitiveness in our setting. We complement this result by giving a matching O (√ n )-competitive algorithm for the subadditive case. At the end, we consider some special cases of our general setting as well.

We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. With our framework: (1) We obtain the first FPT algorithm for the parameterized version of the UNIQUE LABEL COVER problem, with single exponential dependency on the size of the cutset and the size of the alphabet. As a consequence, we extend the set of the polynomial time solvable instances of UNIQUE GAMES to those with at most O(√{log n}) violated constraints. (2) We obtain a new FPT algorithm for the STEINER CUT problem with exponential speed-up over the recent work of Kawarabayashi and Thorup (FOCS'11). (3) We show how to combine considering 'cut' and 'uncut' constraints at the same time. We define a robust problem NODE MULTIWAY CUT-UNCUT that can serve as an abstraction of introducing uncut constraints, and show that it admits an FPT algorithm with single exponential dependency on the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan and Razgon (STACS'10), which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle real weights, to the best of our knowledge, the technique of important separators does not work in the weighted version.

In this paper we consider a generalization of the classical k-center problem with capacities. Our goal is to select k centers in a graph, and assign each node to a nearby center, so that we respect the capacity constraints on centers. The objective is to minimize the maximum distance a node has to travel to get to its assigned center. This problem is NP-hard, even when centers have no capacity restrictions and optimal factor 2 approximation algorithms are known. With capacities, when all centers have identical capacities, a 6 approximation is known with no better lower bounds than for the infinite capacity version. While many generalizations and variations of this problem have been studied extensively, no progress was made on the capacitated version for a general capacity function. We develop the first constant factor approximation algorithm for this problem. Our algorithm uses an LP rounding approach to solve this problem, and works for the case of non-uniform hard capacities, when multiple copies of a node may not be chosen and can be extended to the case when there is a hard bound on the number of copies of a node that may be selected. Finally, for non-uniform soft capacities we present a much simpler 11-approximation algorithm, which we find as one more evidence that hard capacities are much harder to deal with.

We study the problem of scalable monitoring of operational 3G wireless networks. Threshold-based performance monitoring in large 3G networks is very challenging for two main factors: large network scale and dynamics in both time and spatial domains. A fine-grained threshold setting (e.g., perlocation hourly) incurs prohibitively high management complexity, while a single static threshold fails to capture the network dynamics, thus resulting in unacceptably poor alarm quality (up to 70% false/miss alarm rates). In this paper, we propose a scalable monitoring solution, called threshold-compression that can characterize the location- and time-specific threshold trend of each individual network element (NE) with minimal threshold setting. The main insight is to identify groups of NEs with similar threshold behaviors across location and time dimensions, forming spatial-temporal clusters to reduce the number of thresholds while maintaining acceptable alarm accuracy in a large-scale 3G network. Our evaluations based on the operational experience on a commercial 3G network have demonstrated the effectiveness of the proposed solution. We are able to reduce the threshold setting up to 90% with less than 10% false/miss alarms.

We study the problem of online prophet-inequality matching in bipartite graphs. There is a static set of bidders and an online stream of items. We represent the interest of bidders in items by a weighted bipartite graph. Each bidder has a capacity, i.e., an upper bound on the number of items that can be allocated to her. The weight of a matching is the total weight of edges matched to the bidders. Upon the arrival of an item, the online algorithm should either allocate it to a bidder or discard it. The objective is to maximize the weight of the resulting matching. We consider this model in a stochastic setting where we know the distribution of the incoming items in advance. Furthermore, we allow the items to be drawn from different distributions, i.e., we may assume that the tth item is drawn from distribution Dt. In contrast to i.i.d. model, this allows us to model the change in the distribution of items throughout the time. We call this setting the Prophet-Inequality Matching because of the possibility of having a different distribution for each time. We generalize the classic prophet inequality by presenting an algorithm with the approximation ratio of 1--1/√k+3 where k is the minimum capacity. In case of k=2, the algorithm gives a tight ratio of 1/2 which is a different proof of the prophet inequality.

Given an undirected graph with edge lengths and a subset of nodes (called the terminals), the multiway cut (also called the multi-terminal cut) problem asks for a subset of edges, with minimum total length, whose removal disconnects each terminal from all others. The problem generalizes minimum s-t cut, but is NP-hard for planar graphs and APX-hard for general graphs [11]. In this paper, we present a PTAS for multiway cut on planar graphs.

Given a directed graph G, a set of k terminals and an integer p, the Directed Vertex Multiway Cut problem asks if there is a set S of at most p (nonterminal) vertices whose removal disconnects each terminal from all other terminals. Directed Edge Multiway Cut is the analogous problem where S is a set of at most p edges. These two problems indeed are known to be equivalent. A natural generalization of the multiway cut is the multicut problem, in which we want to disconnect only a set of k given pairs instead of all pairs. Marx (Theor. Comp. Sci. 2006) showed that in undirected graphs multiway cut is fixed-parameter tractable (FPT) parameterized by p. Marx and Razgon (STOC 2011) showed that undirected multicut is FPT and directed multicut is W[1]-hard parameterized by p. We complete the picture here by our main result which is that both Directed Vertex Multiway Cut and Directed Edge Multiway Cut can be solved in time 22O(p) nO(1), i.e., FPT parameterized by size p of the cutset of the solution. This answers an open question raised by Marx (Theor. Comp. Sci. 2006) and Marx and Razgon (STOC 2011). It follows from our result that Directed Multicut is FPT for the case of k = 2 terminal pairs, which answers another open problem raised in Marx and Razgon (STOC 2011).

In a Content Distribution Network (CDN) , there are m servers storing the data; each of them has a specific bandwidth. All the requests from a particular client should be assigned to one server because of the routing protocol used. The goal is to minimize the total cost of these assignments—cost of each is proportional to the distance between the client and the server as well as the request size—while the load on each server is kept below its bandwidth limit. When each server also has a setup cost, this is an unsplittable hard-capacitated facility location problem . As much attention as facility location problems have received, there has been no nontrivial approximation algorithm when we have hard capacities (i.e., there can only be one copy of each facility whose capacity cannot be violated) and demands are unsplittable (i.e., all the demand from a client has to be assigned to a single facility). We observe it is NP-hard to approximate the cost to within any bounded factor in this case. Thus, for an arbitrary constant ϵ>0, we relax the capacities to a 1+ϵ factor. For the case where capacities are almost uniform , we give a bicriteria O (log n , 1+ϵ)-approximation algorithm for general metrics and a (1+ϵ, 1+ϵ)-approximation algorithm for tree metrics. A bicriteria (α,β)-approximation algorithm produces a solution of cost at most α times the optimum, while violating the capacities by no more than a β factor. We can get the same guarantees for nonuniform capacities if we allow quasipolynomial running time. In our algorithm, some clients guess the facility they are assigned to, and facilities decide the size of the clients they serve. A straightforward approach results in exponential running time. When costs do not satisfy metricity, we show that a 1.5 violation of capacities is necessary to obtain any approximation. It is worth noting that our results generalize bin packing (zero connection costs and facility costs equal to one), knapsack (single facility with all costs being zero), minimum makespan scheduling for related machines (all connection costs being zero), and some facility location problems.

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 of selfish node players, each creating some incident links, and the goal is to minimize α times the cost of the created links plus sum of the distances to all other players. Fabrikant et al. proved an upper bound O (√α) on the price of anarchy: the relative cost of the lack of coordination. Albers, Eilts, Even-Dar, Mansour, and Roditty show that the price of anarchy is constant for α = O (√ n ) and for α ≥ 12 n ⌈ lg n ⌉, and that the price of anarchy is 15(1+(min{α 2 / n , n 2 /α}) 1/3 ) for any α. The latter bound shows the first sublinear worst-case bound, O ( n 1/3 ), for all α. But no better bound is known for α between ω(√ n ) and o ( n lg n ). Yet α ≈ n is perhaps the most interesting range, for it corresponds to considering the average distance (instead of the sum of distances) to other nodes to be roughly on par with link creation (effectively dividing α by n ). In this article, we prove the first o ( n ε ) upper bound for general α, namely 2 O (√ lg n ) . We also prove a constant upper bound for α = O ( n 1-ε ) for any fixed ε > 0, substantially reducing the range of α for which constant bounds have not been obtained. Along the way, we also improve the constant upper bound by Albers et al. (with the lead constant of 15 ) to 6 for α < ( n /2) 1/2 and to 4 for α < ( n /2) 1/3 . Next we consider the bilateral network variant of Corbo and Parkes, in which links can be created only with the consent of both endpoints and the link price is shared equally by the two. Corbo and Parkes show an upper bound of O (√α) and a lower bound of Ω(lgα) for α ≤ n . In this article, we show that in fact the upper bound O (√α) is tight for α ≤ n , by proving a matching lower bound of Ω(√α). For α > n , we prove that the price of anarchy is Θ( n /√ α). Finally we introduce a variant of both network creation games, in which each player desires to minimize α times the cost of its created links plus the maximum distance (instead of the sum of distances) to the other players. This variant of the problem is naturally motivated by considering the worst case instead of the average case. Interestingly, for the original (unilateral) game, we show that the price of anarchy is at most 2 for α ≥ n , O (min {4 √lg n , ( n /α) 1/3 }) for 2√ lg n ≤ α ≤ n , and O ( n 2/α ) for α < 2√ lg n . For the bilateral game, we prove matching upper and lower bounds of Θ( n /α + 1) for α ≤ n , and an upper bound of 2 for α > n .

In the Steiner Network problem, we are given a graph G with edge-costs and connectivity requirements r uv between node pairs u,v . The goal is to find a minimum-cost subgraph H of G that contains r uv edge-disjoint paths for all u,v ∈ V . In Prize-Collecting Steiner Network problems, we do not need to satisfy all requirements, but are given a penalty function for violating the connectivity requirements, and the goal is to find a subgraph H that minimizes the cost plus the penalty. The case when r uv ∈ {0,1} is the classic Prize-Collecting Steiner Forest problem. In this article, we present a novel linear programming relaxation for the Prize-Collecting Steiner Network problem, and by rounding it, obtain the first constant-factor approximation algorithm for submodular and monotone nondecreasing penalty functions. In particular, our setting includes all-or-nothing penalty functions, which charge the penalty even if the connectivity requirement is slightly violated; this resolves an open question posed by Nagarajan et al. [2008]. We further generalize our results for element-connectivity and node-connectivity.

Coalition formation is a key topic in multi-agent systems. Coalitions enable agents to achieve goals that they may nothave been able to achieve on their own. Previous work hasshown problems in coalition games to be computationally hard. Wooldridge and Dunne (Artifi. Intell. 2006) studied the classical computational complexity of several natural decision problems in Coalitional Resource Games (CRG) - games in which each agent is endowed with a set of resources and coalitions can bring about a set of goals if they are collectively endowed with the necessary amount of resources. The input of coalitional resource games bundles together several elements, e.g., the agent set Ag, the goal set G, the resource set R, etc. Shrot et al. (AAMAS 2009) examine coalition formation problems in the CRG model using the theory of Parameterized Complexity. Their refined analysis shows that not all parts of input act equal - some instances of the problem are indeed tractable while others still remain intractable.We answer an important question left open by Shrot, Aumann,and Kraus by showing that the SC Problem (checking whether a Coalition is Successful) is W[1]-hard when parameterized by the size of the coalition. Then via a single theme of reduction from SC, we are able to show that various problems related to resources, resource bounds, and resource conflicts introduced by Wooldridge et al. are (i) W[1]-hard or co-W[1]-hard w.r.t the size of the coalition; and (ii) Para-NP hard or co-Para-NP-hard w.r.t |R|. When parameterized by |G| or |R| + |Ag|, we give a general algorithm which proves that these problems are indeed tractable.

This paper is a theoretical and experimental study of two related facility location problems that emanated from networking. Suppose we are given a network modeled as a directed graph G = (V, A), together with (not-necessarily-disjoint) subsets C and F of V, where C is a set of customer locations and F is a set of potential facility locations (and typically C ⊆ F). Our goal is to find a minimum sized subset F′ ⊆ F such that for every customer c ∊ C there are two locations f1, f2 ∊ F′ such that traffic from c to f1 and to f2 is routed on disjoint paths (usually shortest paths) under the network's routing protocols. Although we prove that this problem is impossible to approximate in the worst case even to within a factor of 2log1−εn for any ε > 0 (assuming no NP-complete language can be solved in quasipolynomial time), we show that the situation is much better in practice. We propose three algorithms that build solutions and determine lower bounds on the optimum solution, and evaluate them on several large real ISP topologies and on synthetic networks designed to reflect real-world LAN/WAN network structure. Our main algorithms are (1) an algorithm that performs multiple runs of a straightforward randomized greedy heuristic and returns the best result found, (2) a genetic algorithm that uses the greedy algorithm as a subroutine, and (3) a new “Double Hitting Set” algorithm. All three approaches perform surprising well, although, in practice, the most cost-effective approach is the multi-run greedy algorithm. This yields results that average within 0.7% of optimal for our synthetic instances and within 2.9% for our real-world instances, excluding the largest (and most realistic) one. For the latter instance, the other two algorithms come into their own, finding solutions that are more than three times better than those of the multi-start greedy approach. In terms of our motivating monitoring application, where every customer location can be a facility location, the results are even better. Here the above Double Hitting Set solution is 90% better than the default solution which places a monitor at each customer location - such comparisons help justify the proposed alternative monitoring scheme of [8]. Our results also show that, on average for our real-world instances, we could save an additional 18% by choosing the (shortest path) routes ourselves, rather than taking the simpler approach of relying on the network to choose them for us.

As wireless service providers move from flat-fee unlimited data plans to tiered usage-based ones, there has been little published research on how such tiered plans should be designed. In this paper, we tackle this problem from an algorithmic perspective: formulating the problem of tiered data pricing plans for a wireless provider, and proposing an efficient algorithmic framework to compute the plans. Our algorithmic framework can be applied to the usage and cost data of any provider to obtain the pricing functions specific to that provider.

Threshold-based performance monitoring in large 3G networks is very challenging for two main factors: large network scale and dynamics in both time and spatial domains. There exists a fundamental tradeoff between the size of threshold settings and the alarm quality. In this paper, we propose a scalable monitoring solution, called threshold-compression that characterizes the tradeoff via intelligent threshold aggregation. The main insight behind our solution is to identify groups of network elements with similar threshold behaviors across location and time dimensions, thus forming spatial-temporal clusters and generating the associated compressed thresholds within the optimization framework. Our evaluations on a commercial 3G network have demonstrated the effectiveness of our threshold-compression solution, e.g., threshold setting reduction up to 90% within 10% false/miss alarms.

We introduce Capacitated Metric Labeling. As in Metric Labeling, we are given a weighted graph G = (V, E), a label set L, a semimetric dL on this label set, and an assignment cost function ϕ : V × L → ℜ+. The goal in Metric Labeling is to find an assignment f : V → L that minimizes a particular two-cost function. Here we add the additional restriction that each label ti receive at most li nodes, and we refer to this problem as Capacitated Metric Labeling. Allowing the problem to specify capacities on each label allows the problem to more faithfully represent the classification problems that Metric Labeling is intended to model. Our main positive result is a polynomial-time, O(log |V|)-approximation algorithm when the number of labels is fixed, which is the most natural parameter range for classification problems. We also prove that it is impossible to approximate the value of an instance of Capacitated Metric Labeling to within any finite factor, if P ≠ NP. Yet this does not address the more interesting question of how hard Capacitated Metric Labeling is to approximate when we are allowed to violate capacities. To study this question, we introduce the notion of the “congestion” of an instance of Capacitated Metric Labeling. We prove that (under certain complexity assumptions) there is no polynomial-time approximation algorithm that can approximate the congestion to within O((log|L|)1/2–ε) (for any ε > 0) and this implies as a corollary that any polynomial-time approximation algorithm that achieves a finite approximation ratio must multiplicatively violate the label capacities by Ω((log |L|)1/2–ε). We also give a O(log |L|)-approximation algorithm for congestion.

In this paper, we reduce Prize-Collecting Steiner TSP (PCTSP), Prize-Collecting Stroll (PCS), Prize-Collecting Steiner Tree (PCST), Prize-Collecting Steiner Forest (PCSF), and more generally Submodular Prize-Collecting Steiner Forest (SPCSF), on planar graphs (and also on bounded-genus graphs) to the corresponding problem on graphs of bounded treewidth. More precisely, for each of the mentioned problems, an α-approximation algorithm for the problem on graphs of bounded treewidth implies an (α + ε)-approximation algorithm for the problem on planar graphs (and also bounded-genus graphs), for any constant ε > 0. PCS, PCTSP, and PCST can be solved exactly on graphs of bounded treewidth and hence we obtain a PTAS for these problems on planar graphs and bounded-genus graphs. In contrast, we show that PCSF is APX-hard to approximate on series-parallel graphs, which are planar graphs of treewidth at most 2. Apart from ruling out a PTAS for PCSF on planar graphs and bounded treewidth graphs, this result is also interesting since it gives the first provable hardness separation between the approximability of a problem and its prize-collecting version. We also show that PCSF is APX-hard on Euclidean instances.

We study a very natural local protocol for a file transfer problem. Consider a scenario where several files, which may have varied sizes and get created over a period of time, are to be transferred between pairs of hosts in a distributed environment. Our protocol assumes that while executing the file transfers, an individual host does not use any global knowledge; and simply subdivides its I/O resources equally among all the active file transfers at that host at any point in time. This protocol is motivated by its simplicity of use and its applications to scheduling map-reduce workloads.

We prove that any graph excluding a fixed minor can have its edges partitioned into a desired number k of color classes such that contracting the edges in any one color class results in a graph of treewidth linear in k. This result is a natural finale to research in contraction decomposition, generalizing previous such decompositions for planar and bounded-genus graphs, and solving the main open problem in this area (posed at SODA 2007). Our decomposition can be computed in polynomial time, resulting in a general framework for approximation algorithms, particularly PTASs (with k ∼ 1/ε), and fixed-parameter algorithms, for problems closed under contractions in graphs excluding a fixed minor. For example, our approximation framework gives the first PTAS for TSP in weighted H-minor-free graphs, solving a decade-old open problem of Grohe; and gives another fixed-parameter algorithm for k-cut in H-minor-free graphs, which was an open problem of Downey et al. even for planar graphs.

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded-treewidth graphs needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded-treewidth graphs, planar graphs, and bounded-genus graphs.

We study the prize-collecting Steiner tree (PCST), prize-collecting traveling salesman (PCTSP), and prize-collecting path (PC-Path) problems. Given a graph $(V,E)$ with a cost on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or path (for PC-Path) that minimizes the sum of the edge costs in the tree/cycle/path and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, a 2-approximation algorithm for each, appeared first in 1992; a 2-approximation for PC-Path appeared in 2003. The natural linear programming relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present $(2-\epsilon)$-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier. Specifically, our approximation ratio for prize-collecting Steiner tree is below 1.9672.

We prove two structural decomposition theorems about graphs excluding a fixed odd minor H, and show how these theorems can be used to obtain approximation algorithms for several algorithmic problems in such graphs. Our decomposition results provide new structural insights into odd-H-minor-free graphs, on the one hand generalizing the central structural result from Graph Minor Theory, and on the other hand providing an algorithmic decomposition into two bounded-treewidth graphs, generalizing a similar result for minors. As one example of how these structural results conquer difficult problems, we obtain a polynomial-time 2-approximation for vertex coloring in odd-H-minor-free graphs, improving on the previous O(|V(H)|)-approximation for such graphs and generalizing the previous 2-approximation for H-minor-free graphs. The class of odd-H-minor-free graphs is a vast generalization of the well-studied H-minor-free graph families and includes, for example, all bipartite graphs plus a bounded number of apices. Odd-H-minor-free graphs are particularly interesting from a structural graph theory perspective because they break away from the sparsity of H-minor-free graphs, permitting a quadratic number of edges.

We study a natural network creation game, in which each node locally tries to minimize its local diameter or its local average distance to other nodes, by swapping one incident edge at a time. The central question is what structure the resulting equilibrium graphs have, in particular, how well they globally minimize diameter. For the local-average-distance version, we prove an upper bound of 2O(√ lg n), a lower bound of 3, a tight bound of exactly 2 for trees, and give evidence of a general polylogarithmic upper bound. For the local-diameter version, we prove a lower bound of Ω(√ n), and a tight upper bound of 3 for trees. All of our upper bounds apply equally well to previously extensively studied network creation games, both in terms of the diameter metric described above and the previously studied price of anarchy (which are related by constant factors). In surprising contrast, our model has no parameter α for the link creation cost, so our results automatically apply for all values of alpha without additional effort; furthermore, equilibrium can be checked in polynomial time in our model, unlike previous models. Our perspective enables simpler and more general proofs that get at the heart of network creation games.

We give the first polynomial-time approximation scheme (PTAS) for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. As a first step, we show how to build a Steiner forest spanner for such graphs. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle; moreover, the terminals in different subinstances are far from each other. Each subinstance has a relatively inexpensive Steiner tree connecting all its terminals, and the subinstances can be solved (almost) separately. Another building block is a PTAS for Steiner forest on graphs of bounded treewidth. Surprisingly, Steiner forest is NP-hard even on graphs of treewidth 3. Therefore, our PTAS for bounded treewidth graphs needs a nontrivial combination of approximation arguments and dynamic programming on the tree decomposition. We further show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a novel combination of dynamic programming and minimum cut computations, completing our thorough complexity study of Steiner forest in the range of bounded treewidth graphs, planar graphs, and bounded genus graphs.

Buy-at-bulk network design problems arise in settings where the costs for purchasing or installing equipment exhibit economies of scale. The objective is to build a network of cheapest cost to support a given multicommodity flow demand between node pairs. We present approximation algorithms for buy-at-bulk network design problems with costs on both edges and nodes of an undirected graph. Our main result is the first poly-logarithmic approximation ratio for the non-uniform problem that allows different cost functions on each edge and node; the ratio we achieve is $O(\log^4 h)$, where h is the number of demand pairs. In addition we present an $O(\log h)$ approximation for the single sink problem. Poly-logarithmic ratios for some related problems are also obtained. Our algorithm for the multicommodity problem is obtained via a reduction to the single source problem using the notion of junction trees. We believe that this presents a simple yet useful general technique for network design problems.

The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V , with m demand pairs ⊆ V × V and a “target” k ≤ m , the goal is to find a minimum cost subgraph that connects at least k pairs. In this paper, we give an O (min{√ n ⋅log k ,√ k })-approximation algorithm for k -forest, improving on the previous best ratio of O (min { n 2/3 ,√ m }log n ) by Segev and Segev. We then apply our algsorithm for k -forest to obtain approximation algorithms for several Dial-a-Ride problems. The basic Dial-a-Ride problem is the following: given an n point metric space with m objects each with its own source and destination, and a vehicle capable of carrying at most k objects at any time, find the minimum length tour that uses this vehicle to move each object from its source to destination. We want that the tour be non-preemptive : that is, each object, once picked up at its source, is dropped only at its destination. We prove that an α-approximation algorithm for the k -forest problem implies an O (α⋅log 2 n )-approximation algorithm for Dial-a-Ride. Using our results for k -forest, we get an O (min{√ n ,√ k }⋅log 2 n )-approximation algorithm for Dial-a-Ride. The only previous result known for Dial-a-Ride was an O (√ k log n )-approximation by Charikar and Raghavachari; our results give a different proof of a similar approximation guarantee—in fact, when the vehicle capacity k is large, we give a slight improvement on their results. The reduction from Dial-a-Ride to the k -forest problem is fairly robust, and allows us to obtain approximation algorithms (with the same guarantee) for some interesting generalizations of Dial-a-Ride.

No abstract available.

Enterprise networks are increasingly adopting Layer-3 multiprotocol label switching (MPLS) virtual private network (VPN) technology to connect geographically disparate locations. The any-to-any direct connectivity model of this technology is causing routing tables in the service provider's routers to grow very large. The concept of relaying was proposed earlier to separately minimize the routing table memory footprint of individual VPNs by selecting a small number of hub routers to maintain complete reachability information for each VPN and enabling nonhub spoke routers with reduced routing tables to reach others by routing traffic via a hub. A large service provider network typically hosts thousands of different VPNs. In this paper, we generalize relaying to the multi-VPN environment and consider new constraints on resources shared across VPNs, such as router uplink bandwidth and memory. The hub selection problem involves complex tradeoffs along multiple dimensions including these shared resources and the additional distance traversed by traffic. We formulate the hub selection as a constraint optimization problem and develop an algorithm with provable guarantees to approximate this NP-complete problem. Evaluations using traces and configurations from a large provider indicate that the resulting relaying solution reduces the total router memory requirement by 85% while smoothing out the utilization on each router and requiring only a small increase in the end-to-end path for the relayed traffic.

We study the prize-collecting versions of the Steiner tree, traveling salesman, and stroll (a.k.a. Path-TSP) problems (PCST, PCTSP, and PCS, respectively): given a graph (V, E) with costs on each edge and a penalty (a.k.a. prize) on each node, the goal is to find a tree (for PCST), cycle (for PCTSP), or stroll (for PCS) that minimizes the sum of the edge costs in the tree/cycle/stroll and the penalties of the nodes not spanned by it. In addition to being a useful theoretical tool for helping to solve other optimization problems, PCST has been applied fruitfully by AT&T to the optimization of real-world telecommunications networks. The most recent improvements for the first two problems, giving a 2-approximation algorithm for each, appeared first in 1992. (A 2-approximation for PCS appeared in 2003.) The natural linear programming (LP) relaxation of PCST has an integrality gap of 2, which has been a barrier to further improvements for this problem. We present (2 · ¿)-approximation algorithms for all three problems, connected by a unified technique for improving prize-collecting algorithms that allows us to circumvent the integrality gap barrier.

Enterprise networks are increasingly adopting layer 3 multiprotocol label switching (MPLS) virtual private network (VPN) technology to connect geographically disparate locations. The any-to-any direct connectivity model of this technology involves a very high memory footprint and is causing associated routing tables in the service provider's routers to grow very large. The concept of relaying was proposed earlier [6] to separately minimize the routing table memory footprint of individual VPNs, and involves selecting a small number of hub routers to maintain complete reachability information for that VPN, and enabling non-hub spoke routers with reduced routing tables to achieve any-to-any reachability by routing traffic via a hub. A large service provider network typically hosts many thousands of different VPNs. In this paper, we generalize relaying to the multi-VPN environment, and consider new constraints on resources shared across VPNs, such as router uplink bandwidth and memory. The hub selection problem involves complex tradeoffs along multiple dimensions including these shared resources, and the additional distance traversed by traffic. We formulate the hub selection as a constraint optimization problem and develop an algorithm with provable guarantees to solve this NP-complete problem. Evaluations using traces and configurations from a large provider and many real-world VPNs indicate that the resulting Relaying solution substantially reduces the total router memory requirement by 85% while smoothing out the utilization on each router and requiring only a small increase in the end-to-end path for the relayed traffic.

In a Content Distribution Network (CDN), there are m servers storing the data; each of them has a specific bandwidth. All the requests from a particular client should be assigned to one server, because of the routing protocol used. The goal is to minimize the total cost of these assignments —cost of each is proportional to the distance as well as the request size— while the load on each server is kept below its bandwidth limit. When each server also has a setup cost, this is an unsplittable hard-capacitated facility location problem. As much attention as facility location problems have received, there has been no nontrivial approximation algorithm when we have hard capacities (i.e., there can only be one copy of each facility whose capacity cannot be violated) and demands are unsplittable (i.e., all the demand from a client has to be assigned to a single facility). We observe it is NP-hard to approximate the cost to within any bounded factor. Thus, for an arbitrary constant ∊ > 0, we relax the capacities to a 1 + ∊ factor. For the case where capacities are almost uniform, we give a bicriteria O(log n, 1 + ∊)-approximation algorithm for general metrics and a (1 + ∊, 1 + ∊)-approximation algorithm for tree metrics. A bicriteria (α, β)-approximation algorithm produces a solution of cost at most α times the optimum, while violating the capacities by no more than a β factor. We can get the same guarantee for non-uniform capacities if we allow quasipolynomial running time. In our algorithm, some clients guess the facility they are assigned to, and facilities decide the size of clients they serve. A straight-forward approach results in exponential running time. When costs do not satisfy metricity, we show that a 1.5 violation of capacities is necessary to obtain any approximation. It is worth noting that our results generalize bin packing (zero cost matrix and facility costs equal to one), knapsack (single facility with all costs being zero), minimum makespan scheduling for related machines (all costs being zero) and some facility location problems.

It is known that computing the list chromatic number is harder than computing the chromatic number (assuming NP ≠ coNP). In fact, the problem of deciding whether a given graph is f-list-colorable for a function f : V → {c − 1, c} for c ≥ 3 is -complete. In general, it is believed that approximating list coloring is hard for dense graphs. In this paper, we are interested in sparse graphs. More specifically, we deal with nontrivial minor-closed classes of graphs, i.e., graphs excluding some Kk minor. We refine the seminal structure theorem of Robertson and Seymour, and then give an additive approximation for list-coloring within k − 2 of the list chromatic number. This improves the previous multiplicative O(k)-approximation algorithm [20]. Clearly our result also yields an additive approximation algorithm for graph coloring in a minor-closed graph class. This result may give better graph colorings than the previous multiplicative 2-approximation algorithm for graph coloring in a minor-closed graph class [6]. Our structure theorem is of independent interest in the sense that it gives rise to a new insight on well-connected H-minor-free graphs. In particular, this class of graphs can be easily decomposed into two parts so that one part has bounded treewidth and the other part is a disjoint union of bounded-genus graphs. Moreover, we can control the number of edges between the two parts. The proof method itself tells us how knowledge of a local structure can be used to gain a global structure, which gives new insight on how to decompose a graph with the help of local-structure information.

We study scheduling algorithms for loading data feeds into real time data warehouses, which are used in applications such as IP network monitoring, online financial trading, and credit card fraud detection. In these applications, the warehouse collects a large number of streaming data feeds that are generated by external sources and arrive asynchronously. Data for each table are generated at a constant rate, different tables possibly at different rates. For each data feed, the arrival of new data triggers an update that seeks to append the new data to the corresponding table; if multiple updates are pending for the same table, they are batched together before being loaded. At time τ, if a table has been updated with information up to time r≤τ, its staleness is defined as τ--r.

We analyze the structure of equilibria and the price of anarchy in the family of network creation games considered extensively in the past few years, which attempt to unify the network design and network routing problems by modeling both creation and usage costs. In general, the games are played on a host graph, where each node is a selfish independent agent (player) and each edge has a fixed link creation cost~$\alpha$. Together the agents create a network (a subgraph of the host graph) while selfishly minimizing the link creation costs plus the sum of the distances to all other players (usage cost). In this paper, we pursue two important facets of the network creation~game. First, we study extensively a natural version of the game, called the cooperative model, where nodes can collaborate and share the cost of creating any edge in the host graph. We prove the first nontrivial bounds in this model, establishing that the price of anarchy is polylogarithmic in $n$ for all values of~$\alpha$ in complete host graphs. This bound is the first result of this type for any version of the network creation game; most previous general upper bounds are polynomial in~$n$. Interestingly, we also show that equilibrium graphs have polylogarithmic diameter for the most natural range of~$\alpha$ (at most $n \mathop{\rm polylg}\nolimits n$). Second, we study the impact of the natural assumption that the host graph is a general graph, not necessarily complete. This model is a simple example of nonuniform creation costs among the edges (effectively allowing weights of $\alpha$ and~$\infty$). We prove the first assemblage of upper and lower bounds for this context, establishing nontrivial tight bounds for many ranges of~$\alpha$, for both the unilateral and cooperative versions of network creation. In particular, we establish polynomial lower bounds for both versions and many ranges of~$\alpha$, even for this simple nonuniform cost model, which sharply contrasts the conjectured constant bounds for these games in complete (uniform) graphs.

This paper proposes and evaluates a Network Aware Forward Caching approach for determining the optimal deployment strategy of forward caches to a network. A key advantage of this approach is that we can reduce the network costs associated with forward caching to maximize the benefit obtained from their deployment. We show in our simulation that a 37% increase to net benefits could be achieved over the standard method of full cache deployment to cache all POPs traffic. In addition, we show that this maximal point occurs when only 68% of the total traffic is cached.

We give approximation algorithms and inapproximability results for a class of movement problems. In general, these problems involve planning the coordinated motion of a large collection of objects (representing anything from a robot swarm or firefighter team to map labels or network messages) to achieve a global property of the network while minimizing the maximum or average movement. In particular, we consider the goals of achieving connectivity (undirected and directed), achieving connectivity between a given pair of vertices, achieving independence (a dispersion problem), and achieving a perfect matching (with applications to multicasting). This general family of movement problems encompasses an intriguing range of graph and geometric algorithms, with several real-world applications and a surprising range of approximability. In some cases, we obtain tight approximation and inapproximability results using direct techniques (without use of PCP), assuming just that P ≠ NP.

We propose weakening the assumption made when studying the price of anarchy: Rather than assume that self-interested players will play according to a Nash equilibrium (which may even be computationally hard to find), we assume only that selfish players play so as to minimize their own regret. Regret minimization can be done via simple, efficient algorithms even in many settings where the number of action choices for each player is exponential in the natural parameters of the problem. We prove that despite our weakened assumptions, in several broad classes of games, this "price of total anarchy" matches the Nash price of anarchy, even though play may never converge to Nash equilibrium. In contrast to the price of anarchy and the recently introduced price of sinking, which require all players to behave in a prescribed manner, we show that the price of total anarchy is in many cases resilient to the presence of Byzantine players, about whom we make no assumptions. Finally, because the price of total anarchy is an upper bound on the price of anarchy even in mixed strategies, for some games our results yield as corollaries previously unknown bounds on the price of anarchy in mixed strategies.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005.

We prove semilogarithmic inapproximability for a maximization problem called unique coverage: given a collection of sets, find a subcollection that maximizes the number of elements covered exactly once. Specifically, assuming that $\mathrm{NP}\not\subseteq\operatorname{BPTIME}(2^{n^\varepsilon})$ for an arbitrary $\varepsilon>0$, we prove $O(1/\log^{\sigma}n)$ inapproximability for some constant $\sigma=\sigma(\varepsilon)$. We also prove $O(1/\log^{1/3-\varepsilon}n)$ inapproximability for any $\varepsilon>0$, assuming that refuting random instances of 3SAT is hard on average; and we prove $O(1/\log n)$ inapproximability under a plausible hypothesis concerning the hardness of another problem, balanced bipartite independent set. We establish an $\Omega(1/\log n)$-approximation algorithm, even for a more general (budgeted) setting, and obtain an $\Omega(1/\log B)$-approximation algorithm when every set has at most B elements. We also show that our inapproximability results extend to envy-free pricing, an important problem in computational economics. We describe how the (budgeted) unique coverage problem, motivated by real-world applications, has close connections to other theoretical problems, including max cut, maximum coverage, and radio broadcasting.

We develop the algorithmic theory of vertex separators and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into $L_1$ (and even Euclidean embeddings) are insufficient but that the additional structure provided by many embedding theorems does suffice for our purposes. We obtain an $O(\sqrt{\log n})$ approximation for minimum ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be $\Theta(\sqrt{\log n})$. We also prove an optimal $O(\log k)$-approximate max-flow/min-vertex-cut theorem for arbitrary vertex-capacitated multicommodity flow instances on k terminals. For uniform instances on any excluded-minor family of graphs, we improve this to $O(1)$, and this yields a constant-factor approximation for minimum ratio vertex cuts in such graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best known ratio was $O(\log n)$. These results have a number of applications. We exhibit an $O(\sqrt{\log n})$ pseudoapproximation for finding balanced vertex separators in general graphs. In fact, we achieve an approximation ratio of $O(\sqrt{\log {opt}})$, where ${opt}$ is the size of an optimal separator, improving over the previous best bound of $O(\log {opt})$. Likewise, we obtain improved approximation ratios for treewidth: in any graph of treewidth k, we show how to find a tree decomposition of width at most $O(k \sqrt{\log k})$, whereas previous algorithms yielded $O(k \log k)$. For graphs excluding a fixed graph as a minor (which includes, e.g., bounded genus graphs), we give a constant-factor approximation for the treewidth. This in turn can be used to obtain polynomial-time approximation schemes for several problems in such graphs.

Hat problems have become a popular topic in recreational mathematics. In a typical hat problem, each of n players tries to guess the color of the hat he or she is wearing by looking at the colors of the hats worn by some of the other players. In this paper we consider several variants of the problem, united by the common theme that the guessing strategies are required to be deterministic and the objective is to maximize the number of correct answers in the worst case. We also summarize what is currently known about the worst-case analysis of deterministic hat guessing problems with a finite number of players.

We introduce a new notion of embedding, called minimum-relaxation ordinal embedding , parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the relative order between pairs of distances, and not the distances themselves, that must be preserved as much as possible. The (multiplicative) relaxation of an ordinal embedding is the maximum ratio between two distances whose relative order is inverted by the embedding. We develop several worst-case bounds and approximation algorithms on ordinal embedding. In particular, we establish that ordinal embedding has many qualitative differences from metric embedding, and we capture the ordinal behavior of ultrametrics and shortest-path metrics of unweighted trees.

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 of selfish node players, each creating some incident links, and the goal is to minimize α times the cost of the created links plus sum of the distances to all other players. Fabrikant et al. proved an upper bound O(√α) on the price of anarchy, i.e., the relative cost of the lack of coordination. Albers, Eilts, Even-Dar, Mansour, and Roditty show that the price of anarchy is constant for α = O(√n) and for α ≥ 12n[lg n], and that the price of anarchy is 15(1+min {α2 n, n2 α})1/3) for any α. The latter bound shows the first sublinear worst-case bound, O(n1/3), for all α. But no better bound is known for α between ω(√n) and o(n lg n). Yet α ≈ n is perhaps the most interesting range, for it corresponds to considering the average distance (instead ofthe sum of distances) to other nodes to be roughly on par with link creation (effectively dividing α by n).

This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α. There are two natural versions of this problem, both considered extensively in recent work: minimize the total power consumption (including computation time), or minimize the number of gaps in execution. For both versions in a multiprocessor system, we develop a polynomial-time algorithm based on sophisticated dynamic programming. In a generalization of the power-saving problem, where each task can execute in any of a specified set of time intervals, we develop a (1 + 23 α)-approximation, and show that dependence on α is necessary. In contrast, the analogous multi-interval gap scheduling problem is set-cover hard (and thus not o(lg n)-approximable), even in the special cases of just two intervals per job or just three unit intervals per job. We also prove several other hardness-of-approximation results. Finally, we give an O(√n)-approximation for maximizing throughput given a hard upper bound on the number of gaps.

We consider distributed algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. We seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors. Our problem is analogous to recent work on oblivious routing [M. Bienkowski, M. Korzeniowski, and H. Räcke, Proceedings of the $15$th Annual ACM Symposium on Parallel Algorithms and Architectures, 2003, pp. 24–33, C. Harrelson, K. Hildrum, and S. Rao, Proceedings of the $15$th Annual ACM Symposium on Parallel Algorithms and Architectures, 2003, pp. 34–43, H. Räcke, Proceedings of the $43$rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 43–52] but with the objective of maximizing throughput rather than minimizing congestion. In contrast to that work, we prove a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm. This is accompanied by simple algorithms achieving upper bounds which are tight in terms of $\OPT$, the maximum throughput achievable by an omniscient algorithm, and are also tight in terms of m, the number of servers. Finally, we investigate an online version of the problem, in a restricted model which requires that clients, upon becoming active, must remain so for at least $log(n)$ time steps. In contrast to our primarily negative results in the oblivious case, here we present an algorithm which is constant-competitive. Our lower bounds justify the intuition, implicit in earlier work on the subject [B. Awerbuch and Y. Azar, Proceedings of the $35$th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 240–249], that some such restriction (i.e., requiring some stability in the demand pattern over time) is necessary in order to achieve a constant—or even polylogarithmic—competitive ratio.

Oblivious routing algorithms for general undirected networks were introduced by Räcke [2002], and this work has led to many subsequent improvements and applications. Comparatively little is known about oblivious routing in general directed networks, or even in undirected networks with node capacities. We present the first nontrivial upper bounds for both these cases, providing algorithms for k -commodity oblivious routing problems with competitive ratio O (√ k log( n )) for undirected node-capacitated graphs and O (√ k n 1/4 log( n )) for directed graphs. In the special case that all commodities have a common source or sink, our upper bound becomes O (√ n log( n )) in both cases, matching the lower bound up to a factor of log( n ). The lower bound (which first appeared in Azar et al. [2003]) is obtained on a graph with very high degree. We show that, in fact, the degree of a graph is a crucial parameter for node-capacitated oblivious routing in undirected graphs, by providing an O (Δ polylog( n ))-competitive oblivious routing scheme for graphs of degree Δ. For the directed case, however, we show that the lower bound of Ω(√ n ) still holds in low-degree graphs. Finally, we settle an open question about routing problems in which all commodities share a common source or sink. We show that even in this simplified scenario there are networks in which no oblivious routing algorithm can achieve a competitive ratio better than Ω(log n ).

Wireless LAN administrators often have to deal with the problem of sporadic client congestion in popular locations within the network. Existing approaches that relieve congestion by balancing the traffic load are encumbered by the modifications that are required to both access points and clients. We propose cell breathing, a well-known concept in cellular telephony, as a load balancing mechanism to handle client congestion in a wireless LAN. We develop power management algorithms for controlling the coverage of access points to handle dynamic changes in client workloads. We further incorporate hand-off costs and manufacturer specified power level constraints into our algorithms. Our approach does not require modification to clients or to the standard. It only changes the transmission power of beacon packets and does not change the transmission power of data packets to avoid the interactions with auto-rating. We analyze the worst-case bounds of the algorithms and show that they are either optimal or close to optimal. In addition, we evaluate our algorithms empirically using synthetic and real wireless LAN traces. Our results show that cell breathing significantly outperforms the commonly used fixed power scheme and performs at par with sophisticated load balancing schemes that require changes to both the client and access points

Embedding metrics into constant-dimensional geometric spaces, such as the Euclidean plane, is relatively poorly understood. Motivated by applications in visualization, ad-hoc networks, and molecular reconstruction, we consider the natural problem of embedding shortest-path metrics of unweighted planar graphs (planar graph metrics) into the Euclidean plane. It is known that, in the special case of shortest-path metrics of trees, embedding into the plane requires Θ(√n) distortion in the worst case [19, 1], and surprisingly, this worst-case upper bound provides the best known approximation algorithm for minimizing distortion. We answer an open question posed in this work and highlighted by Matoušek [21] by proving that some planar graph metrics require Ω(n2/3) distortion in any embedding into the plane, proving the first separation between these two types of graph metrics. We also prove that some planar graph metrics require Ω(n) distortion in any crossing-free straight-line embedding into the plane, suggesting a separation between low-distortion plane embedding and the well-studied notion of crossing-free straight-line planar drawings. Finally, on the upper-bound side, we prove that all outerplanar graph metrics can be embedded into the plane with O(√n) distortion, generalizing the previous results on trees (both the worst-case bound and the approximation algorithm) and building techniques for handling cycles in plane embeddings of graph metrics.

We consider approximation algorithms for non-uniform buy-at-bulk network design problems. The first non-trivial approximation algorithm for this problem is due to Charikar and Karagiozova (STOC 05); for an instance on h pairs their algorithm has an approximation guarantee of exp(O(radic(log h log log h)))for the uniform-demand case, and log D middot exp(O(radic(log h log log h))) for the general demand case, where D is the total demand. We improve upon this result, by presenting the first poly-logarithmic approximation for this problem. The ratio we obtain is O(log3h middot min{log D, gamma(h2)}) where his the number of pairs and gamma(n) is the worst case distortion in embedding the metric induced by a n vertex graph into a distribution over its spanning trees. Using the best known upper bound on gamma(n) we obtain an O(min{log3h middot log D, log5h log log h}) ratio approximation. We also give poly-logarithmic approximations for some variants of the single-source problem that we need for the multicommodity problem

Abstract — With the increasing commercial interest in supporting voice and multimedia services over the IP network there is a need for bandwidth guaranteed services. For example, guaranteeing the peak demand of VoIP traffic entails high costs in terms of bandwidth reservation requirements. To effectively make use of the reserved peak bandwidth, it is imperative that this bandwidth is shared with best effort data traffic during non peak periods. In this paper, we formulate this bandwidth sharing network design problem. Our goal is to minimize the total cost of bandwidth reservation while satisfying (1) the peak demand for real time traffic, and (2) the average demand of both real time and best effort data traffic. We show that, the problem is polynomially solvable if we do not restrict the number of paths used. It is strongly NP-hard if we use only one path between any pair of nodes. We present a simple 2-approximation algorithm and through simulation studies show that this algorithm can be further improved using a local search heuristic. Our simulation results also show that sharing significantly reduces the total bandwidth reservation costs and our local search heuristic can find a solution which is very close to or equal to the optimal in most cases.

We introduce semi-oblivious routing, a generalization of oblivious routing in which multicommodity flows must be routed using a polynomial-sized set of paths which is predefined by the algorithm before the demand matrix for the flow problem is revealed. Our results, which are primarily negative, exclude the possibility of constant-competitive semi-oblivious routing schemes, even when the network is a grid or a seriesparallel graph. We provide an even stronger lower bound on the congestion of constant-bend routing schemes in the grid.

Bidimensionality provides a tool for developing subexponential fixed-parameter algorithms for combinatorial optimization problems on graph families that exclude a minor. This paper extends the theory of bidimensionality for graphs of bounded genus (which is a minor-excluding family). Specifically we show that, for any problem whose solution value does not increase under contractions and whose solution value is large on a grid graph augmented by a bounded number of handles, the treewidth of any bounded-genus graph is at most a constant factor larger than the square root of the problem's solution value on that graph. Such bidimensional problems include vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, r-dominating set, connected dominating set, planar set cover, and diameter. On the algorithmic side, by showing that an augmented grid is the prototype bounded-genus graph, we generalize and simplify many existing algorithms for such problems in graph classes excluding a minor. On the combinatorial side, our result is a step toward a theory of graph contractions analogous to the seminal theory of graph minors by Robertson and Seymour.

At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.

We consider the problem of deploying or repairing a sensor network to guarantee a specified level of multi-path connectivity (k-connectivity) between all nodes. Such a guarantee simultaneously provides fault tolerance against node failures and high capacity through multi-path routing. We design and analyze the first algorithms that place an almost-minimum number of additional sensors to augment an existing network into a k-connected network, for any desired parameter k. Our algorithms have provable guarantees on the quality of the solution. Specifically, we prove that the number of additional sensors is within a constant factor of the absolute minimum, for any fixed k. We have implemented greedy and distributed versions of this algorithm, and demonstrate in simulation that they produce high-quality placements for the additional sensors. We are also in the process of using our algorithms to deploy nodes in a physical sensor network using a mobile robot.

This paper concerns the design of mechanisms for online scheduling in which agents bid for access to a re-usable resource such as processor time or wireless network access. Each agent is assumed to arrive and depart dynamically, and in the basic model require the resource for one unit of time. We seek mechanisms that are truthful in the sense that truthful revelation of arrival, departure and value information is a dominant strategy, and that are online in the sense that they make allocation decisions without knowledge of the future. First, we provide two characterizations for the class of truthful online allocation rules. The characterizations extend beyond the typical single-parameter settings, and formalize the role of restricted misreporting in reversing existing price-based characterizations. Second, we present an online auction for unit-length jobs that achieves total value that is 2-competitive with the maximum offline value. We prove that no truthful deterministic online mechanism can achieve a better competitive ratio. Third, we consider revenue competitiveness and prove that no deterministic truthful online auction has revenue that is constant-competitive with that of the offline Vickrey-Clarke-Groves (VCG) mechanism We provide a randomized online auction that achieves a competitive ratio of O(log h), where h is the ratio of maximum value to minimum value among the agents; this mechanism does not require prior knowledge of h. Finally, we generalize our model to settings with multiple re-usable goods and to agents with different job lengths.

We develop the algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into L1 (and even Euclidean embeddings) are insufficient, but that the additional structure provided by many embedding theorems does suffice for our purposes.We obtain an O(√log n) approximation for min-ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be Θ(√log n). We also prove various approximate max-flow/min-vertex-cut theorems, which in particular give a constant-factor approximation for min-ratio vertex cuts in any excluded-minor family of graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best-known ratio was O(log n).These results have a number of applications. We exhibit an O(√log n) pseudo-approximation for finding balanced vertex separators in general graphs. In fact, we achieve an approximation ratio of O(√log opt) where opt is the size of an optimal separator, improving over the previous best bound of O(log opt). Likewise, we obtain improved approximation ratios for treewidth: In any graph of treewidth k, we show how to find a tree decomposition of width at most O(k √log k), whereas previous algorithms yielded O(k log k). For graphs excluding a fixed graph as a minor (which includes, e.g., bounded genus graphs), we give a constant-factor approximation for the treewidth; this can be used to obtain the first polynomial-time approximation schemes for problems like minimum feedback vertex set and minimum connected dominating set in such graphs.

Oblivious routing algorithms for general undirected networks were introduced by Räcke, and this work has led to many subsequent improvements and applications. More precisely, Räcke showed that there is an oblivious routing algorithm with polylogarithmic competitive ratio (w.r.t. edge congestion) for any undirected graph. Comparatively little positive results are known about oblivious routing in general directed networks. Using a novel approach, we present the first oblivious routing algorithm which is O(log2 n) competitive with high probability in directed graphs given that the demands are chosen randomly from a known demand-distribution. On the other hand, we show that no oblivious routing algorithm can be o(logn/log log n) competitive even with constant probability in general directed graphs.Our routing algorithms are not oblivious in the traditional definition, but we add the concept of demand-dependence, i.e., the path chosen for an s-t pair may depend on the demand between s and t. This concept that still preserves that routing decisions are only based on local information proves very powerful in our randomized demand model.Finally, we show that our approach for designing competitive oblivious routing algorithms is quite general and has applications in other contexts like stochastic scheduling.

We introduce a new framework for designing fixed-parameter algorithms with subexponential running time---2 O(√k) n O(1) . Our results apply to a broad family of graph problems, called bidimensional problems , which includes many domination and problems such as vertex cover, feedback vertex set, minimum maximal matching, dominating set, edge dominating set, disk dimension, and many others restricted to bounded-genus graphs (phrased as bipartite-graph problem ). Furthermore, it is fairly straightforward to prove that a problem is bidimensional. In particular, our framework includes, as special cases, all previously known problems to have such subexponential algorithms. Previously, these algorithms applied to planar graphs, single-crossing-minor-free graphs, and/or map graphs; we extend these results to apply to bounded-genus graphs as well. In a parallel development of combinatorial results, we establish an upper bound on the treewidth (or branchwidth) of a bounded-genus graph that excludes some planar graph H as a minor. This bound depends linearly on the size |V(H)| of the excluded graph H and the genus g(G) of the graph G , and applies and extends the graph-minors work of Robertson and Seymour.Building on these results, we develop subexponential fixed-parameter algorithms for dominating set, vertex cover, and set cover in any class of graphs excluding a fixed graph H as a minor. In particular, this general category of graphs includes planar graphs, bounded-genus graphs, single-crossing-minor-free graphs, and any class of graphs that is closed under taking minors. Specifically, the running time is 2 O(√k) n h , where h is a constant depending only on H , which is polynomial for k = O (log 2 n ). We introduce a general approach for developing algorithms on H -minor-free graphs, based on structural results about H -minor-free graphs at the heart of Robertson and Seymour's graph-minors work. We believe this approach opens the way to further development on problems in H -minor-free graphs.

The ( k , r )-center problem asks whether an input graph G has ≤ k vertices (called centers ) such that every vertex of G is within distance ≤ r from some center. In this article, we prove that the ( k , r )-center problem, parameterized by k and R , is fixed-parameter tractable (FPT) on planar graphs, i.e., it admits an algorithm of complexity f ( k , r ) n O (1) where the function f is independent of n . In particular, we show that f ( k,r ) = 2 O ( r log r ) √k , where the exponent of the exponential term grows sublinearly in the number of centers. Moreover, we prove that the same type of FPT algorithms can be designed for the more general class of map graphs introduced by Chen, Grigni, and Papadimitriou. Our results combine dynamic-programming algorithms for graphs of small branchwidth and a graph-theoretic result bounding this parameter in terms of k and r . Finally, a byproduct of our algorithm is the existence of a PTAS for the r -domination problem in both planar graphs and map graphs.Our approach builds on the seminal results of Robertson and Seymour on Graph Minors, and as a result is much more powerful than the previous machinery of Alber et al. for exponential speedup on planar graphs. To demonstrate the versatility of our results, we show how our algorithms can be extended to general parameters that are “large” on grids. In addition, our use of branchwidth instead of the usual treewidth allows us to obtain much faster algorithms, and requires more complicated dynamic programming than the standard leaf/introduce/forget/join structure of nice tree decompositions. Our results are also unique in that they apply to classes of graphs that are not minor-closed, namely, constant powers of planar graphs and map graphs.

A frequently arising problem in computational geometry is when a physical structure, such as an ad-hoc wireless sensor network or a protein backbone, can measure local information about its geometry (e.g., distances, angles, and/or orientations), and the goal is to reconstruct the global geometry from this partial information. More precisely, we are given a graph, the approximate lengths of the edges, and possibly extra information, and our goal is to assign coordinates to the vertices that satisfy the given constraints up to a constant factor away from the best possible. We obtain the first subexponential-time (quasipolynomial-time) algorithm for this problem given a complete graph of Euclidean distances with additive error and no extra information. For general graphs, the analogous problem is NP-hard even with exact distances. Thus, for general graphs, we consider natural types of extra information that make the problem more tractable, including approximate angles between edges, the order type of vertices, a model of coordinate noise, or knowledge about the range of distance measurements. Our quasipolynomial-time algorithm for no extra information can also beviewed as a polynomial-time algorithm given an "extremum oracle" as extra information. We give several approximation algorithms and contrasting hardness results for these scenarios.

We study a limited-supply online auction problem, in which an auctioneer has k goods to sell and bidders arrive and depart dynamically. We suppose that agent valuations are drawn independently from some unknown distribution and construct an adaptive auction that is nevertheless value- andtime-strategy proof. For the k=1 problem we have a strategyproof variant on the classic secretary problem. We present a 4-competitive (e-competitive) strategyproof online algorithm with respect to offline Vickrey for revenue (efficiency). We also show (in a model that slightly generalizes the assumption of independent valuations) that no mechanism can be better than 3/2-competitive (2-competitive) for revenue (efficiency). Our general approach considers a learning phase followed by an accepting phase, and is careful to handle incentive issues for agents that span the two phases. We extend to the k›1 case, by deriving strategyproof mechanisms which are constant-competitive for revenue and efficiency. Finally, we present some strategyproof competitive algorithms for the case in which adversary uses a distribution known to the mechanism.

For several graph-theoretic parameters such as vertex cover and dominating set, it is known that if their sizes are bounded by k, then the treewidth of the graph is bounded by some function of k. This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs, single-crossing-minor-free graphs, and graphs of bounded genus. In this paper we examine whether similar bounds can be obtained for larger minor-closed graph classes and for general families of graph parameters, including all those for which such behavior has been reported so far. Given a graph parameter P, we say that a graph family $\mathcal{F}$ has the parameter-treewidth property for P if there is an increasing function t such that every graph $G\in\mathcal{F}$ has treewidth at most t(P(G)). We prove as our main result that, for a large family of graph parameters called contraction-bidimensional, a minor-closed graph family $\mathcal{F}$ has the parameter-treewidth property if $\mathcal{F}$ has bounded local treewidth. We also show "if and only if" for some graph parameters, and thus, this result is in some sense tight. In addition we show that, for a slightly smaller family of graph parameters called minor-bidimensional, all minor-closed graph families $\mathcal{F}$, excluding some fixed graphs, have the parameter-treewidth property. The contraction-bidimensional parameters include many domination and covering graph parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set, and q-dominating set (for fixed q). We use our theorems to develop new fixed-parameter algorithms in these contexts.

In ad hoc wireless networks, it is crucial to minimize power consumption while maintaining key network properties. This work studies power assignments of wireless devices that minimize power while maintaining k-fault tolerance. Specifically, we require all links established by this power setting be symmetric and form a k-vertex connected subgraph of the network graph. This problem is known to be NP-hard. We show current heuristic approaches can use arbitrarily more power than the optimal solution. Hence, we seek approximation algorithms for this problem. We present three approximation algorithms. The first algorithm gives an O(ka) approximation where a is the best approximation factor for the related problem in wired networks (the best a so far is in O(log k).) Then, using a more complicated algorithm and careful analysis, we achieve O(k) approximation for general graphs. We then present simple and practical distributed approximation algorithms for the cases of 2- and 3-connectivity in geometric graphs. In addition, we demonstrate how we can generalize this algorithm for k-connectivity in geometric graphs. Finally, we show that these approximation algorithms compare favorably with existing heuristics. We note that all algorithms presented in this paper can be used to minimize power while maintaining k-edge connectivity with guaranteed approximation factors.

Abstract In this paper, we introduce a generalized version of the facility location problem in which the facility cost is a function of the number of clients assigned to the facility. We focus on the case of concave facility cost functions. We observe that this problem can be reduced to the uncapacitated facility location problem. We analyze a natural greedy algorithm for this problem and show that its approximation factor is at most 1.861. We also consider several generalizations and variants of this problem. © 2003 Wiley Periodicals, Inc.

We can control the topology of a multi-hop wireless network by varying the transmission power at each node. The life-time of such networks depends on battery power at each node. This paper presents a distributed fault-tolerant topology control algorithm for minimum energy consumption in these networks. More precisely, we present algorithms which preserve the connectivity of a network upon failing of, at most, k nodes (k is constant) and simultaneously minimize the transmission power at each node to some extent. In addition, we present simulations to support the effectiveness of our algorithm. We also demonstrate some optimizations to further minimize the power at each node. Finally, we show how our algorithms can be extended to 3-dimensions.

Abstract The path‐matching problem is to find a set of vertex‐ or edge‐disjoint paths with length constraints in a given graph with a given set of endpoints. This problem has several applications in broadcasting and multicasting in computer networks. In this paper, we study the algorithmic complexity of different cases of this problem. In each case, we either provide a polynomial‐time algorithm or prove that the problem is NP‐complete. © 2002 Wiley Periodicals, Inc.