Dorit S. Hochbaum

Dorit S. Hochbaum: A Polynomial Time Algorithm for Rayleigh Ratio on Discrete Variables: Replacing Spectral Techniques for Expander Ratio, Normalized Cut, and Cheeger Constant. Operations Research 61(1): 184-198 (2013)

Dorit S. Hochbaum, James B. Orlin: Simplifications and speedups of the pseudoflow algorithm. Networks 61(1): 40-57 (2013)

Dorit S. Hochbaum, Asaf Levin: Approximation Algorithms for a Minimization Variant of the Order-Preserving Submatrices and for Biclustering Problems. ACM Transactions on Algorithms 9(2): 19 (2013)

Dorit S. Hochbaum, Chun-Nan Hsu, Yan T. Yang: Ranking of multidimensional drug profiling data by fractional-adjusted bi-partitional scores. Bioinformatics 28(12): 106-114 (2012)

Marjan A. Baghaie, Dorit S. Hochbaum, Bhaskar Krishnamachari: Multiflow Transmission in Delay Constrained Cooperative Wireless Networks. CoRR abs/1202.6038 (2012)

Dorit S. Hochbaum, Barak Fishbain: Nuclear threat detection with mobile distributed sensor networks. Annals OR 187(1): 45-63 (2011)

Joe Qranfal, Dorit S. Hochbaum, Germain Tanoh: Experimental Analysis of the MRF Algorithm for Segmentation of Noisy Medical Images. Algorithmic Operations Research 6(2): 79-90 (2011)

Dorit S. Hochbaum, Erick Moreno-Centeno, Phillip Yelland, Rodolfo A. Catena: Rating Customers According to Their Promptness to Adopt New Products. Operations Research 59(5): 1171-1183 (2011)

Marjan A. Baghaie, Dorit S. Hochbaum, Bhaskar Krishnamachari: On Hardness of Multiflow Transmission in Delay Constrained Cooperative Wireless Networks. GLOBECOM 2011: 1-5

Dorit S. Hochbaum: An Efficient and Effective Tool for Image Segmentation, Total Variations and Regularization. SSVM 2011: 338-349

Ilan Adler, Dorit S. Hochbaum: Benchmark Problems for Totally Unimodular Set System Auction. CoRR abs/1102.3499 (2011)

Bala G. Chandran, Dorit S. Hochbaum: Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm. CoRR abs/1105.1569 (2011)

Dorit S. Hochbaum, Asaf Levin: How to allocate review tasks for robust ranking. Acta Inf. 47(5-6): 325-345 (2010)

Tingting Cui, Dorit S. Hochbaum: Complexity of some inverse shortest path lengths problems. Networks 56(1): 20-29 (2010)

Dorit S. Hochbaum: Polynomial Time Algorithms for Ratio Regions and a Variant of Normalized Cut. IEEE Trans. Pattern Anal. Mach. Intell. 32(5): 889-898 (2010)

Dorit S. Hochbaum, Asaf Levin: Covering the edges of bipartite graphs using K_{2, 2} graphs. Theor. Comput. Sci. 411(1): 1-9 (2010)

Barak Fishbain, Dorit S. Hochbaum, Stefan Mueller: Competitive Analysis of Minimum-Cut Maximum Flow Algorithms in Vision Problems. CoRR abs/1007.4531 (2010)

Dorit S. Hochbaum: Submodular problems - approximations and algorithms. CoRR abs/1010.1945 (2010)

Dorit S. Hochbaum: Replacing spectral techniques for expander ratio, normalized cut and conductance by combinatorial flow algorithms. CoRR abs/1010.4535 (2010)

Dorit S. Hochbaum: Dynamic evolution of economically preferred facilities. European Journal of Operational Research 193(3): 649-659 (2009)

Bala G. Chandran, Dorit S. Hochbaum: A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem. Operations Research 57(2): 358-376 (2009)

Dorit S. Hochbaum, Asaf Levin: The multi-integer set cover and the facility terminal cover problem. Networks 53(1): 63-66 (2009)

Dorit S. Hochbaum: An Efficient and Effective Image Segmentation Interactive Tool. BIOSIGNALS 2009: 459-461

Dorit S. Hochbaum, Vikas Singh: An efficient algorithm for Co-segmentation. ICCV 2009: 269-276

Ravindra K. Ahuja, Dorit S. Hochbaum: Technical Note - Solving Linear Cost Dynamic Lot-Sizing Problems in O(n log n) Time. Operations Research 56(1): 255-261 (2008)

Dorit S. Hochbaum: The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem. Operations Research 56(4): 992-1009 (2008)

Dorit S. Hochbaum, Erick Moreno-Centeno: The inequality-satisfiability problem. Oper. Res. Lett. 36(2): 229-233 (2008)

Dorit S. Hochbaum: Polynomial time algorithms for bi-criteria, multi-objective and ratio problems in clustering and imaging. Part I: Normalized cut and ratio regions. CoRR abs/0803.0146 (2008)

Dorit S. Hochbaum: Complexity and algorithms for nonlinear optimization problems. Annals OR 153(1): 257-296 (2007)

Dorit S. Hochbaum, Asaf Levin: Covering the Edges of Bipartite Graphs Using K _{2, 2} Graphs. WAOA 2007: 116-127

Dorit S. Hochbaum, Asaf Levin: Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms. Discrete Optimization 3(4): 327-340 (2006)

Dorit S. Hochbaum, Asaf Levin: Methodologies and Algorithms for Group-Rankings Decision. Management Science 52(9): 1394-1408 (2006)

Dorit S. Hochbaum, Asaf Levin: Optimizing over Consecutive 1's and Circular 1's Constraints. SIAM Journal on Optimization 17(2): 311-330 (2006)

Dorit S. Hochbaum, Asaf Levin: The k-Allocation Problem and Its Variants. WAOA 2006: 253-264

Dorit S. Hochbaum: Ranking Sports Teams and the Inverse Equal Paths Problem. WINE 2006: 307-318

Dorit S. Hochbaum: Complexity and algorithms for convex network optimization and other nonlinear problems. 4OR 3(3): 171-216 (2005)

Ravindra K. Ahuja, Dorit S. Hochbaum, James B. Orlin: A Cut-Based Algorithm for the Nonlinear Dual of the Minimum Cost Network Flow Problem. Algorithmica 39(3): 189-208 (2004)

Dorit S. Hochbaum: 50th Anniversary Article: Selection, Provisioning, Shared Fixed Costs, Maximum Closure, and Implications on Algorithmic Methods Today. Management Science 50(6): 709-723 (2004)

Dorit S. Hochbaum: Monotonizing linear programs with up to two nonzeroes per column. Oper. Res. Lett. 32(1): 49-58 (2004)

Dorit S. Hochbaum: Efficient Algorithms for the Inverse Spanning-Tree Problem. Operations Research 51(5): 785-797 (2003)

Ravindra K. Ahuja, Dorit S. Hochbaum, James B. Orlin: Solving the Convex Cost Integer Dual Network Flow Problem. Management Science 49(7): 950-964 (2003)

Olivier Goldschmidt, Dorit S. Hochbaum, Asaf Levin, Eli V. Olinick: The SONET edge-partition problem. Networks 41(1): 13-23 (2003)

Dorit S. Hochbaum, Maurice Queyranne: Minimizing a Convex Cost Closure Set. SIAM J. Discrete Math. 16(2): 192-207 (2003)

Dorit S. Hochbaum: Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. European Journal of Operational Research 140(2): 291-321 (2002)

Dorit S. Hochbaum, Paul A. Tucker: Minimax problems with bitonic matrices. Networks 40(3): 113-124 (2002)

Dorit S. Hochbaum, Eli V. Olinick: The Bounded Cycle-Cover Problem. INFORMS Journal on Computing 13(2): 104-119 (2001)

Dorit S. Hochbaum: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48(4): 686-701 (2001)

Dorit S. Hochbaum: A new - old algorithm for minimum-cut and maximum-flow in closure graphs. Networks 37(4): 171-193 (2001)

Dorit S. Hochbaum, Anu Pathria: Approximating a generalization of MAX 2SAT and MIN 2SAT. Discrete Applied Mathematics 107(1-3): 41-59 (2000)

Dorit S. Hochbaum: Instant recognition of polynominal time solvability, half integrality and 2-approximations. APPROX 2000: 2-14

Dorit S. Hochbaum, Maurice Queyranne: Minimizing a Convex Cost Closure Set. ESA 2000: 256-267

Dorit S. Hochbaum, Gerhard J. Woeginger: A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources. Oper. Res. Lett. 24(1-2): 25-28 (1999)

Fabián A. Chudak, Dorit S. Hochbaum: A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Oper. Res. Lett. 25(5): 199-204 (1999)

Ravindra K. Ahuja, Dorit S. Hochbaum, James B. Orlin: Solving the Convex Cost Integer Dual Network Flow Problem. IPCO 1999: 31-44

Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, Alistair Sinclair (Eds.): Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99, Berkeley, CA, USA, August 8-11, 1999, Proceedings. Lecture Notes in Computer Science 1671, Springer 1999, isbn 3-540-66329-0

Dorit S. Hochbaum: Approximating Clique and Biclique Problems. J. Algorithms 29(1): 174-200 (1998)

Fabián A. Chudak, Michel X. Goemans, Dorit S. Hochbaum, David P. Williamson: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Oper. Res. Lett. 22(4-5): 111-118 (1998)

Dorit S. Hochbaum: Instant Recognition of Half Integrality and 2-Approximations. APPROX 1998: 99-110

Dorit S. Hochbaum: The t-Vertex Cover Problem: Extending the Half Integrality Framework with Budget Constraints. APPROX 1998: 111-122

Dorit S. Hochbaum: The Pseudoflow Algorithm and the Pseudoflow-Based Simplex for the Maximum Flow Problem. IPCO 1998: 325-337

Klaus Jansen, Dorit S. Hochbaum (Eds.): Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings. Lecture Notes in Computer Science 1444, Springer 1998, isbn 3-540-64736-8

Naveen Garg, Dorit S. Hochbaum: An O (log k)-Approximation Algorithm for the k Minimum Spanning Tree Problem in the Plane. Algorithmica 18(1): 111-121 (1997)

Dorit S. Hochbaum, Dan Landy: Scheduling with Batching: Two Job Types. Discrete Applied Mathematics 72(1-2): 99-114 (1997)

Olivier Goldschmidt, Dorit S. Hochbaum: k-edge Subgraph Problems. Discrete Applied Mathematics 74(2): 159-169 (1997)

Dorit S. Hochbaum, Anu Pathria: Generalized p-Center problems: Complexity results and approximation algorithms. European Journal of Operational Research 100(3): 594-607 (1997)

Dorit S. Hochbaum, Anu Pathria: Path Costs in Evolutionary Tree Reconstruction. Journal of Computational Biology 4(2): 163-175 (1997)

Dorit S. Hochbaum, Joseph Naor: Approximation Algorithms for Network Design Problems on Bounded Subsets. J. Algorithms 21(2): 403-414 (1996)

Dorit S. Hochbaum, Anu Pathria: The bottleneck graph partition problem. Networks 28(4): 221-225 (1996)

Olivier Goldschmidt, Dorit S. Hochbaum, Cor A. J. Hurkens, Gang Yu: Approximation Algorithms for the k-Clique Covering Problem. SIAM J. Discrete Math. 9(3): 492-509 (1996)

Dorit S. Hochbaum: An optimal test compression procedure for combinational circuits. IEEE Trans. on CAD of Integrated Circuits and Systems 15(10): 1294-1299 (1996)

Dorit S. Hochbaum, Sung-Pil Hong: About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Program. 69: 269-309 (1995)

Dorit S. Hochbaum, Joseph Naor: Simple and Fast Algorithms for Linear and Integer Programs With Two Variables per Inequality. SIAM J. Comput. 23(6): 1179-1192 (1994)

Naveen Garg, Dorit S. Hochbaum: An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. STOC 1994: 432-438

Dorit S. Hochbaum, Sridhar Seshadri: The empirical performance of a polynomial algorithm for constrained nonlinear optimization. Annals OR 43(4): 229-248 (1993)

Dorit S. Hochbaum: Why Should Biconnected Components be Identified First. Discrete Applied Mathematics 42(2): 203-210 (1993)

Olivier Goldschmidt, Dorit S. Hochbaum, Gang Yu: A Modified Greedy Heuristic for the Set Covering Problem with Improved Worst Case Bound. Inf. Process. Lett. 48(6): 305-310 (1993)

Dorit S. Hochbaum, Nimrod Megiddo, Joseph Naor, Arie Tamir: Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Math. Program. 62: 69-83 (1993)

Dorit S. Hochbaum, Ron Shamir, J. George Shanthikumar: A polynomial algorithm for an integer quadratic non-separable transportation problem. Math. Program. 55: 359-371 (1992)

Dorit S. Hochbaum, Joseph Naor: Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality. IPCO 1992: 44-59

Dorit S. Hochbaum, Ron Shamir: Minimizing the number of tardy job units under release time constraints. Discrete Applied Mathematics 28(1): 45-57 (1990)

Dorit S. Hochbaum, J. George Shanthikumar: Convex Separable Optimization Is Not Much Harder than Linear Optimization. J. ACM 37(4): 843-862 (1990)

Olivier Goldschmidt, Dorit S. Hochbaum: A Fast Perfect-Matching Algorithm in Random Graphs. SIAM J. Discrete Math. 3(1): 48-57 (1990)

Olivier Goldschmidt, Dorit S. Hochbaum: Asymptotically Optimal Linear Algorithm for the Minimum k-Cut in a Random Graph. SIAM J. Discrete Math. 3(1): 58-73 (1990)

Dorit S. Hochbaum: On the Impossibility of Strongly Polynomial Algorithms for the Allocation Problem and its Extensions. IPCO 1990: 261-273

Dorit S. Hochbaum, Ron Shamir: An O(n log2 n) Algorithm for the Maximum Weighted Tardiness Problem. Inf. Process. Lett. 31(4): 215-219 (1989)

Dorit S. Hochbaum, Arie Segev: Analysis of a flow problem with fixed charges. Networks 19(3): 291-312 (1989)

Dorit S. Hochbaum, J. George Shanthikumar: The Complexity of Nonlinear Separable Optimization. ICALP 1989: 461-472

Dorit S. Hochbaum, David B. Shmoys: A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach. SIAM J. Comput. 17(3): 539-551 (1988)

Olivier Goldschmidt, Dorit S. Hochbaum: Polynomial Algorithm for the k-Cut Problem. FOCS 1988: 444-451

Dorit S. Hochbaum, David B. Shmoys: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1): 144-162 (1987)

Dorit S. Hochbaum, Wolfgang Maass: Fast Approximation Algorithms for a Nonconvex Covering Problem. J. Algorithms 8(3): 305-323 (1987)

Dorit S. Hochbaum, David B. Shmoys: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3): 533-550 (1986)

Dorit S. Hochbaum, Takao Nishizeki, David B. Shmoys: A Better than "Best Possible" Algorithm to Edge Color Multigraphs. J. Algorithms 7(1): 79-104 (1986)

Dorit S. Hochbaum, David B. Shmoys: A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach. FSTTCS 1986: 382-393

Dorit S. Hochbaum, Wolfgang Maass: Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI. J. ACM 32(1): 130-136 (1985)

Dorit S. Hochbaum, David B. Shmoys: Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results. FOCS 1985: 79-89

Dorit S. Hochbaum, Wolfgang Maass: Approximation Schemes for Covering and Packing Problems in Robotics and VLSI. STACS 1984: 55-62

Dorit S. Hochbaum, David B. Shmoys: Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems. STOC 1984: 324-333

Dorit S. Hochbaum: Approximation Algorithms for the Set Covering and Vertex Cover Problems. SIAM J. Comput. 11(3): 555-556 (1982)

Marshall L. Fisher, Dorit S. Hochbaum: Database Location in Computer Networks. J. ACM 27(4): 718-735 (1980)