The irrelevant vertex technique provides a powerful tool for the design of parameterized algorithms for a wide variety of problems on graphs. A common characteristic of these problems, permitting the application of this technique on surface-embedded graphs, is the fact that every graph of large enough treewidth contains a vertex that is irrelevant, in the sense that its removal yields an equivalent instance of the problem. The straightforward application of this technique yields algorithms with running time that is quadratic in the size of the input graph. This running time is due to the fact that it takes linear time to detect one irrelevant vertex and the total number of irrelevant vertices to be detected is linear as well. Using advanced techniques, sub-quadratic algorithms have been designed for particular problems, even in general graphs. However, designing a general framework for linear-time algorithms has been open, even for the bounded-genus case. In this paper we introduce a general framework that enables finding in linear time an entire set of irrelevant vertices whose removal yields a bounded-treewidth graph, provided that the input graph has bounded genus. Our technique consists in decomposing any surface-embedded graph into a tree-structured collection of bounded-treewidth subgraphs where detecting globally irrelevant vertices can be done locally and independently. Our method is applicable to a wide variety of known graph containment or graph modification problems where the irrelevant vertex technique applies. Examples include the (Induced) Minor Folio problem, the (Induced) Disjoint Paths problem, and the F-Minor-Deletion problem.

We study the classic weighted maximum throughput problem on unrelated machines. We give a (1-1/e-ε)-approximation algorithm for the preemptive case. To our knowledge this is the first ever approximation result for this problem. It is an immediate consequence of a polynomial-time reduction we design, that uses any ρ-approximation algorithm for the single-machine problem to obtain an approximation factor of (1-1/e)ρ -ε for the corresponding unrelated-machines problem, for any ε > 0. On a single machine we present a PTAS for the non-preemptive version of the problem for the special case of a constant number of distinct due dates or distinct release dates. By our reduction this yields an approximation factor of (1-1/e) -ε for the non-preemptive problem on unrelated machines when there is a constant number of distinct due dates or release dates on each machine.

Exploring the power of linear programming for combinatorial optimization problems has been recently receiving renewed attention after a series of breakthrough impossibility results. From an algorithmic perspective, the related questions concern whether there are compact formulations even for problems that are known to admit polynomial-time algorithms. We propose a framework for proving lower bounds on the size of extended formulations. We do so by introducing a specific type of extended relaxations that we call product relaxations and is motivated by the study of the Sherali-Adams (SA) hierarchy. Then we show that for every approximate relaxation of a polytope P, there is a product relaxation that has the same size and is at least as strong. We provide a methodology for proving lower bounds on the size of approximate product relaxations by lower bounding the chromatic number of an underlying hypergraph, whose vertices correspond to gap-inducing vectors. We extend the definition of product relaxations and our methodology to mixed integer sets. However in this case we are able to show that mixed product relaxations are at least as powerful as a special family of extended formulations. As an application of our method we show an exponential lower bound on the size of approximate mixed product formulations for the metric capacitated facility location problem, a problem which seems to be intractable for linear programming as far as constant-gap compact formulations are concerned.

Metric facility location is a well-studied problem for which linear programming methods have been used with great success in deriving approximation algorithms. The capacity-constrained generalizations, such as capacitated facility location (CFL) and lower-bounded facility location (LBFL), have proved notorious as far as LP-based approximation is concerned: while there are local-search-based constant-factor approximations, there is no known linear relaxation with constant integrality gap. According to Williamson and Shmoys devising a relaxation-based approximation for CFL is among the top 10 open problems in approximation algorithms. This paper advances significantly the state-of-the-art on the effectiveness of linear programming for capacity-constrained facility location through a host of impossibility results for both CFL and LBFL. We show that the relaxations obtained from the natural LP at Omega(n) levels of the Sherali-Adams hierarchy have an unbounded gap, partially answering an open question from the literature. Here, n denotes the number of facilities in the instance. Building on the ideas for this result, we prove that the standard CFL relaxation enriched with the generalized flow-cover valid inequalities has also an unbounded gap. This disproves a long-standing conjecture of Levi et al. We finally introduce the family of proper relaxations which generalizes to its logical extreme the classic star relaxation and captures general configuration-style LPs. We characterize the behavior of proper relaxations for CFL and LBFL through a sharp threshold phenomenon.

Given a sequencing of jobs on a single machine, each one with a weight, processing time, and a due date, the tardiness of a job is the time needed for its completion beyond its due date. We present an FPTAS for the basic scheduling problem of minimizing the total weighted tardiness when the number of distinct due dates is fixed. Previously, an FPTAS was known only for the case where all jobs have a common due date.

This paper provides a randomized approximation scheme for the k-median problem when the input points lie in the d-dimensional Euclidean space. The worst-case running time is $O(2^{O((\log(1/\epsilon) / \varepsilon)^{d-1})} n \log^{d+6} n ),$ which is nearly linear for any fixed $\varepsilon$ and d. Moreover, our method provides the first polynomial-time approximation scheme for and uncapacitated facility location instances in d-dimensional Euclidean space for any fixed $d > 2.$ Our work extends techniques introduced originally by Arora for the Euclidean traveling salesman problem (TSP). To obtain the improvement we develop a structure theorem to describe hierarchical decomposition of solutions. The theorem is based on an adaptive decomposition scheme, which guesses at every level of the hierarchy the structure of the optimal solution and accordingly modifies the parameters of the decomposition. We believe that our methodology is of independent interest and may find applications to further geometric problems.

We examine how the selfish behavior of heterogeneous users in a network can be regulated through economic disincentives, i.e., through the introduction of appropriate taxation. One wants to impose taxes on the edges so that any traffic equilibrium reached by the selfish users who are conscious of both the travel latencies and the taxes will minimize the social cost, i.e., will minimize the total latency. We generalize previous results of Cole, Dodis and Roughgarden that held for a single origin-destination pair to the multicommodity setting. Our approach, which could be of independent interest, is based on the formulation of traffic equilibria as a nonlinear complementarity problem by Aashtiani and Magnanti (1981), We extend this formulation so that each of its solutions will give us a set of taxes that forces the network users to conform, at equilibrium, to a certain prescribed routing. We use the special nature of the prescribed minimum-latency flow in order to reduce the difficult nonlinear complementarity formulation to a pair of primal-dual linear programs. LP duality is then enough to derive our results.

In this paper we study approximation algorithms for solving a general covering integer program. An n-vector x of nonnegative integers is sought, which minimizes c/sup T//spl middot/x, subject to Ax/spl ges/b, x/spl les/d. The entries of A, b, c are nonnegative. Let m be the number of rows of A. Covering problems have been heavily studied in combinatorial optimization. We focus on the effect of the multiplicity constraints, x/spl les/d, on approximately. Two longstanding open questions remain for this general formulation with upper bounds on the variables. (i) The integrality gap of the standard LP relaxation is arbitrarily large. Existing approximation algorithms that achieve the well-known O(log m)-approximation with respect to the LP value do so at the expense of violating the upper bounds on the variables by the same O(log m) multiplicative factor. What is the smallest possible violation of the upper bounds that still achieves cost within O(log m) of the standard LP optimum? (ii) The best known approximation ratio for the problem has been O(log(max/sub j//spl Sigma//sub i/A/sub ij/)) since 1982. This bound can be as bad as polynomial in the input size. Is an O(log m)-approximation, like the one known for the special case of Set Cover, possible? We settle these two open questions. To answer the first question we give an algorithm based on the relatively simple new idea of randomly rounding variables to smaller-than-integer units. To settle the second question we give a reduction from approximating the problem while respecting multiplicity constraints to approximating the problem with a bounded violation of the multiplicity constraints.

In the single-source unsplittable flow problem, we are given a network G, a source vertex s, and k commodities with sinks t i and real-valued demands $\rho_i,$ $1\leq i \leq k.$ We seek to route the demand $\rho_i$ of each commodity i along a single s-t i flow path so that the total flow routed across any edge e is bounded by the edge capacity u e . The conceptual difficulty of this NP-hard problem arises from combining packing constraints due to the existence of capacities with path selection in a graph of arbitrary topology. In this paper we give a generic framework, which yields approximation algorithms that are simpler than those previously known and achieve significant improvements upon the approximation ratios. Our framework, with appropriate subroutines, applies to all optimization versions previously considered and, unlike previous work, treats in a unified manner directed and undirected graphs. We provide extensions of our algorithms which yield the best possible approximation guarantees for restricted sets of demand values and an associated scheduling problem.

A basic problem faced by designers of high-bandwidth switches and routers is to provide effective techniques for scheduling the routing of cells through crossbars. The problem is particularly important under heavy loads or when quality-of-service (QoS) is to be supported. Much previous work on scheduling has focused on maximum bipartite matching (MBM), maximum weight bipartite matching (MWBM), and heuristics to approximate MBM and MWBM solutions. In this paper, we introduce the shakeup technique: a randomized approach that can be used in conjunction with a number of existing heuristics to substantially improve solution quality. The shakeup approach is conceptually simple and is supported by both theoretical and experimental results. In addition, this paper provides for the first time a framework for experimental scheduler analysis. We give extensive head-to-head comparisons of stability ranges for a number of previously proposed schedulers, and work towards the development of benchmark traffic types.

In the single-source unsplittable flow problem we are given a graph G, a source vertex s and a set of sinks t/sub 1/, ..., t/sub k/ with associated demands. We seek a single s-t/sub i/ flow path for each commodity i so that the demands are satisfied and the total flow routed across any edge e is bounded by its capacity c/sub e/. The problem is an NP-hard variant of max flow and a generalization of single-source edge-disjoint paths with applications to scheduling, load balancing and virtual-circuit routing problems. In a significant development, Kleinberg gave recently constant-factor approximation algorithms for several natural optimization versions of the problem. In this paper we give a generic framework, that yields simpler algorithms and significant improvements upon the constant factors. Our framework, with appropriate subroutines applies to all optimization versions previously considered and treats in a unified manner directed and undirected graphs.