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
Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
Minimum-cost strong network orientation problems: Classification, complexity, and algorithms
1999
In the minimum-cost strong network orientation problem (MCSO), we are given an...
Optimal on-line algorithms for variable-sized bin covering
Optimal on-line algorithms for variable-sized bin covering
1999
We deal with the variable-sized bin covering problem: Given a list L of items in (0,1]...
A comment on consecutive-2-out-of-n systems
A comment on consecutive-2-out-of-n systems
2001
In 1986, Du and Hwang proved that the probability of failure in a cyclic double-loop...
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...
Randomized on-line scheduling on two uniform machines
Randomized on-line scheduling on two uniform machines
2001
We study the problem of on-line scheduling on two uniform machines with speeds 1 and s...
Approximation algorithms for the multiprocessor open shop scheduling problem
Approximation algorithms for the multiprocessor open shop scheduling problem
1999
We investigate the multiprocessor multi-stage open-shop scheduling problem. In this...
On-line scheduling on a single machine: Maximizing the number of early jobs
On-line scheduling on a single machine: Maximizing the number of early jobs
2000
This note deals with the scheduling problem of maximizing the number of early jobs on...
Semi-online scheduling with decreasing job sizes
Semi-online scheduling with decreasing job sizes
2000
We investigate the problem of semi-online scheduling jobs on m identical parallel...
The maximum travelling salesman problem on symmetric Demidenko matrices
The maximum travelling salesman problem on symmetric Demidenko matrices
2000
It is well-known that the Travelling Salesman Problem (TSP) is solvable in polynomial...
When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme?
When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme?
2000
We derive results of the following flavor: If a combinatorial optimization problem can...
Polynomial time approximation algorithms for machine scheduling: Ten open problems
Polynomial time approximation algorithms for machine scheduling: Ten open problems
1999
We discuss what we consider to be the 10 most vexing open questions in the area of...
The computational complexity of a bin packing game
The computational complexity of a bin packing game
1994
In this paper we investigate the following game: two players I and II must alternately...
One, two, three, many, or: complexity aspects of dynamic network flows with dedicated arcs
One, two, three, many, or: complexity aspects of dynamic network flows with dedicated arcs
1998
A dynamic network consists of a directed graph with a source s, a sink t and...
A solvable case of the quadratic assignment problem
A solvable case of the quadratic assignment problem
1998
This short note investigates a restricted version of the quadratic assignment problem...
A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources
A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources
1999
We investigate a special case of the bottleneck transportation problem where the...
An approximation scheme for minimizing agreeably weighted variance on a single machine
An approximation scheme for minimizing agreeably weighted variance on a single machine
1999
We consider the problem of minimizing the weighted variance of job completion times on...
Sensitivity analysis for knapsack problems: Another negative result
Sensitivity analysis for knapsack problems: Another negative result
1999
We answer a question of Blair on the computational complexity of a problem related to...
The disjoint cliques problem
The disjoint cliques problem
1997
Given a graph G = ( V, E ), we consider the problem of finding a set of D pairwise...
Three easy special cases of the Euclidean travelling salesman problem
Three easy special cases of the Euclidean travelling salesman problem
1997
It is known that in case the distance matrix in the Travelling Salesman Problem (TSP)...
Vehicle scheduling in 2-cycle flexible manufacturing systems
Vehicle scheduling in 2-cycle flexible manufacturing systems
1994
Flexible manufacturing systems (FMSs) have received much attention recently due to...
Approximation schemes for scheduling on parallel machines
Approximation schemes for scheduling on parallel machines
1998
We discuss scheduling problems with m identical machines and n jobs where each job has...
A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times
A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times
1998
We investigate the single-machine sequencing problem in which each job has a...
Time complexity and linear-time approximation of the ancient two-machine flow shop
Time complexity and linear-time approximation of the ancient two-machine flow shop
1998
We consider the scheduling problems F2∥C max and F2|no-wait|C max ,...
Makespan minimization in open shops: A polynomial time approximation scheme
Makespan minimization in open shops: A polynomial time approximation scheme
1998
In this paper, we demonstrate the existence of a polynominal time approximation scheme...
Papers per page: