Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form 𝐋𝐱 = 𝐛, where 𝐋 is the Laplacian matrix of a weighted graph with weights w(i,j) > 0 on the edges. The solution 𝐱 of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i,j) is 1/w(i,j). Kelner, Orrechia, Sidford, and Zhu [Kelner et al., 2013] give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector-matrix-vector problem (OMv), which has been conjectured to be difficult for dynamic algorithms [Henzinger et al., 2015]. The conjecture implies that the data structure does not have an O(n^{1-ε}) time algorithm for any ε > 0, and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an Õ(m^{1.5}) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m^{1 + ε}) for any ε > 0. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart.

The Simplex algorithm for solving linear programs---one of Computing in Science & Engineering's top 10 most influential algorithms of the 20th century---is an important topic in many algorithms courses. While the algorithm relies on intuitive geometric ideas, the computationally-involved mechanics of the algorithm can obfuscate a geometric understanding. In this paper, we present gilp, an easy-to-use Simplex algorithm visualization tool designed to connect the mechanical steps of the algorithm with their geometric interpretation. We provide an extensive library of example visualizations, and our tool allows instructors to quickly produce custom interactive HTML files for students to experiment with the algorithm (without requiring students to install anything!). The tool can also be used for interactive assignments in Jupyter notebooks, and has been incorporated into a forthcoming Data Science and Decision Making interactive textbook. In this paper, we first describe how the tool fits into the existing algorithm visualization literature: how it was designed to facilitate student engagement and instructor adoption, and how it substantially extends existing algorithm visualization tools for Simplex. We then describe the development and usage of the tool, and report feedback from its use in a course with roughly 100 students. Student feedback was overwhelmingly positive, with students finding the tool easy to use: it effectively helped them link the algebraic and geometrical views of the Simplex algorithm and understand its nuances. Finally, gilp is open-source, includes an extension to visualizing linear programming-based branch and bound, and is readily amenable to further extensions.

Combinatorial optimization algorithms for graph problems are usually designed afresh for each new problem with careful attention by an expert to the problem structure. In this work, we develop a new framework to solve any combinatorial optimization problem over graphs that can be formulated as a single player game defined by states, actions, and rewards, including minimum spanning tree, shortest paths, traveling salesman problem, and vehicle routing problem, without expert knowledge. Our method trains a graph neural network using reinforcement learning on an unlabeled training set of graphs. The trained network then outputs approximate solutions to new graph instances in linear running time. In contrast, previous approximation algorithms or heuristics tailored to NP-hard problems on graphs generally have at least quadratic running time. We demonstrate the applicability of our approach on both polynomial and NP-hard problems with optimality gaps close to 1, and show that our method is able to generalize well: (i) from training on small graphs to testing on large graphs; (ii) from training on random graphs of one type to testing on random graphs of another type; and (iii) from training on random graphs to running on real world graphs.

The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an n-vertex spanning tree T and an additional set L of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links F such that every terminal pair that has arrived so far is 2-edge-connected in T cup F. This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic O(log^2 n)-competitive algorithm and showed an Omega(log n) lower bound on the competitive ratio of randomized algorithms. The case when T is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic O(log n)-competitive algorithm for online WTAP, which is tight up to constant factors.

We consider the integrality gap of the subtour linear program (LP) relaxation of the traveling salesman problem (TSP) restricted to circulant instances. De Klerk and Dobre [ Discrete Appl. Math., 159 (2011), pp. 1815--1826] conjectured that the value of the optimal solution to the subtour LP in these instances is equal to an entirely combinatorial lower bound from Van der Veen, Van Dal, and Sierksma [ The Symmetric Circulant Traveling Salesman Problem, Research Memorandum 429, Institute of Economic Research, University of Groningen, 1991]. We prove this conjecture by giving an explicit optimal solution to the subtour LP. We then show that the integrality gap of the subtour LP is 2 on circulant instances, making such instances one of the few nontrivial classes of TSP instances for which the integrality gap of the subtour LP is exactly known. We also show that the degree constraints do not strengthen the subtour LP on circulant instances, mimicking the parsimonious property of metric, symmetric TSP instances shown in Goemans and Bertsimas [ Math. Programming, 60 (1993), pp. 145--166] in a distinctly nonmetric set of instances.

We consider constrained versions of the prize-collecting traveling salesman and the minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. We present a 2-approximation algorithm for these problems based on a primal-dual approach. The algorithm relies on finding a threshold value for the dual variable corresponding to the budget constraint in the primal and then carefully constructing a tour/tree that is just within budget. Thereby, we improve the best-known guarantees from 3+epsilon and 2+epsilon for the tree and the tour version, respectively. Our analysis extends to the setting with weighted vertices, in which we want to maximize the total weight of vertices in the tour/tree subject to the same budget constraint.

We consider pricing problems when customers choose among the products according to the nested logit model and there is a quality consistency constraint on the prices charged for the products. We consider two types of quality consistency constraint. In the first, there is an inherent ordering between the qualities of the products in a particular nest and the price for a product of a higher quality should be larger. In the second type of constraint, different nests correspond to different quality levels; the price for any product in a nest corresponding to a higher quality level should be larger than the price for any product in a nest corresponding to a lower quality level. Prices for the products are chosen from a finite set of possible prices. We develop algorithms to find the prices to charge for the products to maximize the expected revenue obtained from a customer, while adhering to a quality consistency constraint. Our algorithms are based on solving linear programs whose sizes scale polynomially with the number of nests, number of products, and number of possible prices for the products. We also give extensions to the cases beyond the two types of quality consistency constraints. Numerical experiments indicate that our algorithms can effectively compute the optimal prices even when there is a large number of products in consideration.

We give a simple, randomized greedy algorithm for the maximum satisfiability problem (MAX SAT) that obtains a $\frac{3}{4}$-approximation in expectation. In contrast to previously known $\frac{3}{4}$-approximation algorithms, our algorithm does not use flows or linear programming. Hence we provide a positive answer to a question posed by Williamson in 1998 on whether such an algorithm exists. Moreover, we show that Johnson's greedy algorithm cannot guarantee a $\frac{3}{4}$-approximation, even if the variables are processed in a random order. Thereby we partially solve a problem posed by Chen, Friesen, and Zheng in 1999. In order to explore the limitations of the greedy paradigm, we use the model of priority algorithms of Borodin, Nielsen, and Rackoff. Since our greedy algorithm works in an online scenario where the variables arrive with their set of undecided clauses, we wonder if a better approximation ratio can be obtained by further fine-tuning its random decisions. For a particular information model we show that no priority algorithm can approximate Online MAX SAT within $\frac{3}{4} + \varepsilon$ (for any $\varepsilon > 0$). We further investigate the strength of deterministic greedy algorithms that may choose the variable ordering. Here we show that no adaptive priority algorithm can achieve approximation ratio $\frac{3}{4}$. We propose two ways in which this inapproximability result can be bypassed. First we show that if our greedy algorithm is additionally given the variable assignments of an optimal solution to the canonical LP relaxation, then we can derandomize its decisions while preserving the overall approximation guarantee. Second we give a simple, deterministic algorithm that performs an additional pass over the input. We show that this 2-pass algorithm satisfies clauses with a total weight of at least $\frac{3}{4} {OPT}_{LP}$, where ${OPT}_{LP}$ is the objective value of the canonical linear program. Moreover, we demonstrate that our analysis is tight and detail how each pass can be implemented in linear time.

Determining the precise integrality gap for the subtour LP relaxation of the traveling salesman problem is a significant open question, with little progress made in thirty years in the general case of symmetric costs that obey triangle inequality. Boyd and Carr [3] observe that we do not even know the worst-case upper bound on the ratio of the optimal 2-matching to the subtour LP; they conjecture the ratio is at most 10/9. In this paper, we prove the Boyd-Carr conjecture. In the case that a fractional 2-matching has no cut edge, we can further prove that an optimal 2-matching is at most 10/9 times the cost of the fractional 2-matching.

We present a general framework and algorithmic approach for incremental approximation algorithms. The framework handles cardinality constrained minimization problems, such as the k-median and k-MST problems. Given some notion of ordering on solutions of different cardinalities k, we give solutions for all values of k such that the solutions respect the ordering and such that for any k, our solution is close in value to the value of an optimal solution of cardinality k. For instance, for the k-median problem, the notion of ordering is set inclusion, and our incremental algorithm produces solutions such that for any k and $k'$, $k

Abstract The smallest k‐ECSS problem is, given a graph along with an integer k, find a spanning subgraph that is k‐edge connected and contains the fewest possible number of edges. We examine a natural approximation algorithm based on rounding an LP solution. A tight bound on the approximation ratio is 1 + 3/k for undirected graphs with k > 1 odd, 1 + 2/k for undirected graphs with k even, and 1 + 2/k for directed graphs with k arbitrary. Using iterated rounding improves the first upper bound to 1 + 2/k. On the hardness side we show that for some absolute constant c > 0, for any integer k ≥ 2 (k ≥ 1), a polynomial‐time algorithm approximating the smallest k‐ECSS on undirected (directed) multigraphs to within ratio 1 + c/k would imply P = NP. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

We give a 7.18-approximation algorithm for the minimum latency problem that uses only $O(n \log n)$ calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the k-minimum spanning tree (k-MST) problem which is called as a black box for each value of k. Their algorithm can achieve an approximation factor of 10.77 while making $O(n (n+\log C) \log n)$ PCST calls, a factor of 8.98 using $O(n^3(n+\log C) \log n)$ PCST calls, or a factor of $7.18+\epsilon$ using $n^{O(1/\epsilon)}\log C$ PCST calls, via the k-MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here n denotes the number of nodes in the instance, and C is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in $O(n^2)$ time, the overall running time of our algorithm is $O(n^3 \log n)$. We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only $O(\log^2 n)$ PCST calls, and derandomize it to obtain a deterministic algorithm with factor $7.18+\epsilon$, using $O(\frac{1}{\epsilon} \log^2 n)$ PCST calls. The basic idea for our improvement is that we do not treat the k-MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate k-MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate k-MSTs for all values of k, even though we have them only for some values of k that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem.

Noncooperative network routing games are a natural model of userstrying to selfishly route flow through a network in order to minimize their own delays. It is well known that the solution resulting from this selfish routing (called the Nash equilibrium) can have social cost strictly higher than the cost of the optimum solution. One way to improve the quality of the resulting solution is to centrally control a fraction of the flow. A natural problem for the network administrator then is to route the centrally controlled flow in such a way that the overall cost of the solution is minimized after the remaining fraction has routed itself selfishl.

Increases in online search activities have spurred the growth of search-based advertising services offered by search engines. These services enable companies to promote their products to consumers based on their search queries. In most search-based advertising services, a company sets a daily budget, selects a set of keywords, determines a bid price for each keyword, and designates an ad associated with each selected keyword. When a consumer searches for one of the selected keywords, search engines then display the ads associated with the highest bids for that keyword on the search result page. A company whose ad is displayed pays the search engine only when the consumer clicks on the ad. If the company's spending has exceeded its daily budget, however, its ads will not be displayed. With millions of available keywords and a highly uncertain clickthru rate associated with the ad for each keyword, identifying the most profitable set of keywords given the daily budget constraint becomes challenging for companies wishing to promote their goods and services via search-based advertising. Motivated by these challenges, we formulate a model of keyword selection in search-based advertising services. We develop an algorithm that adaptively identifies the set of keywords to bid on based on historical performance. The algorithm prioritizes keywords based on a prefix ordering-- sorting of keywords in a descending order of profit-tocost ratio (or "bang-per-buck"). We show that the average expected profit generated by the algorithm converges to near-optimal profits. Furthermore, the convergence rate is independent of the number of keywords and scales gracefully with the problem's parameters. Extensive numerical simulations show that our algorithm outperforms existing methods, increasing profits by about 7%.

The social impact from the World Wide Web cannot be underestimated, but technologies used to build the Web are also revolutionizing the sharing of business and government information within intranets. In many ways the lessons learned from the Internet carry over directly to intranets, but others do not apply. In particular, the social forces that guide the development of intranets are quite different, and the determination of a "good answer" for intranet search is quite different than on the Internet. In this paper we study the problem of intranet search. Our approach focuses on the use of rank aggregation, and allows us to examine the effects of different heuristics on ranking of search results.

In the survivable network design problem (SNDP), given an undirected graph and values r/sub ij/ for each pair of vertices i and j, we attempt to find a minimum-cost subgraph such that there are r/sub ij/ disjoint paths between vertices i and j. In the edge connected version of this problem (EC-SNDP), these paths must be edge-disjoint. In the vertex connected version of the problem (VC-SNDP), the paths must be vertex disjoint. K. Jain et al. (1999) propose a version of the problem intermediate in difficulty to these two, called the element connectivity problem (ELC-SNDP, or ELC). These variants of SNDP are all known to be NP-hard. The best known approximation algorithm for the EC-SNDP has performance guarantee of 2 (K. Jain, 2001), and iteratively rounds solutions to a linear programming relaxation of the problem. ELC has a primal-dual O (log k) approximation algorithm, where k=max/sub i,j/ r/sub ij/. VC-SNDP is not known to have a non-trivial approximation algorithm; however, recently L. Fleischer (2001) has shown how to extend the technique of K. Jain ( 2001) to give a 2-approximation algorithm in the case that r/sub ij//spl isin/{0, 1, 2}. She also shows that the same techniques will not work for VC-SNDP for more general values of r/sub ij/. The authors show that these techniques can be extended to a 2-approximation algorithm for ELC. This gives the first constant approximation algorithm for a general survivable network design problem which allows node failures.

A number of recent papers on approximation algorithms have used the square roots of unity, -1 and 1 to represent binary decision variables for problems in combinatorial optimization, and have relaxed these to unit vectors in real space using semidefinite programming in order to obtain near optimal solutions to these problems. In this paper, we consider using the cube roots of unity, 1, ei2π/3, to represent ternary decision variables for problems in combinatorial optimization. Here the natural relaxation is that of unit vectors in complex space. We use an extension of semidefinite programming to complex space to solve the natural relaxation, and use a natural extension of the random hyperplane technique introduced by the authors in [8] to obtain near-optimal solutions to the problems.

We consider packet routing when packets are injected continuously into a network. We develop an adversarial theory of queuing aimed at addressing some of the restrictions inherent in probabilistic analysis and queuing theory based on time-invariant stochastic generation. We examine the stability of queuing networks and policies when the arrival process is adversarial, and provide some preliminary results in this direction. Our approach sheds light on various queuing policies in simple networks, and paves the way for a systematic study of queuing with few or no probabilistic assumptions.

A number of basic models for VLSI layout are based on the construction of node-disjoint paths between terminals on a multilayer grid. In this setting, one is interested in minimizing both the number of layers required and the area of the underlying grid. Building on work of Cutler and Shiloach [ Networks, 8 (1978), pp. 253--278], Aggarwal et al. [ Proc. 26th IEEE Symposium on Foundations of Computer Science , Portland, OR, 1985; Algorithmica, 6 (1991), pp. 241--255], and Aggarwal, Klawe, and Shor [ Algorithmica}, 6 (1991), pp. 129--151], we prove an upper-bound trade-off between these two quantities in a general multilayer grid model. As a special case of our main result, we obtain significantly improved bounds for the problem of routing a full permutation on the mesh using node-disjoint paths; our new bound here is within polylogarithmic factors of the bisection bound. Our algorithms involve some new techniques for analyzing the structure of node-disjoint paths in planar graphs and indicate some respects in which this problem, at least in the planar case, is fundamentally different from its edge-disjoint counterpart.

We study optimization problems that may be expressed as "Boolean constraint satisfaction problems." An instance of a Boolean constraint satisfaction problem is given by m constraints applied to n Boolean variables. Different computational problems arise from constraint satisfaction problems depending on the nature of the "underlying" constraints as well as on the goal of the optimization task. Here we consider four possible goals: Max CSP (Min CSP) is the class of problems where the goal is to find an assignment maximizing the number of satisfied constraints (minimizing the number of unsatisfied constraints). Max Ones (Min Ones) is the class of optimization problems where the goal is to find an assignment satisfying all constraints with maximum (minimum) number of variables set to 1. Each class consists of infinitely many problems and a problem within a class is specified by a finite collection of finite Boolean functions that describe the possible constraints that may be used. Tight bounds on the approximability of every problem in Max CSP were obtained by Creignou [ J. Comput. System Sci., 51 (1995), pp. 511--522]. In this work we determine tight bounds on the "approximability" (i.e., the ratio to within which each problem may be approximated in polynomial time) of every problem in Max Ones, Min CSP, and Min Ones. Combined with the result of Creignou, this completely classifies all optimization problems derived from Boolean constraint satisfaction. Our results capture a diverse collection of optimization problems such as MAX 3-SAT, Max Cut, Max Clique, Min Cut, Nearest Codeword, etc. Our results unify recent results on the (in-)approximability of these optimization problems and yield a compact presentation of most known results. Moreover, these results provide a formal basis to many statements on the behavior of natural optimization problems that have so far been observed only empirically.

We present a linear programming-based method for finding "gadgets," i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in this method is a simple observation which limits the search space to a finite one. Using this new method we present a number of new, computer-constructed gadgets for several different reductions. This method also answers a question posed by Bellare, Goldreich, and Sudan [SIAM J. Comput., 27 (1998), pp. 804--915] of how to prove the optimality of gadgets: linear programming duality gives such proofs. The new gadgets, when combined with recent results of Håstad [ Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 1--10], improve the known inapproximability results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of $16/17 + ε$ and $12/13+ ε,$ respectively, is NP-hard for every ε > 0. Prior to this work, the best-known inapproximability thresholds for both problems were 71/72 (M. Bellare, O. Goldreich, and M. Sudan [ SIAM J. Comput., 27 (1998), pp. 804--915]). Without using the gadgets from this paper, the best possible hardness that would follow from Bellare, Goldreich, and Sudan and Håstad is 18/19. We also use the gadgets to obtain an improved approximation algorithm for MAX3 SAT which guarantees an approximation ratio of .801. This improves upon the previous best bound (implicit from M. X. Goemans and D. P. Williamson [J. ACM, 42 (1995), pp. 1115--1145]; U. Feige and M. X. Goemans [Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182--189]) of .7704.

In this note we give an alternate proof that a scheduling algorithm of Lawler [E.L. Lawler, Ann. Discrete Math., 2 (1978), pp. 75--90, E.L. Lawler and J.K. Lenstra, in Ordered Sets, I. Rival, ed., D. Reidel, 1982, pp. 655--675] finds the optimal solution for the scheduling problem $1 | prec | \sum_j w_j C_j$ when the precedence constraints are series-parallel. We do this by using a linear programming formulation of $1 | prec | \sum_j w_j C_j$ introduced by Queyranne and Wang. [ Math. Oper. Res., 16 (1991), pp. 1--20]. Queyranne and Wang proved that their formulation completely describes the scheduling polyhedron in the case of series-parallel constraints; a by-product of our proof of correctness of Lawler's algorithm is an alternate proof of this fact. In the course of our proof it is helpful to use what might be called two-dimensional (2D) Gantt charts. We think these may find independent use, and to illustrate this we show that some recent work in the area becomes transparent using 2D Gantt charts.

In this paper we study the approximability of boolean constraint satisfaction problems. A problem in this class consists of some collection of "constraints" (i.e., functions f : f0; 1g k ! f0; 1g); an instance of a problem is a set of constraints applied to specified subsets of n boolean variables. Schaefer earlier studied the question of whether one could find in polynomial time a setting of the variables satisfying all constraints; he showed that every such problem is either in P or is NP-complete. We consider optimization variants of these problems in which one either tries to maximize the number of satisfied constraints (as in MAX 3SAT or MAX CUT) or tries to find an assignment satisfying all constraints which maximizes the number of variables set to 1 (as in MAX CUT or MAX CLIQUE). We completely classify the approximability of all such problems. In the first case, we show that any such optimization problem is either in P or is MAX SNP-hard. In the second case, we show that such problems fall precisely into one of five classes, assuming P 6= NP: solvable in polynomialtime, approximable to within constant factors in polynomial time (but no better), approximable to within polynomial factors in polynomial time (but no better), not approximable to within any factor but decidable in polynomial time, and not decidable in polynomial time. This result proves formally for this class of problems two results which to this point have only been empirical observations; namely, that NP-hard problems in...

The authors present a linear-programming based method for finding "gadgets", i.e., combinatorial structures reducing constraints of one optimization problem to constraints of another. A key step in this method is a simple observation which limits the search space to a finite one. Using this new method they present a number of new, computer-constructed gadgets for several different reductions. This method also answers the question of how to prove the optimality of gadgets-they show how LP duality gives such proofs. The new gadgets improve hardness results for MAX CUT and MAX DICUT, showing that approximating these problems to within factors of 60/61 and 44/45 respectively is NP-hard (improving upon the previous hardness of 71/72 for both problems). They also use the gadgets to obtain an improved approximation algorithm for MAX 3SAT which guarantees an approximation ratio of 0.801, This improves upon the previous best bound of 0.7704.

A number of basic models for VLSI layout are based on the construction of nodedisjoint paths between terminals on a multi-layer grid. In this setting, one is interested in minimizing both the number of layers required and the area of the underlying grid. Building on work of Cutler and Shiloach, and Aggarwal, Klawe, et al., we prove an upper-bound trade-off between these two quantities in a general multi-layer grid model. As a special case of our main result, we obtain significantly improved bounds for the problem of routing a full permutation on the mesh using node-disjoint paths; our new bound here is within polylogarithmic factors of the bisection bound. Our algorithms involve some new techniques for analyzing the structure of node-disjoint paths in planar graphs, and indicate some respects in which this problem, at least in the planar case, is fundamentally different from its edge-disjoint counterpart. 1 Introduction The basic node--disjoint paths problem is as follows. We are give...

We introduce a new approach to the study of dynamic (or continuous) packet routing, where packets are being continuously injected into a network. Our objective is to study what happens to packet routing under continuous injection as a function of network load, for various queueing policies. Our approach is based on the adversarial generation of packets, so that the results are more robust in that they do not hinge upon particular probabilistic assumptions. In suggesting a new approach to studying a classical phenomenon, it is important to give careful consideration to all the relevant previous work in packet routing, queueing theory and probabilistic analysis. We give a more detailed account of previous work in Appendix A, to permit comparison with our work. Here we summarize the salient features of prior work in order to motivate our model. Most prior work on packet routing has been in the static model in which there is a fixed initial set of packet ro

We consider a 2-approximation algorithm for Euclidean minimum-cost perfect matching instances proposed by the authors in a previous paper. We present computational results for both random and real-world instances having between 1,000 and 131,072 vertices. The results indicate that our algorithm generates a matching within 2% of optimal in most cases. In over 1,400 experiments, the algorithm was never more than 4% from optimal. For the purposes of the study, we give a new implementation of the algorithm that uses linear space instead of quadratic space, and appears to run faster in practice.

We present randomized approximation algorithms for the maximum cut (MAX CUT) and maximum 2-satisfiability (MAX 2SAT) problems that always deliver solutions of expected value at least .87856times the optimal value.These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation.This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem.The best previously known approximation algorithms for these problems had perfc~rmance guarantees of ~for MAX CUT and ~for MAX 2SAT.Slight extensions of our analysis lead to a .79607-approximationalgorithm for the maximum directed cut problem (MAX DICUT) and a .758-approximationalgorithm for MAX SAT, where the best previously known approxim ation algorithms had performance guarantees of ~and ~, respectively.Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and represents the first use of :semidefinite programming in the design of approximation algorithms.

We present a general approximation technique for a large class of graph problems. Our technique mostly applies to problems of covering, at minimum cost, the vertices of a graph with trees, cycles, or paths satisfying certain requirements. In particular, many basic combinatorial optimization problems fit in this framework, including the shortest path, minimum-cost spanning tree, minimum-weight perfect matching, traveling salesman, and Steiner tree problems. Our technique produces approximation algorithms that run in $O(n^{2} \log n)$ time and come within a factor of 2 of optimal for most of these problems. For instance, we obtain a 2-approximation algorithm for the minimum-weight perfect matching problem under the triangle inequality. Our running time of $O(n^{2} \log n)$ time compares favorably with the best strongly polynomial exact algorithms running in $O(n^{3})$ time for dense graphs. A similar result is obtained for the 2-matching problem and its variants. We also derive the first approximation algorithms for many NP-complete problems, including the nonfixed point-to-point connection problem, the exact path partitioning problem, and complex location-design problems. Moreover, for the prize-collecting traveling salesman or Steiner tree problems, we obtain 2-approximation algorithms, therefore improving the previously best-known performance guarantees of 2.5 and 3, respectively [Math. Programming, 59 (1993), pp. 413–4201.

The problem of scheduling jobs on parallel machines is studied when (1) the existence of a job is not known until its unknown release date and (2) the processing requirement of a job is not known until the job is processed to completion. Two general algorithmic techniques are demonstrated for converting existing polynomial-time algorithms that require complete knowledge about the input data into algorithms that need less advance knowledge. Information-theoretic lower bounds on the length of on-line schedules are proven for several basic parallel machine models, and almost all of our algorithms construct schedules with lengths that either match or come within a constant factor of the lower bound.

We present randomized approximation algorithms for the MAX CUT and MAX 2SAT problems that always deliver solutions of expected value at least .87856times the optimal value.These algorithms use a simple and elegant technique that randomly rounds the solution to a nonlinear programming relaxation.This relaxation can be interpreted both as a semidefinite program and as an eigenvalue minimization problem.We then show how to derandomize the algorithm to obtain approximation algorithms with the same performance guarantee of .87856.The previous best-known approximation algorithms for these problems had performance guarantees of ~for MAX CUT and ~for MAX 2SAT.A slight extension of our analysis leads to a .79607-approximationalgorithm for the maximum directed cut problem, where a & approximation algorithm was the previous best-known algorithm.Our algorithm gives the first substantial progress in approximating MAX CUT in nearly twenty years, and, to the best of our knowledge, represents the first use of semidefinite programming in the design of approximation algorithms.

Yannakakis recently presented the first $\frac{3}{4}$-approximation algorithm for the Maximum Satisfiability Problem (MAX SAT). His algorithm makes nontrivial use of solutions to maximum flow problems. New, simple $\frac{3}{4}$-approximation algorithms that apply the probabilistic method/randomized rounding to the solution to a linear programming relaxation of MAX SAT are presented. It is shown that although standard randomized rounding does not give a good approximate result, the best solution of the two given by randomized rounding and a well-known algorithm of Johnson is always within $\frac{3}{4}$ of the optimal solution. It is further shown that an unusual twist on randomized rounding also yields 4-approximation algorithms. As a by-product of the analysis, a tight worst-case analysis of the relative duality gap of the linear programming relaxation is obtained.

We present the first polynomial-time approximation algorithm for finding a minimum-cost subgraph having at least a specified number of edges in each cut.This class of problems includes, among others, the generalized Steiner network problem, also called the survivable network design problem.If k is the maximum cut requirement of the problem, our solution comes within a factor of 2k of optimal.Our algorithm is primal-dual and shows the importance of this technique in designing approximation algorithms.1

The authors study the problem of scheduling jobs on parallel machines when the existence of a job is not known until an unknown release date and the processing requirement of a job is not known until the job is processed to completion. They demonstrate two general algorithmic techniques for converting existing polynomial-time algorithms that require complete knowledge about the input data into algorithms that need less advance knowledge. They prove information-theoretic lower bounds on the lengths of online schedules for several basic parallel machine models and then show that the algorithms construct schedules with lengths that either match or come within a constant factor of the lower bounds.>

In their 1971 paper on the travelling salesman problem and minimum spanning trees, Held and Karp showed that finding an optimally weighted 1-tree is equivalent to solving a linear program for the traveling salesman problem (TSP) with only node-degree constraints and subtour elimination constraints. In this paper we show that the Held-Karp 1-trees have a certain monotonicity property: given a particular instance of the symmetric TSP with triangle inequality, the cost of the minimum weighted 1-tree is monotonic with respect to the set of nodes included. As a consequence, we obtain an alternate proof of a result of Wolsey and show that linear programs with node-degree and subtour elimination constraints must have a cost at least 23OPT where OPT is the cost of the optimum solution to the TSP instance.