Hochbaum Dorit S.

Dorit S. Hochbaum

Information about the author Dorit S. Hochbaum will soon be added to the site.
Found 39 papers in total
About strongly polynomial time algorithms for quadratic optimization over submodular constraints
About strongly polynomial time algorithms for quadratic optimization over submodular constraints
1995
The authors present new strongly polynomial algorithms for special cases of convex...
The multicovering problem
The multicovering problem
1992
The multicovering problem is: Min CX subject to AX≥b, X∈∈0,1∈, where...
A nonlinear Knapsack problem
A nonlinear Knapsack problem
1995
The nonlinear Knapsack problem is to maximize a separable concave objective function,...
Scheduling with batching: Minimizing the weighted number of tardy jobs
Scheduling with batching: Minimizing the weighted number of tardy jobs
1994
The weighted tardiness with batching (WTB) problem can be briefly described as...
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality
1993
The problem of integer programming in bounded variables, over constraints with no more...
Lower and upper bounds for the allocation problem and other nonlinear optimization problems
Lower and upper bounds for the allocation problem and other nonlinear optimization problems
1994
The paper demonstrates the impossibility of strongly polynomial algorithms for the...
Why should biconnected components be identified first
Why should biconnected components be identified first
1993
Most graph optimization problems are solved on each connected component of the graph...
A polynomial algorithm for the k-cut problem for fixed k
A polynomial algorithm for the k-cut problem for fixed k
1994
The k -cut problem is to find a partition of an edge weighted graph into k nonempty...
Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources
Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources
1994
The Transportation problem with a linear objective function is known to be solvable in...
The empirical performance of a polynomial algorithm for constrained nonlinear optimization
The empirical performance of a polynomial algorithm for constrained nonlinear optimization
1993
In an earlier paper, a polynomial algorithm based on successive piecewise linear...
An exact sublinear algorithm for the max-flow, vertex disjoint paths and communication problems on random graphs
An exact sublinear algorithm for the max-flow, vertex disjoint paths and communication problems on random graphs
1992
This paper describes a randomized algorithm for solving the maximum-flow maximum-cut...
Strongly polynomial algorithms for the high multiplicity scheduling problem
Strongly polynomial algorithms for the high multiplicity scheduling problem
1991
A high multiplicity scheduling problem consists of many jobs which can be partitioned...
A polynomial algorithm for an integer quadratic non-separable transportation problem
A polynomial algorithm for an integer quadratic non-separable transportation problem
1992
The authors study the problem of minimizing the total weighted tardiness when...
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...
An O(Nlog2N) algorithm for the maximum weighted tardiness problem
An O(Nlog2N) algorithm for the maximum weighted tardiness problem
1989
The authors give an O( n log 2 n ) algorithm which solves the scheduling problem of...
Papers per page: