Dorit S. Hochbaum

According to our database1, Dorit S. Hochbaum authored at least 149 papers between 1980 and 2021.

Collaborative distances:



In proceedings 
PhD thesis 


Online presence:



Applications and efficient algorithms for integer programming problems on monotone constraints.
Networks, 2021

Joint aggregation of cardinal and ordinal evaluations with an application to a student paper competition.
CoRR, 2021

Erratum: A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems.
SIAM J. Optim., 2020

A fully polynomial time approximation scheme for the Replenishment Storage problem.
Oper. Res. Lett., 2020

An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals.
Theory Comput. Syst., 2020

Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer.
Inf. Process. Lett., 2020

Algorithms and Complexity for Variants of Covariates Fine Balance.
CoRR, 2020

Network Flow Methods for the Minimum Covariates Imbalance Problem.
CoRR, 2020

HNCcorr: combinatorial optimization for neuron identification.
Ann. Oper. Res., 2020

The Max-Cut Decision Tree: Improving on the Accuracy and Running Time of Decision Trees.
Proceedings of the 12th International Joint Conference on Knowledge Discovery, 2020

Efficient algorithms to discover alterations with complementary functional association in cancer.
PLoS Comput. Biol., 2019

Algorithms and complexity of range clustering.
Networks, 2019

The Replenishment Schedule to Minimize Peak Storage Problem: The Gap Between the Continuous and Discrete Versions of the Problem.
Oper. Res., 2019

A comparative study of the leading machine learning techniques and two new optimization algorithms.
Eur. J. Oper. Res., 2019

Detecting Aberrant Linking Behavior in Directed Networks.
Proceedings of the 11th International Joint Conference on Knowledge Discovery, 2019

Weighted matching with pair restrictions.
Optim. Lett., 2018

Adjacency-Clustering and Its Application for Yield Prediction in Integrated Circuit Manufacturing.
Oper. Res., 2018

Complexity and approximations for submodular minimization problems on two variables per inequality constraints.
Discret. Appl. Math., 2018

DISPATCH: An Optimal Algorithm for Online Perfect Bipartite Matching with i.i.d. Arrivals.
CoRR, 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

Isolation Branching: A Branch and Bound Algorithm for the k-Terminal Cut Problem.
Proceedings of the Combinatorial Optimization and Applications, 2018

A Faster Algorithm Solving a Generalization of Isotonic Median Regression and a Class of Fused Lasso Problems.
SIAM J. Optim., 2017

High-performance geometric algorithms for sparse computation in big data analytics.
Proceedings of the 2017 IEEE International Conference on Big Data, 2017

Sparse Computation for Large-Scale Data Mining.
IEEE Trans. Big Data, 2016

A competitive study of the pseudoflow algorithm for the minimum s-t cut problem in vision applications.
J. Real Time Image Process., 2016

Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm.
CoRR, 2016

A polynomial time repeated cuts algorithm for the time cost tradeoff problem: The linear and convex crashing cost deadline problem.
Comput. Ind. Eng., 2016

Sparse-Reduced Computation - Enabling Mining of Massively-large Data Sets.
Proceedings of the 5th International Conference on Pattern Recognition Applications and Methods, 2016

Range contracts: Risk sharing and beyond.
Eur. J. Oper. Res., 2015

Efficient deployment of mobile detectors for security applications.
Proceedings of the 2015 IEEE International Conference on Industrial Engineering and Engineering Management, 2015

Security routing games with multivehicle Chinese postman problem.
Networks, 2014

The Supervised Normalized Cut Method for Detecting, Classifying, and Identifying Special Nuclear Materials.
INFORMS J. Comput., 2014

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.
Oper. Res., 2013

Evaluating performance of image segmentation criteria and techniques.
EURO J. Comput. Optim., 2013

Real-time robust target tracking in videos via graph-cuts.
Proceedings of the Real-Time Image and Video Processing 2013, 2013

Multiflow Transmission in Delay Constrained Cooperative Wireless Networks
CoRR, 2012

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

Rating Customers According to Their Promptness to Adopt New Products.
Oper. Res., 2011

Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm
CoRR, 2011

Benchmark Problems for Totally Unimodular Set System Auction
CoRR, 2011

Experimental Analysis of the MRF Algorithm for Segmentation of Noisy Medical Images.
Algorithmic Oper. Res., 2011

Nuclear threat detection with mobile distributed sensor networks.
Ann. Oper. Res., 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

Covering the edges of bipartite graphs using K<sub>2, 2</sub> 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

Submodular problems - approximations and algorithms
CoRR, 2010

Competitive Analysis of Minimum-Cut Maximum Flow Algorithms in Vision Problems
CoRR, 2010

How to allocate review tasks for robust ranking.
Acta Informatica, 2010

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.
Oper. Res., 2009

Dynamic evolution of economically preferred facilities.
Eur. J. Oper. Res., 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

The inequality-satisfiability problem.
Oper. Res. Lett., 2008

Country credit-risk rating aggregation via the separation-deviation model.
Optim. Methods Softw., 2008

The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem.
Oper. Res., 2008

Technical Note - Solving Linear Cost Dynamic Lot-Sizing Problems in <i>O</i>(<i>n</i> log <i>n</i>) Time.
Oper. Res., 2008

Polynomial time algorithms for bi-criteria, multi-objective and ratio problems in clustering and imaging. Part I: Normalized cut and ratio regions
CoRR, 2008

Complexity and algorithms for nonlinear optimization problems.
Ann. Oper. Res., 2007

Covering the Edges of Bipartite Graphs Using <i>K</i> <sub>2, 2</sub> Graphs.
Proceedings of the Approximation and Online Algorithms, 5th International Workshop, 2007

Optimizing over Consecutive 1's and Circular 1's Constraints.
SIAM J. Optim., 2006

Methodologies and Algorithms for Group-Rankings Decision.
Manag. Sci., 2006

Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms.
Discret. Optim., 2006

Ranking Sports Teams and the Inverse Equal Paths Problem.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

The <i>k</i>-Allocation Problem and Its Variants.
Proceedings of the Approximation and Online Algorithms, 4th International Workshop, 2006

Complexity and algorithms for convex network optimization and other nonlinear problems.
4OR, 2005

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.
Manag. Sci., 2004

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

Minimizing a Convex Cost Closure Set.
SIAM J. Discret. Math., 2003

The SONET edge-partition problem.
Networks, 2003

Solving the Convex Cost Integer Dual Network Flow Problem.
Manag. Sci., 2003

Efficient Algorithms for the Inverse Spanning-Tree Problem.
Oper. Res., 2003

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.
Eur. J. Oper. Res., 2002

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

Capacity Acquisition, Subcontracting, and Lot Sizing.
Manag. Sci., 2001

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

The Bounded Cycle-Cover Problem.
INFORMS J. Comput., 2001

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

Approximating a generalization of MAX 2SAT and MIN 2SAT.
Discret. Appl. Math., 2000

Instant recognition of polynominal time solvability, half integrality and 2-approximations.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

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

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 <i>t</i>-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

Path Costs in Evolutionary Tree Reconstruction.
J. Comput. Biol., 1997

Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime.
Oper. Res., 1997

A New and Fast Approach to Very Large Scale Integrated Sequential Circuit Test Generation.
Oper. Res., 1997

Generalized p-Center problems: Complexity results and approximation algorithms.
Eur. J. Oper. Res., 1997

Scheduling with Batching: Two Job Types.
Discret. Appl. Math., 1997

k-edge Subgraph Problems.
Discret. Appl. Math., 1997

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

An optimal test compression procedure for combinational circuits.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 1996

On the Complexity of the Production-Transportation Problem.
SIAM J. Optim., 1996

Approximation Algorithms for the <i>k</i>-Clique Covering Problem.
SIAM J. Discret. Math., 1996

The bottleneck graph partition problem.
Networks, 1996

Approximation Algorithms for Network Design Problems on Bounded Subsets.
J. Algorithms, 1996

A nonlinear Knapsack problem.
Oper. Res. Lett., 1995

About strongly polynomial time algorithms for quadratic optimization over submodular constraints.
Math. Program., 1995

Simple and Fast Algorithms for Linear and Integer Programs With Two Variables per Inequality.
SIAM J. Comput., 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

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.
Discret. Appl. Math., 1993

The empirical performance of a polynomial algorithm for constrained nonlinear optimization.
Ann. Oper. Res., 1993

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.
Oper. Res., 1992

Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem.
Oper. Res., 1991

Convex Separable Optimization Is Not Much Harder than Linear Optimization
J. ACM, October, 1990

Asymptotically Optimal Linear Algorithm for the Minimum <i>k</i>-Cut in a Random Graph.
SIAM J. Discret. Math., 1990

A Fast Perfect-Matching Algorithm in Random Graphs.
SIAM J. Discret. Math., 1990

Minimizing the number of tardy job units under release time constraints.
Discret. Appl. Math., 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

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

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

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

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.
Oper. Res., 1986

The Linzertorte problem, or a unified approach to painting, baking and weaving.
Discret. Appl. Math., 1986

A fast approximation algorithm for the multicovering problem.
Discret. Appl. Math., 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

Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI
J. ACM, January, 1985

A Best Possible Heuristic for the <i>k</i>-Center Problem.
Math. Oper. Res., 1985

When are NP-hard location problems easy?
Ann. Oper. Res., 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

Efficient bounds for the stable set, vertex cover and set packing problems.
Discret. Appl. Math., 1983

Approximation Algorithms for the Set Covering and Vertex Cover Problems.
SIAM J. Comput., 1982

Heuristics for the fixed cost median problem.
Math. Program., 1982

Probabilistic Analysis of the Planar <i>k</i>-Median Problem.
Math. Oper. Res., 1980

Database Location in Computer Networks.
J. ACM, 1980