Search

Given a capacitated graph G = (V,E) and a set of terminals K ⊆ V, how should we produce a graph H only on the terminals K so that every (multicommodity) flow between the terminals in G could be supported in H with low congestion, and vice versa? (Such a graph H is called a flow-sparsifier for G.) What if we want H to be a ˵simple″ graph? What if we allow H to be a convex combination of simple graphs? Improving on results of Moitra [FOCS 2009] and Leighton and Moitra [STOC 2010], we give efficient algorithms for constructing: (a) a flow-sparsifier H that maintains congestion up to a factor of ]> , where k = |K|. (b) a convex combination of trees over the terminals K that maintains congestion up to a factor of O(logk). (c) for a planar graph G, a convex combination of planar graphs that maintains congestion up to a constant factor. This requires us to give a new algorithm for the 0-extension problem, the first one in which the preimages of each terminal are connected in G. Moreover, this result extends to minor-closed families of graphs. Our bounds immediately imply improved approximation guarantees for several terminal-based cut and ordering problems. [ABSTRACT FROM AUTHOR]

In this work, we study the strength of the Chvátal-Gomory cut generating procedure for several hard optimization problems. For hypergraph matching on k-uniform hypergraphs, we show that using Chvátal-Gomory cuts of low rank can reduce the integrality gap significantly even though Sherali-Adams relaxation has a large gap even after linear number of rounds. On the other hand, we show that for other problems such as k-CSP, unique label cover, maximum cut, and vertex cover, the integrality gap remains large even after adding all Chvátal-Gomory cuts of large rank. [ABSTRACT FROM AUTHOR]

In recent years, considerable advances have been made in the study of properties of metric spaces in terms of their doubling dimension. This line of research has not only enhanced our understanding of finite metrics, but has also resulted in many algorithmic applications. However, we still do not understand the interaction between various graph-theoretic (topological) properties of graphs, and the doubling (geometric) properties of the shortest-path metrics induced by them. For instance, the following natural question suggests itself: given a finite doubling metric (V,d), is there always an unweighted graph (V',E') with V ⊆ V' such that the shortest path metric d' on V' is still doubling, and which agrees with d on V. This is often useful, given that unweighted graphs are often easier to reason about. A first hurdle to answering this question is that subdividing edges can increase the doubling dimension unboundedly, and it is not difficult to show that the answer to the above question is negative. However, surprisingly, allowing a distortion between d and d' enables us bypass this impossibility: we show that for any metric space (V,d), there is an unweighted graph (V',E') with shortest-path metric such that for all x,y ϵ V, the distances , and the doubling dimension for d' is not much more than that of d, where this change depends only on and not on the size of the graph. We show a similar result when both (V,d) and (V',E') are restricted to be trees: this gives a simple proof that doubling trees embed into constant dimensional Euclidean space with constant distortion. We also show that our results are tight in terms of the tradeoff between distortion and dimension blowup. [ABSTRACT FROM AUTHOR]

One of the interesting recent developments in the design and analysis of approximation algorithms has been in the area of algorithms for discrete stochastic optimization problems. In this domain, one is given not just one input, but rather a probability distribution over inputs, and yet the aim is to design an algorithm that has provably good worst-case performance, that is, for any probability distribution over inputs, the objective function value of the solution found by the algorithm must be within a specified factor of the optimal value. The a priori traveling salesman problem is a prime example of such a stochastic optimization problem. One starts with the standard traveling salesman problem (in which one wishes to find the shortest tour through a given set of points N), and then considers the possibility that only a subset A of the entire set of points is active. The active set is given probabilistically; that is, there is a probability distribution over the subsets of N, which is given as part of the input. The aim is still to compute a tour through all points in N, but in order to evaluate its cost, we instead compute the expectation of the length of this tour after shortcutting it to include only those points in the active set A (where the expectation is computed with respect to the given probability distribution). The goal is to compute a ˵master tour″ for which this expectation is minimized. This problem was introduced in the doctoral theses of Jaillet and Bertsimas, who gave asymptotic analyses when the distances between points in the input set are also given probabilistically. In this paper, we restrict attention to the so-called ˵independent activation″ model in which we assume that each point j is active with a given probability pj, and that these independent random events. For this setting, we give a 8-approximation algorithm, a polynomial-time algorithm that computes a tour whose a priori TSP objective function value is guaranteed to be within a factor of 8 of optimal (and a randomized 4-approximation algorithm, which produces a tour of expected cost within a factor of 4 of optimal). This is the first constant approximation algorithm for this model. [ABSTRACT FROM AUTHOR]

Given a graph G and degree bound B on its nodes, the bounded-degree minimum spanning tree (BDMST) problem is to find a minimum cost spanning tree among the spanning trees with maximum degree B. This bi-criteria optimization problem generalizes several combinatorial problems, including the Traveling Salesman Path Problem (TSPP). An $(\alpha,\:f(B))$-approximation algorithm for the BDMST problem produces a spanning tree that has maximum degree f(B) and cost within a factor α of the optimal cost. Könemann and Ravi [13,14] give a polynomial-time $({1+\frac{1}{\beta}},\:{bB(1+\beta) + \log•bn})$-approximation algorithm for any b > 1, β> 0. In a recent paper [2], Chaudhuri et al. improved these results with a $({1},\:{bB+\sqrt{b}\log•bn})$-approximation for any b > 1. In this paper, we present a $({1+\frac{1}{\beta}},\:{2B(1+ \beta) + o(B(1+\beta))})$-approximation polynomial-time algorithm. That is, we give the first algorithm that approximates both degree and cost to within a constant factor of the optimal. These results generalize to the case of non-uniform degree bounds. The crux of our solution is an approximation algorithm for the related problem of finding a minimum spanning tree (MST) in which the maximum degree of the nodes is minimized, a problem we call the minimum-degree MST (MDMST) problem. Given a graph G for which the degree of the MDMST solution is $\Delta•{\mbox{\sc{opt}}}$, our algorithm obtains in polynomial time an MST of G of degree at most $2\Delta•{\mbox{\sc{opt}}} + o(\Delta•{\mbox{\sc{opt}}})$. This result improves on a previous result of Fischer [4] that finds an MST of G of degree at most $b\Delta•{\mbox{\sc{opt}}} + \log•bn$ for any b > 1, and on the improved quasipolynomial algorithm of [2]. Our algorithm uses the push-relabel framework developed by Goldberg [7] for the maximum flow problem. To our knowledge, this is the first instance of a push-relabel approximation algorithm for an NP-hard problem, and we believe these techniques may have larger impact. We note that for B = 2, our algorithm gives a tree of cost within a (1+ε)-factor of the optimal solution to TSPP and of maximum degree $O(\frac{1}{\epsilon})$ for any ε> 0, even on graphs not satisfying the triangle inequality. [ABSTRACT FROM AUTHOR]

The buy-at-bulk network design problem is to design a minimum cost network to satisfy some flow demands, by installing cables from an available set of cables with different costs per unit length and capacities, where the cable costs obey economies of scale. For the single-sink buy-at-bulk problem, [10] gave the first constant factor approximation. In this paper, we use techniques of [9] to get an improved constant factor approximation. This also shows that the integrality gap of a natural linear programming formulation is a constant, thus answering the open question in [9]. [ABSTRACT FROM AUTHOR]

In this paper we initiate the study of the AND-OR directed feedback vertex set problem from the viewpoint of approximation algorithms. This AND-OR feedback vertex set problem is motivated by a practical deadlock resolution problem that appears in the development of distributed database systemsThanks to Ondrej Such from Microsoft for asking an algorithm for this problem.. This problem also turns out be a natural generalization of the directed feedback vertex set problem. Awerbuch and Micali [1] gave a polynomial time algorithm to find a minimal solution for this problem. Unfortunately, a minimal solution can be arbitrarily more expensive than the minimum cost solution. We show that finding the minimum cost solution is as hard as the directed Steiner tree problem (and thus Ω(log2n) hard to approximate). On the positive side, we give algorithms which work well when the number of writers (AND nodes) or the number of readers (OR nodes) are small. We also consider a variant that we call permanent deadlock resolution where we cannot specify an execution order for the surviving processes; they should get completed even if they were scheduled adversarially. When all processes are writers (AND nodes), we give an O(log n log log n) approximation for this problem. Finally we give an LP-rounding approach and discuss some other natural variants. [ABSTRACT FROM AUTHOR]

A caterpillar is a tree in which all vertices of degree three or more lie on one path, called the backbone. We present a polynomial time algorithm that produces a linear arrangement of the vertices of a caterpillar with bandwidth at most O(log n/loglog n) times the local density of the caterpillar, where the local density is a well known lower bound on the bandwidth. This result is best possible in the sense that there are caterpillars whose bandwidth is larger than their local density by a factor of Ω(log n/loglog n). The previous best approximation ratio for the bandwidth of caterpillars was O(log n). We show that any further improvement in the approximation ratio would require using linear arrangements that do not respect the order of the vertices of the backbone. We also show how to obtain a (1 + ε) approximation for the bandwidth of caterpillars in time $2^{\tilde{O}(\sqrt{n/\epsilon})}$. This result generalizes to trees, planar graphs, and any family of graphs with treewidth $\tilde{O}(\sqrt{n})$. [ABSTRACT FROM AUTHOR]

Given a graph and degree upper bounds on vertices, the problem requires us to find the minimum cost spanning tree respecting the given degree bounds.and Ravi [10,11] give bicriteria approximation algorithms for the problem using local search techniques of Fischer [5]. For a graph with a cost C, degree B spanning tree, and parameters b, w> 1, their algorithm produces a tree whose cost is at most wC and whose degree is at most $\frac{w}{w-1}bB + \log_b n.$ We give a polynomial-time algorithm that finds a tree of optimal cost and with maximum degree at most bB + 2(b+1)logbn. We also give a quasi-polynomial algorithm which produces a tree of optimal cost C and maximum degree bounded by B + O(log n/loglog n). Our algorithms work when there are upper as well as lower bounds on the degrees of the vertices. [ABSTRACT FROM AUTHOR]

We give a simple characterization of all single-item truth-revealing auctions under some mild (and natural) assumptions about the auctions. Our work opens up the possibility of using variational calculus to design auctions having desired properties. [ABSTRACT FROM AUTHOR]

We provide the first strongly polynomial time exact combinatorial algorithm to compute Fisher equilibrium for the case when utility functions do not satisfy the Gross substitutability property. The motivation for this comes from the work of Kelly, Maulloo, and Tan [15] and Kelly and Vazirani [16] on rate control in communication networks. We consider a tree like network in which root is the source and all the leaf nodes are the sinks. Each sink has got a fixed amount of money which it can use to buy the capacities of the edges in the network. The edges of the network sell their capacities at certain prices. The objective of each edge is to fix a price which can fetch the maximum money for it and the objective of each sink is to buy capacities on edges in such a way that it can facilitate the sink to pull maximum flow from the source. In this problem, the edges and the sinks play precisely the role of sellers and buyers, respectively, in the Fisher's market model. The utility of a buyer (or sink) takes the form of Leontief function which is known for not satisfying Gross substitutability property. We develop an O(m3) exact combinatorial algorithm for computing equilibrium prices of the edges. The time taken by our algorithm is independent of the values of sink money and edge capacities. A corollary of our algorithm is that equilibrium prices and flows are rational numbers. Although there are algorithms to solve this problem but they are all based on convex programming techniques. To the best of our knowledge, ours is the first strongly polynomial time exact combinatorial algorithm for computing equilibrium prices of Fisher model under the case when buyers' utility functions do not satisfy Gross substitutability property. [ABSTRACT FROM AUTHOR]

In pay-per-click online advertising systems like Google, Overture, or MSN, advertisers are charged for their ads only when a user clicks on the ad. While these systems have many advantages over other methods of selling online ads, they suffer from one major drawback. They are highly susceptible to a particular style of fraudulent attack called click fraud. Click fraud happens when an advertiser or service provider generates clicks on an ad with the sole intent of increasing the payment of the advertiser. Leaders in the pay-per-click marketplace have identified click fraud as the most significant threat to their business model. We demonstrate that a particular class of learning algorithms, called click-based algorithms, are resistant to click fraud in some sense. We focus on a simple situation in which there is just one ad slot, and show that fraudulent clicks can not increase the expected payment per impression by more than o(1) in a click-based algorithm. Conversely, we show that other common learning algorithms are vulnerable to fraudulent attacks. [ABSTRACT FROM AUTHOR]