Woeginger Gerhard J.

Gerhard J. Woeginger

Information about the author Gerhard J. Woeginger will soon be added to the site.
Found 64 papers in total
Complexity of the job insertion problem in multi-stage scheduling
Complexity of the job insertion problem in multi-stage scheduling
2007
The job insertion problem in multi-stage scheduling is: given a schedule for n jobs...
A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
A polynomial time equivalence between DNA sequencing and the exact perfect matching problem
2007
We investigate the computational complexity of a combinatorial problem that arises in...
Sports tournaments, home–away assignments, and the break minimization problem
Sports tournaments, home–away assignments, and the break minimization problem
2006
We consider the break minimization problem for fixing home–away assignments in...
On the dimension of simple monotonic games
On the dimension of simple monotonic games
2006
We show that the following problem is NP-hard, and hence computationally intractable:...
Exact algorithms for the Hamiltonian cycle problem in planar graphs
Exact algorithms for the Hamiltonian cycle problem in planar graphs
2006
We construct an exact algorithm for the Hamiltonian cycle problem in planar graphs...
On the robust assignment problem under a fixed number of cost scenarios
On the robust assignment problem under a fixed number of cost scenarios
2006
We investigate the complexity of the min–max assignment problem under a fixed...
Scheduling with step-improving processing times
Scheduling with step-improving processing times
2006
We consider the scheduling problem of minimizing the makespan on a single machine with...
The traveling salesman problem with few inner points
The traveling salesman problem with few inner points
2006
We propose two algorithms for the planar Euclidean traveling salesman problem. The...
The no-wait flow-shop paradox
The no-wait flow-shop paradox
2005
We discuss a new resource paradox in the area of scheduling: Increasing the speed of...
Minimizing makespan and preemption costs on a system of uniform machines
Minimizing makespan and preemption costs on a system of uniform machines
2005
It is well known that for preemptive scheduling on uniform machines there exist...
Monge strikes again: optimal placement of web proxies in the internet
Monge strikes again: optimal placement of web proxies in the internet
2000
In a recent paper, Li et al . study the problem of placing m web proxies in the...
A comment on scheduling on uniform machines under chain-type precedence constraints
A comment on scheduling on uniform machines under chain-type precedence constraints
2000
In a recent paper, Chekuri and Bender derive (among other results) a polynomial-time...
Approximation of the supply scheduling problem
Approximation of the supply scheduling problem
2005
The supply scheduling problem consists in finding a minimum cost delivery plan from a...
Inapproximability results for no-wait job shop scheduling
Inapproximability results for no-wait job shop scheduling
2004
We investigate the approximability of the no-wait job shop scheduling problem under...
A note on the complexity of determining optimal strategies in games with common payoffs
A note on the complexity of determining optimal strategies in games with common payoffs
2003
In a recent paper, Chu and Halpern investigated the problem of finding optimal...
On the nearest neighbor rule for the traveling salesman problem
On the nearest neighbor rule for the traveling salesman problem
2004
Rosenkrantz et al . and Johnson and Papadimitriou constructed families of TSP...
Minimum-cost dynamic flows: The series-parallel case
Minimum-cost dynamic flows: The series-parallel case
2004
A dynamic network consists of a directed graph with capacities, costs, and integral...
Complexity and approximability results for slicing floorplan designs
Complexity and approximability results for slicing floorplan designs
2003
The first stage in hierarchical approaches to floorplan design determines certain...
A branch-and-price algorithm for a hierarchical crew scheduling problem
A branch-and-price algorithm for a hierarchical crew scheduling problem
2002
We describe a real-life problem arising at a crane rental company. This problem is a...
The two-machine open shop problem: To fit or not to fit, that is the question
The two-machine open shop problem: To fit or not to fit, that is the question
2003
We consider the open shop scheduling problem with two machines. Each job consists of...
Local search for the minimum label spanning tree problem with bounded color classes
Local search for the minimum label spanning tree problem with bounded color classes
2003
In the Minimum Label Spanning tree problem, the input consists of an edge-colored...
Non-approximability results for scheduling problems with minsum criteria
Non-approximability results for scheduling problems with minsum criteria
2001
We provide several non-approximability results for deterministic scheduling problems...
On-line scheduling of unit time jobs with rejection: Minimizing the total completion time
On-line scheduling of unit time jobs with rejection: Minimizing the total completion time
2002
We consider on-line scheduling of unit time jobs on a single machine with...
A note on the bottleneck graph partition problem
A note on the bottleneck graph partition problem
1999
The bottleneck graph partition problem consists of partitioning the vertices of an...
Papers per page: