Arrow Research search

Author name cluster

David P. Williamson

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

24 papers
2 author rows

Possible papers

24

TCS Journal 2006 Journal Article

On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems

  • R.N. Uma
  • Joel Wein
  • David P. Williamson

Enumerative approaches to solving optimization problems, such as branch and bound, require a subroutine that produces a lower bound on the value of the optimal solution. In the domain of scheduling problems the requisite lower bound has typically been derived from either the solution to a linear-programming (LP) relaxation of the problem or the solution to a combinatorial relaxation. In this paper we investigate, from a theoretical perspective, the relationship between several LP-based lower bounds and combinatorial lower bounds for three scheduling problems in which the goal is to minimize the average weighted completion time of the jobs scheduled. We establish a number of facts about the relationship between these different sorts of lower bounds, including the equivalence of certain LP-based lower bounds for these problems to combinatorial lower bounds used in successful branch-and-bound algorithms. As a result, we obtain the first worst-case analysis of the quality of the lower bounds delivered by these combinatorial relaxations.

Details DOI

FOCS Conference 2001 Conference Paper

An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem

  • Lisa Fleischer
  • Kamal Jain
  • David P. Williamson

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.

Details

STOC Conference 2001 Conference Paper

Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming

  • Michel X. Goemans
  • David P. Williamson

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, e i2π/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. In particular, we consider the problem of maximizing the total weight of satisfied equations x u -x v ≡c (mod 3) and inequations x u -x v ≢c (mod 3), where x u ∈ {0,1,2} u . This problem can be used to model the MAX-3-CUT problem and a directed variant we call MAX-3-DICUT. For the general problem, we obtain a .79373-approximation algorithm. If the instance contains only inequations (as it does for MAX-3-CUT), we obtain a performance guarantee of 7/12 + 3/(4π 2 ) arccos 2 (-1/4)≈.83601. This compares with proven performance guarantees of .800217 for MAX-3-CUT (by Frieze and Jerrum [7]) and 1/3 + 10 -8 for the general problem (by Andersson, Engebretson, and Håstad [2]). It matches the guarantee of .836008 for MAX-3-CUT found independently by de Klerk, Pasechnik, and Warners [4]. We show that all these algorithms are in fact identical in the case of MAX-3-CUT.

Details

FOCS Conference 1996 Conference Paper

Gadgets, Approximation, and Linear Programming (extended abstract)

  • Luca Trevisan 0001
  • Gregory B. Sorkin
  • Madhu Sudan 0001
  • David P. Williamson

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.

Details

FOCS Conference 1991 Conference Paper

Scheduling Parallel Machines On-Line

  • David B. Shmoys
  • Joel Wein
  • David P. Williamson

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. >

Details
v2026.09.13