# Dorit S. Hochbaum

According to our database

Collaborative distances:

^{1}, Dorit S. Hochbaum authored at least 130 papers between 1980 and 2019.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2019

A comparative study of the leading machine learning techniques and two new optimization algorithms.

European Journal of Operational Research, 2019

2018

Weighted matching with pair restrictions.

Optimization Letters, 2018

Adjacency-Clustering and Its Application for Yield Prediction in Integrated Circuit Manufacturing.

Operations Research, 2018

Complexity and approximations for submodular minimization problems on two variables per inequality constraints.

Discrete Applied Mathematics, 2018

DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals.

Proceedings of the Approximation and Online Algorithms - 16th International Workshop, 2018

Efficient Algorithms to Discover Alterations with Complementary Functional Association in Cancer.

Proceedings of the Research in Computational Molecular Biology, 2018

Isolation Branching: A Branch and Bound Algorithm for the k-Terminal Cut Problem.

Proceedings of the Combinatorial Optimization and Applications, 2018

2017

A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems.

SIAM Journal on Optimization, 2017

High-performance geometric algorithms for sparse computation in big data analytics.

Proceedings of the 2017 IEEE International Conference on Big Data, BigData 2017, 2017

2016

A competitive study of the pseudoflow algorithm for the minimum s-t cut problem in vision applications.

J. Real-Time Image Processing, 2016

A polynomial time repeated cuts algorithm for the time cost tradeoff problem: The linear and convex crashing cost deadline problem.

Computers & Industrial Engineering, 2016

Sparse-Reduced Computation - Enabling Mining of Massively-large Data Sets.

Proceedings of the 5th International Conference on Pattern Recognition Applications and Methods, 2016

2015

Range contracts: Risk sharing and beyond.

European Journal of Operational Research, 2015

Efficient deployment of mobile detectors for security applications.

Proceedings of the 2015 IEEE International Conference on Industrial Engineering and Engineering Management, 2015

2014

Security routing games with multivehicle Chinese postman problem.

Networks, 2014

The Supervised Normalized Cut Method for Detecting, Classifying, and Identifying Special Nuclear Materials.

INFORMS Journal on Computing, 2014

Sparse computation for large-scale data mining.

Proceedings of the 2014 IEEE International Conference on Big Data, 2014

2013

Approximation Algorithms for a Minimization Variant of the Order-Preserving Submatrices and for Biclustering Problems.

ACM Trans. Algorithms, 2013

Simplifications and speedups of the pseudoflow algorithm.

Networks, 2013

A Polynomial Time Algorithm for Rayleigh Ratio on Discrete Variables: Replacing Spectral Techniques for Expander Ratio, Normalized Cut, and Cheeger Constant.

Operations Research, 2013

Evaluating performance of image segmentation criteria and techniques.

EURO J. Computational Optimization, 2013

Real-time robust target tracking in videos via graph-cuts.

Proceedings of the Real-Time Image and Video Processing 2013, 2013

2012

Ranking of multidimensional drug profiling data by fractional-adjusted bi-partitional scores.

Bioinformatics, 2012

2011

Rating Customers According to Their Promptness to Adopt New Products.

Operations Research, 2011

Experimental Analysis of the MRF Algorithm for Segmentation of Noisy Medical Images.

Algorithmic Operations Research, 2011

Nuclear threat detection with mobile distributed sensor networks.

Annals OR, 2011

An Efficient and Effective Tool for Image Segmentation, Total Variations and Regularization.

Proceedings of the Scale Space and Variational Methods in Computer Vision, 2011

On Hardness of Multiflow Transmission in Delay Constrained Cooperative Wireless Networks.

Proceedings of the Global Communications Conference, 2011

2010

Covering the edges of bipartite graphs using K

_{2, 2}graphs.
Theor. Comput. Sci., 2010

Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut.

IEEE Trans. Pattern Anal. Mach. Intell., 2010

Complexity of some inverse shortest path lengths problems.

Networks, 2010

How to allocate review tasks for robust ranking.

Acta Inf., 2010

2009

The multi-integer set cover and the facility terminal cover problem.

Networks, 2009

A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem.

Operations Research, 2009

Dynamic evolution of economically preferred facilities.

European Journal of Operational Research, 2009

An efficient algorithm for Co-segmentation.

Proceedings of the IEEE 12th International Conference on Computer Vision, ICCV 2009, Kyoto, Japan, September 27, 2009

An Efficient and Effective Image Segmentation Interactive Tool.

Proceedings of the BIOSIGNALS 2009, 2009

2008

The inequality-satisfiability problem.

Oper. Res. Lett., 2008

Country credit-risk rating aggregation via the separation-deviation model.

Optimization Methods and Software, 2008

The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem.

Operations Research, 2008

Operations Research, 2008

2007

Complexity and algorithms for nonlinear optimization problems.

Annals OR, 2007

Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

2006

Optimizing over Consecutive 1's and Circular 1's Constraints.

SIAM Journal on Optimization, 2006

Methodologies and Algorithms for Group-Rankings Decision.

Management Science, 2006

Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms.

Discrete Optimization, 2006

Ranking Sports Teams and the Inverse Equal Paths Problem.

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

The

*k*-Allocation Problem and Its Variants.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

2005

Complexity and algorithms for convex network optimization and other nonlinear problems.

4OR, 2005

2004

Due Date Quotation Models and Algorithms.

Proceedings of the Handbook of Scheduling - Algorithms, Models, and Performance Analysis., 2004

Monotonizing linear programs with up to two nonzeroes per column.

Oper. Res. Lett., 2004

50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today.

Management Science, 2004

A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem.

Algorithmica, 2004

2003

The SONET edge-partition problem.

Networks, 2003

Efficient Algorithms for the Inverse Spanning-Tree Problem.

Operations Research, 2003

2002

Minimax problems with bitonic matrices.

Networks, 2002

Baseball, Optimization, and the World Wide Web.

Interfaces, 2002

Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations.

European Journal of Operational Research, 2002

2001

A new - old algorithm for minimum-cut and maximum-flow in closure graphs.

Networks, 2001

Capacity Acquisition, Subcontracting, and Lot Sizing.

Management Science, 2001

An efficient algorithm for image segmentation, Markov random fields and related problems.

J. ACM, 2001

The Bounded Cycle-Cover Problem.

INFORMS Journal on Computing, 2001

2000

Performance Analysis and Best Implementations of Old and New Algorithms for the Open-Pit Mining Problem.

Operations Research, 2000

Approximating a generalization of MAX 2SAT and MIN 2SAT.

Discrete Applied Mathematics, 2000

Minimizing a Convex Cost Closure Set.

Proceedings of the Algorithms, 2000

Instant recognition of polynominal time solvability, half integrality and 2-approximations.

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources.

Oper. Res. Lett., 1999

A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine.

Oper. Res. Lett., 1999

Solving the Convex Cost Integer Dual Network Flow Problem.

Proceedings of the Integer Programming and Combinatorial Optimization, 1999

1998

A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs.

Oper. Res. Lett., 1998

Approximating Clique and Biclique Problems.

J. Algorithms, 1998

The Pseudoflow Algorithm and the Pseudoflow-Based Simplex for the Maximum Flow Problem.

Proceedings of the Integer Programming and Combinatorial Optimization, 1998

The

*t*-Vertex Cover Problem: Extending the Half Integrality Framework with Budget Constraints.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

Instant Recognition of Half Integrality and 2-Approximations.

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 1998

1997

Path Costs in Evolutionary Tree Reconstruction.

Journal of Computational Biology, 1997

Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime.

Operations Research, 1997

A New and Fast Approach to Very Large Scale Integrated Sequential Circuit Test Generation.

Operations Research, 1997

Generalized p-Center problems: Complexity results and approximation algorithms.

European Journal of Operational Research, 1997

Scheduling with Batching: Two Job Types.

Discrete Applied Mathematics, 1997

k-edge Subgraph Problems.

Discrete Applied Mathematics, 1997

An O (log k)-Approximation Algorithm for the k Minimum Spanning Tree Problem in the Plane.

Algorithmica, 1997

1996

An optimal test compression procedure for combinational circuits.

IEEE Trans. on CAD of Integrated Circuits and Systems, 1996

On the Complexity of the Production-Transportation Problem.

SIAM Journal on Optimization, 1996

Approximation Algorithms for the

*k*-Clique Covering Problem.
SIAM J. Discrete Math., 1996

The bottleneck graph partition problem.

Networks, 1996

Approximation Algorithms for Network Design Problems on Bounded Subsets.

J. Algorithms, 1996

1995

A nonlinear Knapsack problem.

Oper. Res. Lett., 1995

About strongly polynomial time algorithms for quadratic optimization over submodular constraints.

Math. Program., 1995

1994

Scheduling with batching: minimizing the weighted number of tardy jobs.

Oper. Res. Lett., 1994

Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems.

Math. Oper. Res., 1994

A Polynomial Algorithm for the k-cut Problem for Fixed k.

Math. Oper. Res., 1994

Strongly Polynomial Algorithms for the Quadratic Transportation Problem with a Fixed Number of Sources.

Math. Oper. Res., 1994

An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane.

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality.

Math. Program., 1993

A Modified Greedy Heuristic for the Set Covering Problem with Improved Worst Case Bound.

Inf. Process. Lett., 1993

Why Should Biconnected Components be Identified First.

Discrete Applied Mathematics, 1993

The empirical performance of a polynomial algorithm for constrained nonlinear optimization.

Annals OR, 1993

1992

A polynomial algorithm for an integer quadratic non-separable transportation problem.

Math. Program., 1992

An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint Paths and Communication Problems on Random Graphs.

Operations Research, 1992

Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality.

Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

1991

Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem.

Operations Research, 1991

1990

Convex Separable Optimization Is Not Much Harder than Linear Optimization

J. ACM, October, 1990

Asymptotically Optimal Linear Algorithm for the Minimum

*k*-Cut in a Random Graph.
SIAM J. Discrete Math., 1990

A Fast Perfect-Matching Algorithm in Random Graphs.

SIAM J. Discrete Math., 1990

Minimizing the number of tardy job units under release time constraints.

Discrete Applied Mathematics, 1990

On the Impossibility of Strongly Polynomial Algorithms for the Allocation Problem and its Extensions.

Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990

1989

Analysis of a flow problem with fixed charges.

Networks, 1989

An O(n log2 n) Algorithm for the Maximum Weighted Tardiness Problem.

Inf. Process. Lett., 1989

The Complexity of Nonlinear Separable Optimization.

Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

1988

A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach.

SIAM J. Comput., 1988

Polynomial Algorithm for the k-Cut Problem

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Fast Approximation Algorithms for a Nonconvex Covering Problem.

J. Algorithms, 1987

Using dual approximation algorithms for scheduling problems theoretical and practical results.

J. ACM, 1987

1986

A Better than "Best Possible" Algorithm to Edge Color Multigraphs.

J. Algorithms, 1986

A unified approach to approximation algorithms for bottleneck problems.

J. ACM, 1986

OR Practice - Lagrangian Relaxation for Testing Infeasibility in VLSI Routing.

Operations Research, 1986

The Linzertorte problem, or a unified approach to painting, baking and weaving.

Discrete Applied Mathematics, 1986

A fast approximation algorithm for the multicovering problem.

Discrete Applied Mathematics, 1986

A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach.

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

1985

Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI

J. ACM, January, 1985

A Best Possible Heuristic for the

*k*-Center Problem.
Math. Oper. Res., 1985

Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

When are NP-hard location problems easy?

Annals OR, 1984

Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Approximation Schemes for Covering and Packing Problems in Robotics and VLSI.

Proceedings of the STACS 84, 1984

1983

Efficient bounds for the stable set, vertex cover and set packing problems.

Discrete Applied Mathematics, 1983

1982

Approximation Algorithms for the Set Covering and Vertex Cover Problems.

SIAM J. Comput., 1982

Heuristics for the fixed cost median problem.

Math. Program., 1982

1980

Probabilistic Analysis of the Planar

*k*-Median Problem.
Math. Oper. Res., 1980

Database Location in Computer Networks.

J. ACM, 1980