We investigate the power of CUT queries to reveal the structure of unknown hypergraphs. While simple graphs allow for optimal O(n)-query connectivity algorithms, hypergraphs face a fundamental identifiability barrier in that distinct hypergraphs can share identical cut-profiles, making exact edge learning impossible in general, a primitive crucial in the graph connectivity algorithms. We first present a zero-error randomized algorithm that identifies the connected components of any weighted hypergraph using O(n) expected queries, matching the Ω(n) lower bound. This approach bypasses the reconstruction barrier by introducing the notion of "independent families" - vertex subpartitions that do not share hyperedges - and iteratively coarsening them using auxiliary weighted graph connectivity techniques of [Liao and Chakrabarty, 2024]. Second, we demonstrate that the impossibility of exact learning depends on hyperedge parity. For hypergraphs all of whose hyperedges have even cardinality, we show that the structure is reconstructible using a Möbius transform on the CUT function to implement binary-search-style vertex identification. This yields deterministic algorithms for obtaining k-connectivity certificates for r-bounded even hypergraphs in Õ_r(kn) queries. Finally, we bypass parity and rank constraints for linear hypergraphs, achieving a subquadratic Õ(kn^1.5) query complexity for k-connectivity. This significantly improves upon the general Õ(n²) bound derived via symmetric submodular function minimization.

We revisit the problem of designing sublinear algorithms for estimating the average degree of an \(n\)-vertex graph. The standard access model for graphs allows for the following queries: sampling a uniform random vertex, the degree of a vertex, sampling a uniform random neighbor of a vertex, and “pair queries” which determine if a pair of vertices form an edge. In this model, original results [Goldreich-Ron, RSA 2008; Eden-Ron-Seshadhri, SIDMA 2019] on this problem prove that the complexity of getting \((1+\varepsilon)\)-multiplicative approximations to the average degree, ignoring \(\varepsilon\)-dependencies, is \(\Theta(\sqrt{n})\). When random edges can be sampled, it is known that the average degree can be estimated in \(\tilde{O}(n^{1/3})\) queries, even without pair queries Motwani-Panigrahy-Xu-ICALP-2007, Beretta-Tetek-TALG-2024.

Abstract. Monotonicity testing of Boolean functions on the hypergrid, [Formula: see text], is a classic topic in property testing. Determining the nonadaptive complexity of this problem is an important open question. For arbitrary [Formula: see text], [H. Black, D. Chakrabarty, and C. Seshadhri, Proceedings of the 14 th Annual ACM-SIAM Symposium on Discrete Algorithms, 2020, pp. 1975–1994] describes a tester with query complexity [Formula: see text]. This complexity is independent of [Formula: see text] but has a suboptimal dependence on [Formula: see text]. Recently, Braverman et al. [ Proceedings of Innovations in Theoretical Computer Science, 2023, pp. 25:1–25:24] and H. Black, D. Chakrabarty, and C. Seshadhri [ Proceedings of the 55 th Annual ACM Symposium on Theory of Computing, 2023, pp. 233–241] described [Formula: see text]- and [Formula: see text]-query testers, respectively. These testers have an almost optimal dependence on [Formula: see text] but a suboptimal polynomial dependence on [Formula: see text]. In this paper, we describe a nonadaptive, one-sided monotonicity tester with query complexity [Formula: see text] , independent of [Formula: see text]. Up to the [Formula: see text]-factors, our result resolves the nonadaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of [Formula: see text] yields a nonadaptive, one-sided [Formula: see text]-query monotonicity tester for Boolean functions [Formula: see text] associated with an arbitrary product measure.

We introduce the aggregated clustering problem, where one is given T instances of a center-based clustering task over the same n points, but under different metrics. The goal is to open k centers to minimize an aggregate of the clustering costs - e.g., the average or maximum - where the cost is measured via k-center/median/means objectives. More generally, we minimize a norm Ψ over the T cost values. We show that for T ≥ 3, the problem is inapproximable to any finite factor in polynomial time. For T = 2, we give constant-factor approximations. We also show W[2]-hardness when parameterized by k, but obtain f(k,T)poly(n)-time 3-approximations when parameterized by both k and T. When the metrics have structure, we obtain efficient parameterized approximation schemes (EPAS). If all T metrics have bounded ε-scatter dimension, we achieve a (1+ε)-approximation in f(k,T,ε)poly(n) time. If the metrics are induced by edge weights on a common graph G of bounded treewidth tw, and Ψ is the sum function, we get an EPAS in f(T,ε,tw)poly(n,k) time. Conversely, unless (randomized) ETH is false, any finite factor approximation is impossible if parametrized by only T, even when the treewidth is tw = Ω(polylog n).

In this paper we describe a randomized algorithm which returns a maximal spanning forest of an unknown {\em weighted} undirected graph making $O(n)$ $\mathsf{CUT}$ queries in expectation. For weighted graphs, this is optimal due to a result in [Auza and Lee, 2021] which shows an $\Omega(n)$ lower bound for zero-error randomized algorithms. These questions have been extensively studied in the past few years, especially due to the problem’s connections to symmetric submodular function minimization. We also describe a simple polynomial time deterministic algorithm that makes $O(\frac{n\log n}{\log\log n})$ queries on undirected unweighted graphs and returns a maximal spanning forest, thereby (slightly) improving upon the state-of-the-art.

We consider the problem of learning an unknown partition of an $n$ element universe using rank queries. Such queries take as input a subset of the universe and return the number of parts of the partition it intersects. We give a simple $O(n)$-query, efficient, deterministic algorithm for this problem. We also generalize to give an $O(n + k\log r)$-rank query algorithm for a general partition matroid where $k$ is the number of parts and $r$ is the rank of the matroid.

We consider the problem of finding a spanning forest in an unknown {\em weighted} undirected graph when the access to the graph is via CUT queries, that is, one can query a subset $S\subseteq V$ of vertices and get the cut-value $\sum_{e\in \partial S} w(e)$ as the response. It is not too hard to solve this problem using $O(n\log n)$ queries mimicking a Prim-style algorithm using a binary-search style idea. In this paper we use the power of CUT queries to obtain a Monte-Carlo algorithm that makes $O(n\log \log n(\log\log\log n)^2)$ CUT queries. At the core of our contribution is a generalization of a result in [Apers et al., 2022] which studies the same problem on unweighted graphs, but to handle weights, we need to combine their ideas with ideas for {\em support estimation} of weighted vectors, as in [Stockmeyer, 1983], and {\em weighted graph reconstruction} algorithms, as in [Bshouty and Mazzawi, 2012].

Monotonicity testing of Boolean functions on the hypergrid, $f:[n]^{d} \rightarrow\{0,1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary n, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $\widetilde{O}\left(\varepsilon^{-4 / 3} d^{5 / 6}\right)$. This complexity is independent of n, but has a suboptimal dependence on d. Recently, [Braverman-Khot-Kindler-Minzer, ITCS 2023] and [Black-Chakrabarty-Seshadhri, STOC 2023] describe $\widetilde{O}\left(\varepsilon^{-2} n^{3} \sqrt{d}\right)$ and $\widetilde{O}\left(\varepsilon^{-2} n \sqrt{d}\right)$-query testers, respectively. These testers have an almost optimal dependence on d, but a suboptimal polynomial dependence on n. In this paper, we describe a non-adaptive, onesided monotonicity tester with query complexity $O\left(\varepsilon^{-2} d^{1 / 2+o(1)}\right)$, independent of n. Up to the $d^{o(1)}$. factors, our result resolves the non-adaptive complexity of monotonicity testing for Boolean functions on hypergrids. The independence of n yields a non-adaptive, one-sided $O\left(\varepsilon^{-2} d^{1 / 2+o(1)}\right)$-query monotonicity tester for Boolean functions $f: \mathbb{R}^{d} \rightarrow\{0,1\}$ associated with an arbitrary product measure.

We consider the parallel complexity of submodular function minimization (SFM). We provide a pair of methods which obtain two new query versus depth trade-offs a submodular function defined on subsets of $n$ elements that has integer values between $-M$ and $M$. The first method has depth $2$ and query complexity $n^{O(M)}$ and the second method has depth $\widetilde{O}(n^{1/3} M^{2/3})$ and query complexity $O(\mathrm{poly}(n, M))$. Despite a line of work on improved parallel lower bounds for SFM, prior to our work the only known algorithms for parallel SFM either followed from more general methods for sequential SFM or highly-parallel minimization of convex $\ell_2$-Lipschitz functions. Interestingly, to obtain our second result we provide the first highly-parallel algorithm for minimizing $\ell_\infty$-Lipschitz function over the hypercube which obtains near-optimal depth for obtaining constant accuracy.

The problem of testing monotonicity for Boolean functions on the hypergrid, f:[n]d → {0,1} is a classic topic in property testing. When n=2, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making O(ε−2√d) queries. Up to polylog d and ε factors, this bound matches the Ω(√d)-query non-adaptive lower bound (Chen-De-Servedio-Tan (STOC 2015), Chen-Waingarten-Xie (STOC 2017)). For any n > 2, the optimal non-adaptive complexity was unknown. A previous result of the authors achieves a O(d5/6)-query upper bound (SODA 2020), quite far from the √d bound for the hypercube. In this paper, we resolve the non-adaptive complexity of monotonicity testing for all constant n, up to poly(ε−1logd) factors. Specifically, we give a non-adaptive, one-sided monotonicity tester making O(ε−2n√d) queries. From a technical standpoint, we prove new directed isoperimetric theorems over the hypergrid [n]d. These results generalize the celebrated directed Talagrand inequalities that were only known for the hypercube.

In this paper, we consider center-based clustering problems where C, the set of points to be clustered, lies in a metric space (X,d), and the set X of candidate centers is potentially infinite-sized. We call such problems continuous clustering problems to differentiate them from the discrete clustering problems where the set of candidate centers is explicitly given. It is known that for many objectives, when one restricts the set of centers to C itself and applies an α_dis-approximation algorithm for the discrete version, one obtains a β ⋅ α_{dis}-approximation algorithm for the continuous version via the triangle inequality property of the distance function. Here β depends on the objective, and for many objectives such as k-median, β = 2, while for some others such as k-means, β = 4. The motivating question in this paper is whether this gap of factor β between continuous and discrete problems is inherent, or can one design better algorithms for continuous clustering than simply reducing to the discrete case as mentioned above? In a recent SODA 2021 paper, Cohen-Addad, Karthik, and Lee prove a factor-2 and a factor-4 hardness, respectively, for the continuous versions of the k-median and k-means problems, even when the number of cluster centers is a constant. The discrete problem for a constant number of centers is easily solvable exactly using enumeration, and therefore, in certain regimes, the "β-factor loss" seems unavoidable. In this paper, we describe a technique based on the round-or-cut framework to approach continuous clustering problems. We show that, for the continuous versions of some clustering problems, we can design approximation algorithms attaining a better factor than the β-factor blow-up mentioned above. In particular, we do so for: the uncapacitated facility location problem with uniform facility opening costs (λ-UFL); the k-means problem; the individually fair k-median problem; and the k-center with outliers problem. Notably, for λ-UFL, where β = 2 and the discrete version is NP-hard to approximate within a factor of 1.27, we describe a 2.32-approximation for the continuous version, and indeed 2.32 < 2 × 1.27. Also, for k-means, where β = 4 and the best known approximation factor for the discrete version is 9, we obtain a 32-approximation for the continuous version, which is better than 4 × 9 = 36. The main challenge one faces is that most algorithms for the discrete clustering problems, including the state of the art solutions, depend on Linear Program (LP) relaxations that become infinite-sized in the continuous version. To overcome this, we design new linear program relaxations for the continuous clustering problems which, although having exponentially many constraints, are amenable to the round-or-cut framework.

We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prove that any deterministic SFM algorithm on a ground set of n elements requires at least $\Omega(n\log n)$ queries to an evaluation oracle. This is the first super-linear query complexity lower bound for SFM and improves upon the previous best lower bound of 2n given by [Graur et al., ITCS 2020]. Using our construction, we also prove that any (possibly randomized) parallel SFM algorithm, which can make up to poly $(n)$ queries per round, requires at least $\Omega(n/\log n)$ rounds to minimize a submodular function. This improves upon the previous best lower bound of $\tilde{\Omega}(n^{1/3})$ rounds due to [Chakrabarty et al., FOCS 2021], and settles the parallel complexity of query-efficient SFM up to logarithmic factors due to a recent advance in [Jiang, SODA 2021].

Multi-pass streaming algorithm for Maximum Matching have been studied since more than 15 years and various algorithmic results are known today, including 2-pass streaming algorithms that break the 1/2-approximation barrier, and (1-ε)-approximation streaming algorithms that run in O(poly 1/ε) passes in bipartite graphs and in O((1/ε)^(1/ε)) or O(poly (1/ε) ⋅ log n) passes in general graphs, where n is the number of vertices of the input graph. However, proving impossibility results for such algorithms has so far been elusive, and, for example, even the existence of 2-pass small space streaming algorithms with approximation factor 0.999 has not yet been ruled out. The key building block of all multi-pass streaming algorithms for Maximum Matching is the Greedy matching algorithm. Our aim is to understand the limitations of this approach: How many passes are required if the algorithm solely relies on the invocation of the Greedy algorithm? In this paper, we initiate the study of lower bounds for restricted families of multi-pass streaming algorithms for Maximum Matching. We focus on the simple yet powerful class of algorithms that in each pass run Greedy on a vertex-induced subgraph of the input graph. In bipartite graphs, we show that 3 passes are necessary and sufficient to improve on the trivial approximation factor of 1/2: We give a lower bound of 0.6 on the approximation ratio of such algorithms, which is optimal. We further show that Ω(1/ε) passes are required for computing a (1-ε)-approximation, even in bipartite graphs. Last, the considered class of algorithms is not well-suited to general graphs: We show that Ω(n) passes are required in order to improve on the trivial approximation factor of 1/2.

The problem of minimizing a submodular function (SFM) is a common generalization of several fundamental combinatorial optimization problems, including minimum$s-t$cuts in graphs and matroid intersection. It is well-known that a submodular function can be minimized with only$\text{poly} (N)$function evaluation queries where$N$denotes the universe size. However, all known polynomial query algorithms for SFM are highly adaptive, requiring at least$N$rounds of adaptivity. A natural question is if SFM can be efficiently solved in a highly parallel manner, namely, with$\text{poly} (N)$queries using only poly-logarithmic rounds of adaptivity. An important step towards understanding the adaptivity needed to solve SFM efficiently was taken in the very recent work of Balkanski and Singer who showed that any SFM algorithm with$\text{poly} (N)$queries. This left open the possibility of efficient SFM algorithms with poly-logarithmic rounds of adaptivity. In this work, we strongly rule out this possibility by showing that any, possibly randomized, algorithm for submodular function minimization making$\text{poly} (N)$queries requires$\tilde{\Omega}(N^{1/3})$rounds of adaptivity. In fact, we show a polynomial lower bound on the number of rounds of adaptivity even for algorithms that make up to$2^{N^{1-\delta}}$queries, for any constant$\delta > 0$.

In the Priority $k$-Center problem, the input consists of a metric space $(X,d)$, an integer $k$, and for each point $v \in X$ a priority radius $r(v)$. The goal is to choose $k$-centers $S \subseteq X$ to minimize $\max_{v \in X} \frac{1}{r(v)} d(v,S)$. If all $r(v)$'s are uniform, one obtains the $k$-Center problem. Plesník [Plesník, Disc. Appl. Math. 1987] introduced the Priority $k$-Center problem and gave a $2$-approximation algorithm matching the best possible algorithm for $k$-Center. We show how the problem is related to two different notions of fair clustering [Harris et al., NeurIPS 2018; Jung et al., FORC 2020]. Motivated by these developments we revisit the problem and, in our main technical contribution, develop a framework that yields constant factor approximation algorithms for Priority $k$-Center with outliers. Our framework extends to generalizations of Priority $k$-Center to matroid and knapsack constraints, and as a corollary, also yields algorithms with fairness guarantees in the lottery model of Harris et al [Harris et al, JMLR 2019].

We study data clustering problems with $\ell_p$-norm objectives (e.g. \textsc{$k$-Median} and \textsc{$k$-Means}) in the context of individual fairness. The dataset consists of $n$ points, and we want to find $k$ centers such that (a) the objective is minimized, while (b) respecting the individual fairness constraint that every point $v$ has a center within a distance at most $r(v)$, where $r(v)$ is $v$'s distance to its $(n/k)$th nearest point. Jung, Kannan, and Lutz [FORC 2020] introduced this concept and designed a clustering algorithm with provable (approximate) fairness and objective guarantees for the $\ell_\infty$ or \textsc{$k$-Center} objective. Mahabadi and Vakilian [ICML 2020] revisited this problem to give a local-search algorithm for all $\ell_p$-norms. Empirically, their algorithms outperform Jung et. al.'s by a large margin in terms of cost (for \textsc{$k$-Median} and \textsc{$k$-Means}), but they incur a reasonable loss in fairness. In this paper, our main contribution is to use Linear Programming (LP) techniques to obtain better algorithms for this problem, both in theory and in practice. We prove that by modifying known LP rounding techniques, one gets a worst-case guarantee on the objective which is much better than in MV20, and empirically, this objective is extremely close to the optimal. Furthermore, our theoretical fairness guarantees are comparable with MV20 in theory, and empirically, we obtain noticeably fairer solutions.Although solving the LP {\em exactly} might be prohibitive, we demonstrate that in practice, a simple sparsification technique drastically improves the run-time of our algorithm.

We describe a Õ(d5/6)-query monotonicity tester for Boolean functions f: [n]d → {0, 1} on the nhypergrid. This is the first o(d) monotonicity tester with query complexity independent of n. Motivated by this independence of n, we initiate the study of monotonicity testing of measurable Boolean functions f: ℝd → {0, 1} over the continuous domain, where the distance is measured with respect to a product distribution over ℝd. We give a Õ(d5/6)-query monotonicity tester for such functions. Our main technical result is a domain reduction theorem for monotonicity. For any function f: [n]d → {0, 1}, let εf be its distance to monotonicity. Consider the restriction of the function on a random [k]d sub-hypergrid of the original domain. We show that for k = poly(d/εf), the expected distance of the restriction is . Previously, such a result was only known for d = 1 (Berman-Raskhodnikova-Yaroslavtsev, STOC 2014). Our result for testing Boolean functions over [n]d then follows by applying the d5/6 · poly(1/ε log n, log d)-query hypergrid tester of Black-Chakrabarty-Seshadhri (SODA 2018). To obtain the result for testing Boolean functions over ℝd, we use standard measure theoretic tools to reduce monotonicity testing of a measurable function f to monotonicity testing of a discretized version of f over a hypergrid domain [N]d for large, but finite, N (that may depend on f). The independence of N in the hypergrid tester is crucial to getting the final tester over ℝd.

Abstract We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of $$(2+\varepsilon )$$ (2+ε) and an amortized update time of $$O(\log n/\varepsilon ^2)$$ O(logn/ε2) . Our result can be generalized to give a fully dynamic $$O(f^3)$$ O(f3) -approximate algorithm with $$O(f^2)$$ O(f2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices.

In this article, we introduce and study the Non-Uniform k -Center (NUkC) problem. Given a finite metric space ( X , d ) and a collection of balls of radii { r 1 ≥ … ≥ r k }, the NUkC problem is to find a placement of their centers in the metric space and find the minimum dilation α, such that the union of balls of radius α ⋅ r i around the i th center covers all the points in X . This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds. The NUkC problem generalizes the classic k -center problem, wherein all the k radii are the same (which can be assumed to be 1 after scaling). It also generalizes the k -center with outliers (kCwO for short) problem, in which there are k balls of radius 1 and ℓ (number of outliers) balls of radius 0. Before this work, there was a 2-approximation and 3-approximation algorithm known for these problems, respectively; the former is best possible unless P=NP. We first observe that no O (1)-approximation to the optimal dilation is possible unless P=NP, implying that the NUkC problem is harder than the above two problems. Our main algorithmic result is an ( O (1), O (1))- bi-criteria approximation result: We give an O (1)-approximation to the optimal dilation; however, we may open Θ(1) centers of each radii. Our techniques also allow us to prove a simple (uni-criterion), optimal 2-approximation to the kCwO problem improving upon the long-standing 3-factor approximation for this problem. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees that have been studied recently in the TCS community. We show NUkC is at least as hard as the firefighter problem. While we do nt know whether the converse is true, we are able to adapt ideas from recent works [1, 3] in non-trivial ways to obtain our constant factor bi-criteria approximation.

Recently, Chakrabarty and Swamy (STOC 2019) introduced the {\em minimum-norm load-balancing} problem on unrelated machines, wherein we are given a set $J$ of jobs that need to be scheduled on a set of $m$ unrelated machines, and a monotone, symmetric norm; We seek an assignment $\sg:J\mapsto[m]$ that minimizes the norm of the resulting load vector $\lvec_\sg\in\R_+^m$, where $\lvec_\sg(i)$ is the load on machine $i$ under the assignment $\sg$. Besides capturing all $\ell_p$ norms, symmetric norms also capture other norms of interest including top-$\ell$ norms, and ordered norms. Chakrabarty and Swamy (STOC 2019) give a $(38+\ve)$-approximation algorithm for this problem via a general framework they develop for minimum-norm optimization that proceeds by first carefully reducing this problem (in a series of steps) to a problem called \minmax ordered load balancing, and then devising a so-called deterministic oblivious LP-rounding algorithm for ordered load balancing. We give a direct, and simple $4$-approximation algorithm for the minimum-norm load balancing based on rounding a (near-optimal) solution to a novel convex-programming relaxation for the problem. Whereas the natural convex program encoding minimum-norm load balancing problem has a large non-constant integrality gap, we show that this issue can be remedied by including a key constraint that bounds the "norm of the job-cost vector." Our techniques also yield a (essentially) $4$-approximation for: (a) {\em multi-norm load balancing}, wherein we are given multiple monotone symmetric norms, and we seek an assignment respecting a given budget for each norm; (b) the best {\em simultaneous approximation factor} achievable for all symmetric norms for a given instance.

In this paper we consider the classic matroid intersection problem: given two matroids M1= (V, I1) and M2= (V, I2) defined over a common ground set V , compute a set S ∈ I1∩ I2of largest possible cardinality, denoted by r. We consider this problem both in the setting where each Mi is accessed through an independence oracle, i.e. a routine which returns whether or not a set S ∈ Iiin Tindtime, and the setting where each Mi is accessed through a rank oracle, i.e. a routine which returns the size of the largest independent subset of S in Miin Tranktime. In each setting we provide faster exact and approximate algorithms. Given an independence oracle, we provide an exact O(nr log r · Tind) time algorithm. This improves upon previous best known running times of O(nr1.5·Tind) due to Cunningham O(n2·Tindin 1986 and + n3) due to Lee, Sidford, and Wong in 2015. We also provide two algorithms which compute a (1- ε-approximate solution to matroid intersection running in times O(n1.5/ε1.5· Tind) and O((n2r-1ε-2+ r1.5ε-4.5) · Tind), respectively. These results improve upon the O(nr/ε · Tind)time algorithm of Cunningham (noted recently by Chekuri and Quanrud). Given a rank oracle, we provide algorithms with even better dependence on n and r. We provide an O(n√r log n · Trank)time exact algorithm and an O(nε-1log n · Trank)-time algorithm which obtains a (1 - 0)-approximation to the matroid intersection problem. The former result improves over the O(nr · Trank+ n3)-time algorithm by Lee, Sidford, and Wong. The rank oracle is of particular interest as the matroid intersection problem with this oracle is a special case (via Edmond's minimax characterization of matroid intersection) of the submodular function minimization (SFM) problem with an evaluation oracle, and understanding SFM query complexity is an outstanding open question.

Testing monotonicity of a Boolean function f:{0,1}^n -> {0,1} is an important problem in the field of property testing. It has led to connections with many interesting combinatorial questions on the directed hypercube: routing, random walks, and new isoperimetric theorems. Denoting the proximity parameter by epsilon, the best tester is the non-adaptive O~(epsilon^{-2}sqrt{n}) tester of Khot-Minzer-Safra (FOCS 2015). A series of recent results by Belovs-Blais (STOC 2016) and Chen-Waingarten-Xie (STOC 2017) have led to Omega~(n^{1/3}) lower bounds for adaptive testers. Reducing this gap is a significant question, that touches on the role of adaptivity in monotonicity testing of Boolean functions. We approach this question from the perspective of parametrized property testing, a concept recently introduced by Pallavoor-Raskhodnikova-Varma (ACM TOCT 2017), where one seeks to understand performance of testers with respect to parameters other than just the size. Our result is an adaptive monotonicity tester with one-sided error whose query complexity is O(epsilon^{-2}I(f)log^5 n), where I(f) is the total influence of the function. Therefore, adaptivity provably helps monotonicity testing for low influence functions.

We study the problem of finding low-cost {\em fair clusterings} in data where each data point may belong to many protected groups. Our work significantly generalizes the seminal work of Chierichetti \etal (NIPS 2017) as follows. - We allow the user to specify the parameters that define fair representation. More precisely, these parameters define the maximum over- and minimum under-representation of any group in any cluster. - Our clustering algorithm works on any $\ell_p$-norm objective (e.g. $k$-means, $k$-median, and $k$-center). Indeed, our algorithm transforms any vanilla clustering solution into a fair one incurring only a slight loss in quality. - Our algorithm also allows individuals to lie in multiple protected groups. In other words, we do not need the protected groups to partition the data and we can maintain fairness across different groups simultaneously. Our experiments show that on established data sets, our algorithm performs much better in practice than what our theoretical results suggest.

In many optimization problems, a feasible solution induces a multi-dimensional cost vector. For example, in load-balancing a schedule induces a load vector across the machines. In k-clustering, opening k facilities induces an assignment cost vector across the clients. Typically, one seeks a solution which either minimizes the sum- or the max- of this vector, and these problems (makespan minimization, k-median, and k-center) are classic NP-hard problems which have been extensively studied.

We study the ℱ-center problem with outliers: Given a metric space ( X , d ), a general down-closed family ℱ of subsets of X , and a parameter m , we need to locate a subset S ∈ ℱ of centers such that the maximum distance among the closest m points in X to S is minimized. Our main result is a dichotomy theorem . Colloquially, we prove that there is an efficient 3-approximation for the ℱ-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over ℱ subject to a partition constraint. One concrete upshot of our result is a polynomial time 3-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.

We consider a generalization of $k$-median and $k$-center, called the {\em ordered $k$-median} problem. In this problem, we are given a metric space $(\mathcal{D},\{c_{ij}\})$ with $n=|\mathcal{D}|$ points, and a non-increasing weight vector $w\in\mathbb{R}_+^n$, and the goal is to open $k$ centers and assign each point each point $j\in\mathcal{D}$ to a center so as to minimize $w_1\cdot\text{(largest assignment cost)}+w_2\cdot\text{(second-largest assignment cost)}+\ldots+w_n\cdot\text{($n$-th largest assignment cost)}$. We give an $(18+ε)$-approximation algorithm for this problem. Our algorithms utilize Lagrangian relaxation and the primal-dual schema, combined with an enumeration procedure of Aouad and Segev. For the special case of $\{0,1\}$-weights, which models the problem of minimizing the $\ell$ largest assignment costs that is interesting in and of by itself, we provide a novel reduction to the (standard) $k$-median problem showing that LP-relative guarantees for $k$-median translate to guarantees for the ordered $k$-median problem; this yields a nice and clean $(8.5+ε)$-approximation algorithm for $\{0,1\}$ weights.

We design fast dynamic algorithms for proper vertex and edge colorings in a graph undergoing edge insertions and deletions. In the static setting, there are simple linear time algorithms for (Δ + 1)- vertex coloring and (2Δ – 1)-edge coloring in a graph with maximum degree Δ. It is natural to ask if we can efficiently maintain such colorings in the dynamic setting as well. We get the following three results. (1) We present a randomized algorithm which maintains a (Δ + 1)-vertex coloring with O(log Δ) expected amortized update time. (2) We present a deterministic algorithm which maintains a (1 + o(1)Δ-vertex coloring with O(polylog Δ) amortized update time. (3) We present a simple, deterministic algorithm which maintains a (2Δ – 1)-edge coloring with O(log Δ) worst-case update time. This improves the recent O(Δ)-edge coloring algorithm with worst-case update time [4].

We study monotonicity testing of Boolean functions over the hypergrid [n]d and design a non-adaptive tester with 1-sided error whose query complexity is Õ(d5/6). poly(log n, 1/ε). Previous to our work, the best known testers had query complexity linear in d but independent of n. We improve upon these testers as long as n = 2do(1). To obtain our results, we work with what we call the augmented hypergrid, which adds extra edges to the hypergrid. Our main technical contribution is a Margulis-style isoperimetric result for the augmented hypergrid, and our tester, like previous testers for the hypercube domain, performs directed random walks on this structure.

We present the first online algorithms for the nonuniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show (a) a polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs, (b) a quasi-polynomial time online algorithm with a polylogarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs, (c) for any fixed $\epsilon > 0$, a polynomial time online algorithm with a competitive ratio of $\tilde{O}\big(k^{\frac{1}{2}+\epsilon})$ (where $k$ is the number of demands, and the tilde hides polylog factors) for MC-BB in directed graphs, and (d) algorithms with matching competitive ratios for the prize-collecting variant of all the preceding problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs [B. Awerbuch and Y. Azar, FOCS, 1997, pp. 542--547], and a polylogarithmic-competitive algorithm was known for the edge-weighted single-sink problem [A. Meyerson, Procedings of SPAA, 2004, pp. 275--280]. We believe no online algorithm was known in the node-weighted and directed settings, even for uniform costs. Our main technical contribution is an online reduction theorem of MC-BB problems to their single-sink counterparts. We use the concept of junction-tree solutions from [C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, and M. R. Salavatipour, Proceedings of FOCS, 2006, pp. 677--686], which play an important role in solving the offline versions of the problem via a greedy subroutine---an inherently offline procedure. We use just the existence of good junction-trees for our reduction.

We study the problem of testing unateness of functions f:{0,1}^d -> R. We give an O(d/\epsilon . log(d/\epsilon))-query nonadaptive tester and an O(d/\epsilon)-query adaptive tester and show that both testers are optimal for a fixed distance parameter \epsilon. Previously known unateness testers worked only for Boolean functions, and their query complexity had worse dependence on the dimension both for the adaptive and the nonadaptive case. Moreover, no lower bounds for testing unateness were known. We generalize our results to obtain optimal unateness testers for functions f:[n]^d -> R. Our results establish that adaptivity helps with testing unateness of real-valued functions on domains of the form {0,1}^d and, more generally, [n]^d. This stands in contrast to the situation for monotonicity testing where there is no adaptivity gap for functions f:[n]^d -> R.

Submodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be solved in polynomial time. Owing to applications in computer vision and machine learning, fast SFM algorithms are highly desirable. The current fastest algorithms [Lee, Sidford, Wong, 2015] run in O(n2lognM· EO + n3logO(1)nM) time and O(n3log2n· EO +n4logO(1)n)time respectively, where M is the largest absolute value of the function (assuming the range is integers) and is the time taken to evaluate the function on any set. Although the best known lower bound on the query complexity is only Ω(n) [Harvey, 2008], the current shortest non-deterministic proof [Cunningham, 1985] certifying the optimum value of a function requires Ω(n2) function evaluations.

The primary problem in property testing is to decide whether a given function satisfies a certain property or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over theuniformdistribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this article, we provide simple and optimal testers forbounded derivative propertiesoverarbitrary product distributions. Bounded derivative properties include fundamental properties, such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing over arbitrary ranges. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show that this sum-of-depths is also a lower bound. A technical contribution of our work is anoptimal dimension reduction theoremfor all bounded derivative properties that relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity, and our theorem is an exponential improvement to the previous best-known result.

In this paper, we introduce and study the Non-Uniform k-Center problem (NUkC). Given a finite metric space $(X,d)$ and a collection of balls of radii $\{r_1\geq \cdots \ge r_k\}$, the NUkC problem is to find a placement of their centers on the metric space and find the minimum dilation $α$, such that the union of balls of radius $α\cdot r_i$ around the $i$th center covers all the points in $X$. This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds. The NUkC problem generalizes the classic $k$-center problem when all the $k$ radii are the same (which can be assumed to be $1$ after scaling). It also generalizes the $k$-center with outliers (kCwO) problem when there are $k$ balls of radius $1$ and $\ell$ balls of radius $0$. There are $2$-approximation and $3$-approximation algorithms known for these problems respectively; the former is best possible unless P=NP and the latter remains unimproved for 15 years. We first observe that no $O(1)$-approximation is to the optimal dilation is possible unless P=NP, implying that the NUkC problem is more non-trivial than the above two problems. Our main algorithmic result is an $(O(1),O(1))$-bi-criteria approximation result: we give an $O(1)$-approximation to the optimal dilation, however, we may open $Θ(1)$ centers of each radii. Our techniques also allow us to prove a simple (uni-criteria), optimal $2$-approximation to the kCwO problem improving upon the long-standing $3$-factor. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees which have been studied recently in the TCS community.

Interference in WiFi deployments is a growing problem due to the increasing popularity of WiFi. Therefore it is important that APs find the right channel to operate upon. Through a large scale measurement study involving over 10,000 WiFi APs we show that channel measurements and selection are most effective when performed frequently (every few minutes). This is because of the highly dynamic nature of WiFi traffic congestion. Our key contribution in this paper is a novel approach to distributed channel selection -- Ineffective time Quantum (IQ) Hopping, that is simple enough to be described in three lines and has provable optimality guarantees. IQ-Hopping does not require any explicit channel measurements and can react within a matter of several seconds to bad channel conditions, including microwave ovens, hidden interferers, or dynamically varying congestion. Through implementation and experiments on off-the-shelf WiFi routers (OpenWRT, MadWiFi), we demonstrate the effectiveness of IQ-Hopping.

We present the first non-trivial online algorithms for the non-uniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive ratios qualitatively match the best known approximation factors for the corresponding offline problems. In particular, we show:1. A polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected edge-weighted graphs.2. A quasi-polynomial time online algorithm with a poly-logarithmic competitive ratio for the MC-BB problem in undirected node-weighted graphs.3. For any fixed ε > 0, a polynomial time online algorithm with a competitive ratio of O̅(k{1/2+ε}polylog(n)) (where k is the number of demands) for MC-BB in directed graphs.4. Algorithms with matching competitive ratios for the prize-collecting variants of all the above problems. Prior to our work, a logarithmic competitive ratio was known for undirected, edge-weighted graphs only for the special case of uniform costs (Awerbuch and Azar, FOCS 1997), and a polylogarithmic competitive ratio was known for the edge-weighted single-sink problem (Meyerson, SPAA 2004). To the best of our knowledge, no previous online algorithm was known, even for uniform costs, in the node-weighted and directed settings. Our main engine for the results above is an online reduction theorem of MC-BB problems to their single-sink (SS-BB) counterparts. We use the concept of junction-tree solutions (Chekuri et al., FOCS 2006) that play an important role in solving the offline versions of the problem via a greedy subroutine -- an inherently offline procedure. Our main technical contribution is in designing an online algorithm using only the existence of good junction-trees to reduce an MC-BB instance to multiple SS-BB sub-instances. Along the way, we also give the first non-trivial online node-weighted/directed single-sink buy-at-bulk algorithms. In addition to the new results, our generic reduction also yields new proofs of recent results for the online node-weighted Steiner forest and online group Steiner forest problems.

The primary problem in property testing is to decide whether a given function satisfies a certain property, or is far from any function satisfying it. This crucially requires a notion of distance between functions. The most prevalent notion is the Hamming distance over the uniform distribution on the domain. This restriction to uniformity is rather limiting, and it is important to investigate distances induced by more general distributions. In this paper, we give simple and optimal testers for bounded derivative properties over arbitrary product distributions. Bounded derivative properties include fundamental properties such as monotonicity and Lipschitz continuity. Our results subsume almost all known results (upper and lower bounds) on monotonicity and Lipschitz testing. We prove an intimate connection between bounded derivative property testing and binary search trees (BSTs). We exhibit a tester whose query complexity is the sum of expected depths of optimal BSTs for each marginal. Furthermore, we show this sum-of-depths is also a lower bound. A technical contribution of our work is an optimal dimension reduction theorem for all bounded derivative properties, which relates the distance of a function from the property to the distance of restrictions of the function to random lines. Such a theorem has been elusive even for monotonicity, and our theorem is an exponential improvement to the previous best known result.

Makespan minimization on unrelated machines is a classic problem in approximation algorithms. No polynomial time (2 – δ)-approximation algorithm is known for the problem for constant δ > 0. This is true even for certain special cases, most notably the restricted assignment problem where each job has the same load on any machine but can be assigned to one from a specified subset. Recently in a breakthrough result, Svensson [16] proved that the integrality gap of a certain configuration LP relaxation is upper bounded by 1.95 for the restricted assignment problem; however, the rounding algorithm is not known to run in polynomial time. In this paper we consider the (1, ε)-restricted assignment problem where each job is either heavy (pj = 1) or light (pj = ε), for some parameter ε > 0. Our main result is a (2 – δ)-approximate polynomial time algorithm for the (1, ε)-restricted assignment problem for a fixed constant δ > 0. Even for this special case, the best polynomial-time approximation factor known so far is 2. We obtain this result by rounding the configuration LP relaxation for this problem. A simple reduction from vertex cover shows that this special case remains NP-hard to approximate to within a factor better than 7/6.

A coverage function $f$ over a ground set $[m]$ is associated with a universe $U$ of weighted elements and $m$ sets $A_1,\ldots,A_m \subseteq U$, and for any $T\subseteq [m]$, $f(T)$ is defined as the total weight of the elements in the union $\cup_{j\in T} A_j$. Coverage functions are an important special case of submodular functions, and arise in many applications, for instance, as a class of utility functions of agents in combinatorial auctions. Naïve representations of coverage functions have size exponential in $m$, and in algorithmic applications, an access to a value oracle is assumed. In this paper, we ask whether one can recognize if a given oracle is that of a coverage function or not. We demonstrate an algorithm which makes $O(m|U|)$ queries to an oracle of a coverage function and completely reconstructs it. This is polynomial time whenever $|U|$ is polynomially bounded implying the function has a succinct description. To complement the above result, we show a negative result. We prove that “noncoverageness” needs large certificates---there exists a function which is not coverage and yet any algorithm making fewer than $2^{m-1}$ queries cannot distinguish this function from some coverage function. Our positive result shows that the property of coverageness has $O(m|U|)$-query proximity oblivious testers, while our negative result shows an exponential lower bound. We believe our lower bound also goes through for general property testers, and provide some evidence of the same.

In this paper, we study mechanism design problems in the ordinal setting wherein the preferences of agents are described by orderings over outcomes, as opposed to specific numerical values associated with them. This setting is relevant when agents can compare outcomes, but aren't able to evaluate precise utilities for them. Such a situation arises in diverse contexts including voting and matching markets.

Motivated by the recent work of [V. V. Vazirani, J. ACM, 59 (2012), 7], we take a fresh look at understanding the quality and robustness of solutions to Nash and nonsymmetric bargaining games by subjecting them to several stress tests. Our tests are quite basic; e.g., we ask whether the solutions are computable in polynomial time, and whether they have certain properties such as efficiency, fairness, and desirable response when agents change their disagreement points or play with a subset of the agents. Our main conclusion is that imposing submodularity, a natural economies of scale condition, on Nash and nonsymmetric bargaining games endows them with several desirable properties.

In Internet ad auctions, search engines often throttle budget constrained advertisers so as to spread their spends across the specified time period. Such policies are known as budget smoothing policies. In this paper, we perform a principled, game-theoretic study of what the outcome of an ideal budget smoothing algorithm should be. In particular, we propose the notion of regret-free budget smoothing policies whose outcomes throttle each advertiser optimally, given the participation of the other advertisers. We show that regret-free budget smoothing policies always exist, and in the case of single slot auctions we can give a polynomial time smoothing algorithm. Inspired by the existence proof, we design a heuristic for budget smoothing which performs considerably better than existing benchmark heuristics.

Given oracle access to a Boolean function f:{0,1}n -> {0,1}, we design a randomized tester that takes as input a parameter ε>0, and outputs Yes if the function is monotonically non-increasing, and outputs No with probability >2/3, if the function is ε-far from being monotone, that is, f needs to be modified at ε-fraction of the points to make it monotone. Our non-adaptive, one-sided tester makes ~O(n5/6ε-5/3) queries to the oracle.

The problem of monotonicity testing over the hypergrid and its special case, the hypercube, is a classic question in property testing. We are given query access to f:[k]n -> R (for some ordered range R). The hypergrid/cube has a natural partial order given by coordinate-wise ordering, denoted by prec. A function is monotone if for all pairs x prec y, f(x) ≤ f(y). The distance to monotonicity, εf, is the minimum fraction of values of f that need to be changed to make f monotone. For k=2 (the boolean hypercube), the usual tester is the edge tester, which checks monotonicity on adjacent pairs of domain points. It is known that the edge tester using O(ε-1n log|R|) samples can distinguish a monotone function from one where εf > ε. On the other hand, the best lower bound for monotonicity testing over general R is Ω(n). We resolve this long standing open problem and prove that O(n/ε) samples suffice for the edge tester. For hypergrids, known testers require O(ε-1n log k log |R|) samples, while the best known (non-adaptive) lower bound is Ω(ε-1 n log k). We give a (non-adaptive) monotonicity tester for hypergrids running in O(ε{-1} n log k) time.

In this paper we prove new properties of hypergraphic linear programming relaxations for the Steiner tree problem. In particular, we show that a partition-based relaxation has the same value as other relaxations based on subtours and directed cuts. Additionally, we establish structural properties of basic solutions by using uncrossing methods. For quasi-bipartite instances we show that these hypergraphic relaxations have the same value as the well-studied graphic bidirected cut relaxation. We show how to analyze several approximation algorithms relative to the hypergraphic linear programs; one gives an approximation ratio and integrality gap of at most $\sqrt{3} \simeq 1.729$ for the Steiner tree problem when the full components arrive online.

In this paper we consider the following maximum budgeted allocation (MBA) problem: Given a set of m indivisible items and n agents, with each agent i willing to pay $b_{ij}$ on item j and with a maximum budget of $B_i$, the goal is to allocate items to agents to maximize revenue. The problem naturally arises as auctioneer revenue maximization in budget-constrained auctions and as the winner determination problem in combinatorial auctions when utilities of agents are budgeted-additive. Our main results are as follows: (i) We give a $3/4$-approximation algorithm for MBA improving upon the previous best of $\simeq0.632$ [N. Andelman and Y. Mansour, Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), 2004, pp. 26–38], [J. Vondrák, Proceedings of the 40th Annual ACM Symposium on the Theory of Computing (STOC), 2008, pp. 67–74] (also implied by the result of [U. Feige and J. Vondrák, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667–676]). Our techniques are based on a natural LP relaxation of MBA, and our factor is optimal in the sense that it matches the integrality gap of the LP. (ii) We prove it is NP-hard to approximate MBA to any factor better than $15/16$; previously only NP-hardness was known [T. Sandholm and S. Suri, Games Econom. Behav., 55 (2006), pp. 321–330], [B. Lehmann, D. Lehmann, and N. Nisan, Proceedings of the 3rd ACM Conference on Electronic Commerce (EC), 2001, pp. 18–28]. Our result also implies NP-hardness of approximating maximum submodular welfare with demand oracle to a factor better than $15/16$, improving upon the best known hardness of $275/276$ [U. Feige and J. Vondrák, Proceedings of the 47th IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 667–676]. (iii) Our hardness techniques can be modified to prove that it is NP-hard to approximate the generalized assignment problem (GAP) to any factor better than $10/11$. This improves upon the $422/423$ hardness of [C. Chekuri and S. Khanna, Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2000, pp. 213–222], [M. Chlebík and J. Chlebíková, Proceedings of the 8th Scandinavian Workshop on Algorithm Theory (SWAT), 2002, pp. 170–179]. We use iterative rounding on a natural LP relaxation of the MBA problem to obtain the $3/4$-approximation. We also give a $(3/4-\epsilon)$-factor algorithm based on the primal-dual schema which runs in $\tilde{O}(nm)$ time, for any constant $\epsilon>0$.

Inspired by the convex program of Eisenberg and Gale which captures Fisher markets with linear utilities, Jain and Vazirani [K. Jain and V. V. Vazirani, Games and Economic Behavior, 70 (2010), pp. 84–106] introduced the class of Eisenberg–Gale (EG) markets. We study the structure of EG(2) markets, the class of EG markets with two agents. We prove that all markets in this class are rational, that is, they have rational equilibrium, and they admit strongly polynomial time algorithms whenever the polytope containing the set of feasible utilities of the two agents can be described via a combinatorial linear program (LP). This helps positively resolve the status of two markets left as open problems by Jain and Vazirani: the capacity allocation market in a directed graph with two source-sink pairs and the network coding market in a directed network with two sources. Our algorithms for solving the corresponding nonlinear convex programs are fundamentally different from those obtained by Jain and Vazirani; whereas they use the primal-dual schema, our main tool is binary search powered by the strong LP-duality theorem.

We consider the class of max-min and min-max optimization problems subject to a global budget constraint. We undertake a systematic algorithmic and complexity-theoretic study of such problems, which we call design problems. Every optimization problem leads to a natural design problem. Our main result uses techniques of Freund and Schapire [Games Econom. Behav., 29 (1999), pp. 79–103] from learning theory, and its generalizations, to show that for a large class of optimization problems, the design version is as easy as the optimization version. We also observe the relationship between max-min design problems and fractional packing problems. In particular, we obtain in a systematic fashion results about the fractional packing number of Steiner trees.

We consider the Max-Min Allocation problem: given a set A of m agents and a set I of n items, where agent A ¿ A has utility uA,i for item i ¿ I, our goal is to allocate items to agents so as to maximize fairness. Specifically, the utility of an agent is the sum of its utilities for the items it receives, and we seek to maximize the minimum utility of any agent. While this problem has received much attention recently, its approximability has not been well-understood thus far: the best known approximation algorithm achieves an O¿(¿m)-approximation, and in contrast, the best known hardness of approximation stands at 2. Our main result is an algorithm that achieves an O¿(n¿)-approximation for any ¿ = ¿((log log n)/(log n)) in time nO(1/¿). In particular, we obtain poly-logarithmic approximation in quasipolynomial time, and for every constant ¿ > 0, we obtain an O¿(n¿)-approximation in polynomial time. An interesting technical aspect of our algorithm is that we use as a building block a linear program whose integrality gap is ¿(¿m). We bypass this obstacle by iteratively using the solutions produced by the LP to construct new instances with significantly smaller integrality gaps, eventually obtaining the desired approximation. As a corollary of our main result, we also show that for any constant ¿ > 0, an O(m¿)-approximation can be achieved in quasi-polynomial time. We also investigate the special case of the problem, where every item has non-zero utility for at most two agents. This problem is hard to approximate up to any factor better than 2. We give a factor 2-approximation algorithm.

Message Ferrying is a mobility assisted technique for working around the disconnectedness and sparsity of Mobile ad hoc networks. One of the importantquestions which arise in this context is to determine the routing of the ferry,so as to minimize the buffers used to store data at the nodes in thenetwork. We introduce a simple model to capture the ferry routingproblem. We characterize {\em stable} solutions of the system andprovide efficient approximation algorithms for the {\sc Min-Max Buffer Problem} for the case when the nodes are onhierarchically separated metric spaces.

In this paper we consider the following maximum budgeted allocation (MBA) problem: Given a set of m indivisible items and n agents; each agent i willing to pay bijon item j and with a maximum budget of Bi, the goal is to allocate items to agents to maximize revenue. The problem naturally arises as auctioneer revenue maximization in budget-constrained auctions and as winner determination problem in combinatorial auctions when utilities of agents are budgeted-additive.We give a 3/4-approximation algorithm for MBA improving upon the previous best of sime0.632[2, 10]. Our techniques are based on a natural LP relaxation of MBA and our factor is optimal in the sense that it matches the integrality gap of the LP.We prove it is NP-hard to approximate MBA to any factor better than 15/16, previously only NP-hardness was known [21, 17]. Our result also implies NP- hardness of approximating maximum submodular welfare with demand oracle to a factor better than 15/16, improving upon the best known hardness of 275/276[10].Our hardness techniques can be modified to prove that it is NP-hard to approximate the Generalized Assignment Problem (GAP) to any factor better than 10/11. This improves upon the 422/423 hardness of [7, 9].We use iterative rounding on a natural LP relaxation of MBA to obtain the 3/4-approximation. We also give a (3/4 - epsiv) -factor algorithm based on the primal-dual schema which runs in O(nm) time, for any constant epsiv > 0.

We consider the budget-constrained bidding optimization problem for sponsored search auctions, and model it as an online (multiple-choice) knapsack problem. We design both deterministic and randomized algorithms for the online (multiple-choice) knapsack problems achieving a provably optimal competitive ratio. This translates back to fully automatic bidding strategies maximizing either profit or revenue for the budget-constrained advertiser. Our bidding strategy for revenue maximization is oblivious (i.e., without knowledge) of other bidders' prices and/or click-through-rates for those positions. We evaluate our bidding algorithms using both synthetic data and real bidding data gathered manually, and also discuss a sniping heuristic that strictly improves bidding performance. With sniping and parameter tuning enabled, our bidding algorithms can achieve a performance ratio above 90% against the optimum by the omniscient bidder.

We study two problems, that of computing social optimum and that of finding fair allocations, in the congestion game model of Milchtaich[8] Although we show that the general problem is hard to approximate to any factor, we give simple algorithms for natural simplifications. We also consider these problems in the symmetric network congestion game model [11, 4], and show hardness results and approximate solutions.