Shmoys David B.

David B. Shmoys

Information about the author David B. Shmoys will soon be added to the site.
Found 8 papers in total
Algorithms for the universal and a priori traveling salesman problem (TSP)
Algorithms for the universal and a priori traveling salesman problem (TSP)
2008
We present two simple results for generalizations of the traveling salesman problem...
Approximations and randomization to boost constraint satisfaction problem techniques
Approximations and randomization to boost constraint satisfaction problem techniques
2004
In recent years we have seen an increasing interest in combining constraint...
An improved approximation algorithm for the partial Latin square extension problem
An improved approximation algorithm for the partial Latin square extension problem
2004
Previous work on the partial Latin square extension (PLSE) problem resulted in a...
Using dual approximation algorithms for scheduling problems: Theoretical and practical results
Using dual approximation algorithms for scheduling problems: Theoretical and practical results
1987
The problem of scheduling a set of n jobs on m identical machines so as to minimize...
Jackson’s Rule for single-machine scheduling: Making a good heuristic better
Jackson’s Rule for single-machine scheduling: Making a good heuristic better
1992
The authors consider the scheduling problem in which jobs with release dates and...
Permutation vs. non-permutation flow shop schedules
Permutation vs. non-permutation flow shop schedules
1991
In studying the m -machine flow shop scheduling problem, it is common practice to...
Approximation algorithms for scheduling unrelated parallel machines
Approximation algorithms for scheduling unrelated parallel machines
1990
The authors consider the following scheduling problem. There are m parallel machines...
The parallel complexity of TSP Heuristics
The parallel complexity of TSP Heuristics
1989
The authors consider eight heuristics for constructing approximate solutions to the...
Papers per page: