BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Chaitanya Swamy

Chaitanya Swamy appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputer Science and Game TheoryDiscrete MathematicsMachine Learning

Catalog footprint

What is connected

20works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

20 published item(s)

preprint2020arXiv

A Constant-Factor Approximation for Directed Latency in Quasi-Polynomial Time

We give the first constant-factor approximation for the Directed Latency problem in quasi-polynomial time. Here, the goal is to visit all nodes in an asymmetric metric with a single vehicle starting at a depot $r$ to minimize the average time a node waits to be visited by the vehicle. The approximation guarantee is an improvement over the polynomial-time $O(\log n)$-approximation [Friggstad, Salavatipour, Svitkina, 2013] and no better quasi-polynomial time approximation algorithm was known. To obtain this, we must extend a recent result showing the integrality gap of the Asymmetric TSP-Path LP relaxation is bounded by a constant [Köhne, Traub, and Vygen, 2019], which itself builds on the breakthrough result that the integrality gap for standard Asymmetric TSP is also a constant [Svensson, Tarnawsi, and Vegh, 2018]. We show the standard Asymmetric TSP-Path integrality gap is bounded by a constant even if the cut requirements of the LP relaxation are relaxed from $x(δ^{in}(S)) \geq 1$ to $x(δ^{in}(S)) \geq ρ$ for some constant $1/2 < ρ\leq 1$. We also give a better approximation guarantee in the special case of Directed Latency in regret metrics where the goal is to find a path $P$ minimize the average time a node $v$ waits in excess of $c_{rv}$, i.e. $\frac{1}{|V|} \cdot \sum_{v \in V} (c_v(P)-c_{rv})$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximating Min-Cost Chain-Constrained Spanning Trees: A Reduction from Weighted to Unweighted Problems

We study the {\em min-cost chain-constrained spanning-tree} (abbreviated \mcst) problem: find a min-cost spanning tree in a graph subject to degree constraints on a nested family of node sets. We devise the {\em first} polytime algorithm that finds a spanning tree that (i) violates the degree constraints by at most a constant factor {\em and} (ii) whose cost is within a constant factor of the optimum. Previously, only an algorithm for {\em unweighted} \cst was known \cite{olver}, which satisfied (i) but did not yield any cost bounds. This also yields the first result that obtains an $O(1)$-factor for {\em both} the cost approximation and violation of degree constraints for any spanning-tree problem with general degree bounds on node sets, where an edge participates in a super-constant number of degree constraints. A notable feature of our algorithm is that we {\em reduce} \mcst to unweighted \cst (and then utilize \cite{olver}) via a novel application of {\em Lagrangian duality} to simplify the {\em cost structure} of the underlying problem and obtain a decomposition into certain uniform-cost subproblems. We show that this Lagrangian-relaxation based idea is in fact applicable more generally and, for any cost-minimization problem with packing side-constraints, yields a reduction from the weighted to the unweighted problem. We believe that this reduction is of independent interest. As another application of our technique, we consider the {\em $k$-budgeted matroid basis} problem, where we build upon a recent rounding algorithm of \cite{BansalN16} to obtain an improved $n^{O(k^{1.5}/ε)}$-time algorithm that returns a solution that satisfies (any) one of the budget constraints exactly and incurs a $(1+ε)$-violation of the other budget constraints.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers

We consider clustering problems with {\em non-uniform lower bounds and outliers}, and obtain the {\em first approximation guarantees} for these problems. We have a set $\F$ of facilities with lower bounds $\{L_i\}_{i\in\F}$ and a set $\D$ of clients located in a common metric space $\{c(i,j)\}_{i,j\in\F\cup\D}$, and bounds $k$, $m$. A feasible solution is a pair $\bigl(S\sse\F,σ:\D\mapsto S\cup\{\mathsf{out}\}\bigr)$, where $σ$ specifies the client assignments, such that $|S|\leq k$, $|σ^{-1}(i)|\geq L_i$ for all $i\in S$, and $|σ^{-1}(\mathsf{out})|\leq m$. In the {\em lower-bounded min-sum-of-radii with outliers} (\lbksro) problem, the objective is to minimize $\sum_{i\in S}\max_{j\inσ^{-1}(i)}c(i,j)$, and in the {\em lower-bounded $k$-supplier with outliers} (\lbkso) problem, the objective is to minimize $\max_{i\in S}\max_{j\inσ^{-1}(i)}c(i,j)$. We obtain an approximation factor of $12.365$ for \lbksro, which improves to $3.83$ for the non-outlier version (i.e., $m=0$). These also constitute the {\em first} approximation bounds for the min-sum-of-radii objective when we consider lower bounds and outliers {\em separately}. We apply the primal-dual method to the relaxation where we Lagrangify the $|S|\leq k$ constraint. The chief technical contribution and novelty of our algorithm is that, departing from the standard paradigm used for such constrained problems, we obtain an $O(1)$-approximation {\em despite the fact that we do not obtain a Lagrangian-multiplier-preserving algorithm for the Lagrangian relaxation}. We believe that our ideas have {broader applicability to other clustering problems with outliers as well.} We obtain approximation factors of $5$ and $3$ respectively for \lbkso and its non-outlier version. These are the {\em first} approximation results for $k$-supplier with {\em non-uniform} lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Hardness Results for Signaling in Bayesian Zero-Sum and Network Routing Games

We study the optimization problem faced by a perfectly informed principal in a Bayesian game, who reveals information to the players about the state of nature to obtain a desirable equilibrium. This signaling problem is the natural design question motivated by uncertainty in games and has attracted much recent attention. We present new hardness results for signaling problems in (a) Bayesian two-player zero-sum games, and (b) Bayesian network routing games. For Bayesian zero-sum games, when the principal seeks to maximize the equilibrium utility of a player, we show that it is NP-hard to obtain an additive FPTAS. Our hardness proof exploits duality and the equivalence of separation and optimization in a novel way. Further, we rule out an additive PTAS assuming planted clique hardness, which states that no polynomial time algorithm can recover a planted clique from an Erdős-Rényi random graph. Complementing these, we obtain a PTAS for a structured class of zero-sum games (where obtaining an FPTAS is still NP-hard) when the payoff matrices obey a Lipschitz condition. Previous results ruled out an FPTAS assuming planted-clique hardness, and a PTAS only for implicit games with quasi-polynomial-size strategy sets. For Bayesian network routing games, wherein the principal seeks to minimize the average latency of the Nash flow, we show that it is NP-hard to obtain a (multiplicative) $(4/3 - ε)$-approximation, even for linear latency functions. This is the optimal inapproximability result for linear latencies, since we show that full revelation achieves a $(4/3)$-approximation for linear latencies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications

We consider the {\em matroid median} problem \cite{KrishnaswamyKNSS11}, wherein we are given a set of facilities with opening costs and a matroid on the facility-set, and clients with demands and connection costs, and we seek to open an independent set of facilities and assign clients to open facilities so as to minimize the sum of the facility-opening and client-connection costs. We give a simple 8-approximation algorithm for this problem based on LP-rounding, which improves upon the 16-approximation in \cite{KrishnaswamyKNSS11}. Our techniques illustrate that much of the work involved in the rounding algorithm of in \cite{KrishnaswamyKNSS11} can be avoided by first converting the LP solution to a half-integral solution, which can then be rounded to an integer solution using a simple uncapacitated-facility-location (UFL) style clustering step. We illustrate the power of these ideas by deriving: (a) a 24-approximation algorithm for matroid median with penalties, which is a vast improvement over the 360-approximation obtained in \cite{KrishnaswamyKNSS11}; and (b) an 8-approximation for the {\em two-matroid median} problem, a generalization of matroid median that we introduce involving two matroids. We show that a variety of seemingly disparate facility-location problems considered in the literature---data placement problem, mobile facility location, $k$-median forest, metric uniform minimum-latency UFL---in fact reduce to the matroid median or two-matroid median problems, and thus obtain improved approximation guarantees for all these problems. Our techniques also yield an improvement for the knapsack median problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Near-Optimal and Robust Mechanism Design for Covering Problems with Correlated Players

We consider the problem of designing incentive-compatible, ex-post individually rational (IR) mechanisms for covering problems in the Bayesian setting, where players' types are drawn from an underlying distribution and may be correlated, and the goal is to minimize the expected total payment made by the mechanism. We formulate a notion of incentive compatibility (IC) that we call {\em support-based IC} that is substantially more robust than Bayesian IC, and develop black-box reductions from support-based-IC mechanism design to algorithm design. For single-dimensional settings, this black-box reduction applies even when we only have an LP-relative {\em approximation algorithm} for the algorithmic problem. Thus, we obtain near-optimal mechanisms for various covering settings including single-dimensional covering problems, multi-item procurement auctions, and multidimensional facility location.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Computing Optimal Tolls in Routing Games without Knowing the Latency Functions

We consider the following question: in a nonatomic routing game, can the tolls that induce the minimum latency flow be computed without knowing the latency functions? Since the latency functions are unknown, we assume we are given an oracle that has access to the underlying routing game. A query to the oracle consists of tolls on edges, and the response is the resulting equilibrium flow. We show that in this model, it is impossible to obtain optimal tolls. However, if we augment the oracle so that it returns the total latency of the equilibrium flow induced by the tolls in addition to the flow itself, then the required tolls can be computed with a polynomial number of queries.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Learning Arbitrary Statistical Mixtures of Discrete Distributions

We study the problem of learning from unlabeled samples very general statistical mixture models on large finite sets. Specifically, the model to be learned, $\vartheta$, is a probability distribution over probability distributions $p$, where each such $p$ is a probability distribution over $[n] = \{1,2,\dots,n\}$. When we sample from $\vartheta$, we do not observe $p$ directly, but only indirectly and in very noisy fashion, by sampling from $[n]$ repeatedly, independently $K$ times from the distribution $p$. The problem is to infer $\vartheta$ to high accuracy in transportation (earthmover) distance. We give the first efficient algorithms for learning this mixture model without making any restricting assumptions on the structure of the distribution $\vartheta$. We bound the quality of the solution as a function of the size of the samples $K$ and the number of samples used. Our model and results have applications to a variety of unsupervised learning scenarios, including learning topic models and collaborative filtering.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Achieving Target Equilibria in Network Routing Games without Knowing the Latency Functions

The analysis of network routing games typically assumes, right at the onset, precise and detailed information about the latency functions. Such information may, however, be unavailable or difficult to obtain. Moreover, one is often primarily interested in enforcing a desired target flow as the equilibrium by suitably influencing player behavior in the routing game. We ask whether one can achieve target flows as equilibria without knowing the underlying latency functions. Our main result gives a crisp positive answer to this question. We show that, under fairly general settings, one can efficiently compute edge tolls that induce a given target multicommodity flow in a nonatomic routing game using a polynomial number of queries to an oracle that takes candidate tolls as input and returns the resulting equilibrium flow. This result is obtained via a novel application of the ellipsoid method. Our algorithm extends easily to many other settings, such as (i) when certain edges cannot be tolled or there is an upper bound on the total toll paid by a user, and (ii) general nonatomic congestion games. We obtain tighter bounds on the query complexity for series-parallel networks, and single-commodity routing games with linear latency functions, and complement these with a query-complexity lower bound. We also obtain strong positive results for Stackelberg routing to achieve target equilibria in series-parallel graphs. Our results build upon various new techniques that we develop pertaining to the computation of, and connections between, different notions of approximate equilibrium; properties of multicommodity flows and tolls in series-parallel graphs; and sensitivity of equilibrium flow with respect to tolls. Our results demonstrate that one can indeed circumvent the potentially-onerous task of modeling latency functions, and yet obtain meaningful results for the underlying routing game.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Improved Region-Growing and Combinatorial Algorithms for $k$-Route Cut Problems

We study the {\em $k$-route} generalizations of various cut problems, the most general of which is \emph{$k$-route multicut} ($k$-MC) problem, wherein we have $r$ source-sink pairs and the goal is to delete a minimum-cost set of edges to reduce the edge-connectivity of every source-sink pair to below $k$. The $k$-route extensions of multiway cut ($k$-MWC), and the minimum $s$-$t$ cut problem ($k$-$(s,t)$-cut), are similarly defined. We present various approximation and hardness results for these $k$-route cut problems that improve the state-of-the-art for these problems in several cases. (i) For {\em $k$-route multiway cut}, we devise simple, but surprisingly effective, combinatorial algorithms that yield bicriteria approximation guarantees that markedly improve upon the previous-best guarantees. (ii) For {\em $k$-route multicut}, we design algorithms that improve upon the previous-best approximation factors by roughly an $O(\sqrt{\log r})$-factor, when $k=2$, and for general $k$ and unit costs and any fixed violation of the connectivity threshold $k$. The main technical innovation is the definition of a new, powerful \emph{region growing} lemma that allows us to perform region-growing in a recursive fashion even though the LP solution yields a {\em different metric} for each source-sink pair. (iii) We complement these results by showing that the {\em $k$-route $s$-$t$ cut} problem is at least as hard to approximate as the {\em densest-$k$-subgraph} (DkS) problem on uniform hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Linear-Programming based Approximation Algorithms for Multi-Vehicle Minimum Latency Problems

We consider various {\em multi-vehicle versions of the minimum latency problem}. There is a fleet of $k$ vehicles located at one or more depot nodes, and we seek a collection of routes for these vehicles that visit all nodes so as to minimize the total latency incurred, which is the sum of the client waiting times. We obtain an $8.497$-approximation for the version where vehicles may be located at multiple depots and a $7.183$-approximation for the version where all vehicles are located at the same depot, both of which are the first improvements on this problem in a decade. Perhaps more significantly, our algorithms exploit various LP-relaxations for minimum-latency problems. We show how to effectively leverage two classes of LPs---{\em configuration LPs} and {\em bidirected LP-relaxations}---that are often believed to be quite powerful but have only sporadically been effectively leveraged for network-design and vehicle-routing problems. This gives the first concrete evidence of the effectiveness of LP-relaxations for this class of problems. The $8.497$-approximation the multiple-depot version is obtained by rounding a near-optimal solution to an underlying configuration LP for the problem. The $7.183$-approximation can be obtained both via rounding a bidirected LP for the single-depot problem or via more combinatorial means. The latter approach uses a bidirected LP to obtain the following key result that is of independent interest: for any $k$, we can efficiently compute a rooted tree that is at least as good, with respect to the prize-collecting objective (i.e., edge cost + number of uncovered nodes) as the best collection of $k$ rooted paths. Our algorithms are versatile and extend easily to handle various extensions involving: (i) weighted sum of latencies, (ii) constraints specifying which depots may serve which nodes, (iii) node service times.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Welfare Maximization and Truthfulness in Mechanism Design with Ordinal Preferences

We study mechanism design problems in the {\em 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. Our paper addresses two issues that arise in ordinal mechanism design. To design social welfare maximizing mechanisms, one needs to be able to quantitatively measure the welfare of an outcome which is not clear in the ordinal setting. Second, since the impossibility results of Gibbard and Satterthwaite~\cite{Gibbard73,Satterthwaite75} force one to move to randomized mechanisms, one needs a more nuanced notion of truthfulness. We propose {\em rank approximation} as a metric for measuring the quality of an outcome, which allows us to evaluate mechanisms based on worst-case performance, and {\em lex-truthfulness} as a notion of truthfulness for randomized ordinal mechanisms. Lex-truthfulness is stronger than notions studied in the literature, and yet flexible enough to admit a rich class of mechanisms {\em circumventing classical impossibility results}. We demonstrate the usefulness of the above notions by devising lex-truthful mechanisms achieving good rank-approximation factors, both in the general ordinal setting, as well as structured settings such as {\em (one-sided) matching markets}, and its generalizations, {\em matroid} and {\em scheduling} markets.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximation Algorithms for Non-Single-minded Profit-Maximization Problems with Limited Supply

We consider {\em profit-maximization} problems for {\em combinatorial auctions} with {\em non-single minded valuation functions} and {\em limited supply}. We obtain fairly general results that relate the approximability of the profit-maximization problem to that of the corresponding {\em social-welfare-maximization} (SWM) problem, which is the problem of finding an allocation $(S_1,\ldots,S_n)$ satisfying the capacity constraints that has maximum total value $\sum_j v_j(S_j)$. For {\em subadditive valuations} (and hence {\em submodular, XOS valuations}), we obtain a solution with profit $\OPT_\swm/O(\log c_{\max})$, where $\OPT_\swm$ is the optimum social welfare and $c_{\max}$ is the maximum item-supply; thus, this yields an $O(\log c_{\max})$-approximation for the profit-maximization problem. Furthermore, given {\em any} class of valuation functions, if the SWM problem for this valuation class has an LP-relaxation (of a certain form) and an algorithm "verifying" an {\em integrality gap} of $\al$ for this LP, then we obtain a solution with profit $\OPT_\swm/O(\al\log c_{\max})$, thus obtaining an $O(\al\log c_{\max})$-approximation. For the special case, when the tree is a path, we also obtain an incomparable $O(\log m)$-approximation (via a different approach) for subadditive valuations, and arbitrary valuations with unlimited supply. Our approach for the latter problem also gives an $\frac{e}{e-1}$-approximation algorithm for the multi-product pricing problem in the Max-Buy model, with limited supply, improving on the previously known approximation factor of 2.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Approximation Algorithms for Regret-Bounded Vehicle Routing and Applications to Distance-Constrained Vehicle Routing

We consider vehicle-routing problems (VRPs) that incorporate the notion of {\em regret} of a client, which is a measure of the waiting time of a client relative to its shortest-path distance from the depot. Formally, we consider both the additive and multiplicative versions of, what we call, the {\em regret-bounded vehicle routing problem} (RVRP). In these problems, we are given an undirected complete graph $G=(\{r\}\cup V,E)$ on $n$ nodes with a distinguished root (depot) node $r$, edge costs $\{c_{uv}\}$ that form a metric, and a regret bound $R$. Given a path $P$ rooted at $r$ and a node $v\in P$, let $c_P(v)$ be the distance from $r$ to $v$ along $P$. The goal is to find the fewest number of paths rooted at $r$ that cover all the nodes so that for every node $v$ covered by (say) path $P$: (i) its additive regret $c_P(v)-c_{rv}$, with respect to $P$ is at most $R$ in {\em additive-RVRP}; or (ii) its multiplicative regret, $c_P(c)/c_{rv}$, with respect to $P$ is at most $R$ in {\em multiplicative-RVRP}. Our main result is the {\em first} constant-factor approximation algorithm for additive-RVRP by devising rounding techniques for a natural {\em configuration-style LP}. This is a substantial improvement over the previous-best $O(\log n)$-approximation. Additive-RVRP turns out be a rather central vehicle-routing problem, whose study reveals insights into a variety of other regret-related problems as well as the classical {\em distance-constrained VRP} ({DVRP}). We obtain approximation ratios of $O\bigl(\log(\frac{R}{R-1})\bigr)$ for multiplicative-RVRP, and $O\bigl(\min\bigl\{\mathit{OPT},\frac{\log D}{\log\log D}\bigr\}\bigr)$ for DVRP with distance bound $D$ via reductions to additive-RVRP; the latter improves upon the previous-best approximation for DVRP.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Learning Mixtures of Arbitrary Distributions over Large Discrete Domains

We give an algorithm for learning a mixture of {\em unstructured} distributions. This problem arises in various unsupervised learning scenarios, for example in learning {\em topic models} from a corpus of documents spanning several topics. We show how to learn the constituents of a mixture of $k$ arbitrary distributions over a large discrete domain $[n]=\{1,2,\dots,n\}$ and the mixture weights, using $O(n\polylog n)$ samples. (In the topic-model learning setting, the mixture constituents correspond to the topic distributions.) This task is information-theoretically impossible for $k>1$ under the usual sampling process from a mixture distribution. However, there are situations (such as the above-mentioned topic model case) in which each sample point consists of several observations from the same mixture constituent. This number of observations, which we call the {\em "sampling aperture"}, is a crucial parameter of the problem. We obtain the {\em first} bounds for this mixture-learning problem {\em without imposing any assumptions on the mixture constituents.} We show that efficient learning is possible exactly at the information-theoretically least-possible aperture of $2k-1$. Thus, we achieve near-optimal dependence on $n$ and optimal aperture. While the sample-size required by our algorithm depends exponentially on $k$, we prove that such a dependence is {\em unavoidable} when one considers general mixtures. A sequence of tools contribute to the algorithm, such as concentration results for random matrices, dimension reduction, moment estimations, and sensitivity analysis.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Local-Search based Approximation Algorithms for Mobile Facility Location Problems

We consider the {\em mobile facility location} (\mfl) problem. We are given a set of facilities and clients located in a common metric space. The goal is to move each facility from its initial location to a destination and assign each client to the destination of some facility so as to minimize the sum of the movement-costs of the facilities and the client-assignment costs. This abstracts facility-location settings where one has the flexibility of moving facilities from their current locations to other destinations so as to serve clients more efficiently by reducing their assignment costs. We give the first {\em local-search based} approximation algorithm for this problem and achieve the best-known approximation guarantee. Our main result is $(3+ε)$-approximation for this problem for any constant $ε>0$ using local search. The previous best guarantee was an 8-approximation algorithm based on LP-rounding. Our guarantee {\em matches} the best-known approximation guarantee for the $k$-median problem. Since there is an approximation-preserving reduction from the $k$-median problem to \mfl, any improvement of our result would imply an analogous improvement for the $k$-median problem. Furthermore, {\em our analysis is tight} (up to $o(1)$ factors) since the tight example for the local-search based 3-approximation algorithm for $k$-median can be easily adapted to show that our local-search algorithm has a tight approximation ratio of 3. One of the chief novelties of the analysis is that in order to generate a suitable collection of local-search moves whose resulting inequalities yield the desired bound on the cost of a local-optimum, we define a tree-like structure that (loosely speaking) functions as a "recursion tree", using which we spawn off local-search moves by exploring this tree to a constant depth.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Truthful Mechanism Design for Multidimensional Covering Problems

We investigate {\em multidimensional covering mechanism-design} problems, wherein there are $m$ items that need to be covered and $n$ agents who provide covering objects, with each agent $i$ having a private cost for the covering objects he provides. The goal is to select a set of covering objects of minimum total cost that together cover all the items. We focus on two representative covering problems: uncapacitated facility location (\ufl) and vertex cover (\vcp). For multidimensional \ufl, we give a black-box method to transform any {\em Lagrangian-multiplier-preserving} $ρ$-approximation algorithm for \ufl to a truthful-in-expectation, $ρ$-approx. mechanism. This yields the first result for multidimensional \ufl, namely a truthful-in-expectation 2-approximation mechanism. For multidimensional \vcp (\mvcp), we develop a {\em decomposition method} that reduces the mechanism-design problem into the simpler task of constructing {\em threshold mechanisms}, which are a restricted class of truthful mechanisms, for simpler (in terms of graph structure or problem dimension) instances of \mvcp. By suitably designing the decomposition and the threshold mechanisms it uses as building blocks, we obtain truthful mechanisms with the following approximation ratios ($n$ is the number of nodes): (1) $O(r^2\log n)$ for $r$-dimensional \vcp; and (2) $O(r\log n)$ for $r$-dimensional \vcp on any proper minor-closed family of graphs (which improves to $O(\log n)$ if no two neighbors of a node belong to the same player). These are the first truthful mechanisms for \mvcp with non-trivial approximation guarantees.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Improved Approximation Guarantees for Lower-Bounded Facility Location

We consider the {\em lower-bounded facility location} (\lbfl) problem (also sometimes called {\em load-balanced facility location}), which is a generalization of {\em uncapacitated facility location} (\ufl), where each open facility is required to serve a certain {\em minimum} amount of demand. More formally, an instance $\I$ of \lbfl is specified by a set $\F$ of facilities with facility-opening costs $\{f_i\}$, a set $\D$ of clients, and connection costs $\{c_{ij}\}$ specifying the cost of assigning a client $j$ to a facility $i$, where the $c_{ij}$s form a metric. A feasible solution specifies a subset $F$ of facilities to open, and assigns each client $j$ to an open facility $i(j)\in F$ so that each open facility serves {\em at least $M$ clients}, where $M$ is an input parameter. The cost of such a solution is $\sum_{i\in F}f_i+\sum_j c_{i(j)j}$, and the goal is to find a feasible solution of minimum cost. The current best approximation ratio for \lbfl is 448 \cite{Svitkina08}. We substantially advance the state-of-the-art for \lbfl by devising an approximation algorithm for \lbfl that achieves a significantly-improved approximation guarantee of 82.6. Our improvement comes from a variety of ideas in algorithm design and analysis, which also yield new insights into \lbfl.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Facility Location with Client Latencies: Linear-Programming based Techniques for Minimum-Latency Problems

We introduce a problem that is a common generalization of the uncapacitated facility location and minimum latency (ML) problems, where facilities need to be opened to serve clients and also need to be sequentially activated before they can provide service. Formally, we are given a set \F of n facilities with facility-opening costs {f_i}, a set of m clients, and connection costs {c_{ij}} specifying the cost of assigning a client j to a facility i, a root node r denoting the depot, and a time metric d on \F\cup{r}. Our goal is to open a subset F of facilities, find a path P starting at r and spanning F to activate the open facilities, and connect each client j to a facility ϕ(j)\in F, so as to minimize \sum_{i\in F}f_i +\sum_{clients j}(c_{ϕ(j),j}+t_j), where t_j is the time taken to reach ϕ(j) along path P. We call this the minimum latency uncapacitated facility location (MLUFL) problem. Our main result is an O(\log n\max{\log n,\log m})-approximation for MLUFL. We also show that any improvement in this approximation guarantee, implies an improvement in the (current-best) approximation factor for group Steiner tree. We obtain constant approximations for two natural special cases of the problem: (a) related MLUFL (metric connection costs that are a scalar multiple of the time metric); (b) metric uniform MLUFL (metric connection costs, unform time-metric). Our LP-based methods are versatile and easily adapted to yield approximation guarantees for MLUFL in various more general settings, such as (i) when the latency-cost of a client is a function of the delay faced by the facility to which it is connected; and (ii) the k-route version, where k vehicles are routed in parallel to activate the open facilities. Our LP-based understanding of MLUFL also offers some LP-based insights into ML, which we believe is a promising direction for obtaining improvements for ML.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Fault-Tolerant Facility Location: a randomized dependent LP-rounding algorithm

We give a new randomized LP-rounding 1.725-approximation algorithm for the metric Fault-Tolerant Uncapacitated Facility Location problem. This improves on the previously best known 2.076-approximation algorithm of Swamy & Shmoys. To the best of our knowledge, our work provides the first application of a dependent-rounding technique in the domain of facility location. The analysis of our algorithm benefits from, and extends, methods developed for Uncapacitated Facility Location; it also helps uncover new properties of the dependent-rounding approach. An important concept that we develop is a novel, hierarchical clustering scheme. Typically, LP-rounding approximation algorithms for facility location problems are based on partitioning facilities into disjoint clusters and opening at least one facility in each cluster. We extend this approach and construct a laminar family of clusters, which then guides the rounding procedure. It allows to exploit properties of dependent rounding, and provides a quite tight analysis resulting in the improved approximation ratio.

0 citations0 reviewsNo code linkedOpen access