Dorit S. Hochbaum

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

Collaborative distances:



In proceedings 
PhD thesis 





Algorithms and complexity of range clustering.
Networks, 2019

A comparative study of the leading machine learning techniques and two new optimization algorithms.
European Journal of Operational Research, 2019

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

Algorithms and Complexity of Range Clustering.
CoRR, 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

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

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

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 Processing, 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.
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

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

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

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

Multiflow Transmission in Delay Constrained Cooperative Wireless Networks
CoRR, 2012

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

Rating Customers According to Their Promptness to Adopt New Products.
Operations Research, 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 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

Covering the edges of bipartite graphs using K2, 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

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 Inf., 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.
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

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

Technical Note - Solving Linear Cost Dynamic Lot-Sizing Problems in O(n log n) Time.
Operations Research, 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.
Annals OR, 2007

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

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

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.
Management Science, 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. Discrete Math., 2003

The SONET edge-partition problem.
Networks, 2003

Solving the Convex Cost Integer Dual Network Flow Problem.
Management Science, 2003

Efficient Algorithms for the Inverse Spanning-Tree Problem.
Operations Research, 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.
European Journal of Operational Research, 2002

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

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

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

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

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

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

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

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

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

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

Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem.
Operations Research, 1991

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

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.
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

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

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

Efficient bounds for the stable set, vertex cover and set packing problems.
Discrete Applied Mathematics, 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 k-Median Problem.
Math. Oper. Res., 1980

Database Location in Computer Networks.
J. ACM, 1980