dblp.uni-trier.dewww.uni-trier.de

Dorit S. Hochbaum Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
72 Dorit S. Hochbaum: An Efficient and Effective Image Segmentation Interactive Tool. BIOSIGNALS 2009: 459-461
71EEDorit S. Hochbaum: Dynamic evolution of economically preferred facilities. European Journal of Operational Research 193(3): 649-659 (2009)
70EEDorit S. Hochbaum, Asaf Levin: The multi-integer set cover and the facility terminal cover problem. Networks 53(1): 63-66 (2009)
69EEBala 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)
2008
68EEDorit 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)
67EEDorit S. Hochbaum, Erick Moreno-Centeno: The inequality-satisfiability problem. Oper. Res. Lett. 36(2): 229-233 (2008)
66EERavindra 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)
65EEDorit S. Hochbaum: The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem. Operations Research 56(4): 992-1009 (2008)
2007
64EEDorit S. Hochbaum, Asaf Levin: Covering the Edges of Bipartite Graphs Using K 2, 2 Graphs. WAOA 2007: 116-127
63EEDorit S. Hochbaum: Complexity and algorithms for nonlinear optimization problems. Annals OR 153(1): 257-296 (2007)
2006
62EEDorit S. Hochbaum, Asaf Levin: The k-Allocation Problem and Its Variants. WAOA 2006: 253-264
61EEDorit S. Hochbaum: Ranking Sports Teams and the Inverse Equal Paths Problem. WINE 2006: 307-318
60EEDorit S. Hochbaum, Asaf Levin: Cyclical scheduling and multi-shift scheduling: Complexity and approximation algorithms. Discrete Optimization 3(4): 327-340 (2006)
2005
59EEDorit S. Hochbaum: Complexity and algorithms for convex network optimization and other nonlinear problems. 4OR 3(3): 171-216 (2005)
2004
58EERavindra 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)
57EEDorit S. Hochbaum: Monotonizing linear programs with up to two nonzeroes per column. Oper. Res. Lett. 32(1): 49-58 (2004)
2003
56EEOlivier Goldschmidt, Dorit S. Hochbaum, Asaf Levin, Eli V. Olinick: The SONET edge-partition problem. Networks 41(1): 13-23 (2003)
55EEDorit S. Hochbaum: Efficient Algorithms for the Inverse Spanning-Tree Problem. Operations Research 51(5): 785-797 (2003)
54EEDorit S. Hochbaum, Maurice Queyranne: Minimizing a Convex Cost Closure Set. SIAM J. Discrete Math. 16(2): 192-207 (2003)
2002
53EEDorit S. Hochbaum, Paul A. Tucker: Minimax problems with bitonic matrices. Networks 40(3): 113-124 (2002)
2001
52EEDorit S. Hochbaum, Eli V. Olinick: The Bounded Cycle-Cover Problem. INFORMS Journal on Computing 13(2): 104-119 (2001)
51EEDorit S. Hochbaum: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48(4): 686-701 (2001)
50EEDorit S. Hochbaum: A new - old algorithm for minimum-cut and maximum-flow in closure graphs. Networks 37(4): 171-193 (2001)
2000
49EEDorit S. Hochbaum: Instant recognition of polynominal time solvability, half integrality and 2-approximations. APPROX 2000: 2-14
48EEDorit S. Hochbaum, Maurice Queyranne: Minimizing a Convex Cost Closure Set. ESA 2000: 256-267
47 Dorit S. Hochbaum, Anu Pathria: Approximating a generalization of MAX 2SAT and MIN 2SAT. Discrete Applied Mathematics 107(1-3): 41-59 (2000)
1999
46 Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, Alistair Sinclair: 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 Springer 1999
45EERavindra K. Ahuja, Dorit S. Hochbaum, James B. Orlin: Solving the Convex Cost Integer Dual Network Flow Problem. IPCO 1999: 31-44
44EEDorit 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)
43EEFabiá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)
1998
42 Klaus Jansen, Dorit S. Hochbaum: Approximation Algorithms for Combinatorial Optimization, International Workshop APPROX'98, Aalborg, Denmark, July 18-19, 1998, Proceedings Springer 1998
41EEDorit S. Hochbaum: The t-Vertex Cover Problem: Extending the Half Integrality Framework with Budget Constraints. APPROX 1998: 111-122
40EEDorit S. Hochbaum: Instant Recognition of Half Integrality and 2-Approximations. APPROX 1998: 99-110
39EEDorit S. Hochbaum: The Pseudoflow Algorithm and the Pseudoflow-Based Simplex for the Maximum Flow Problem. IPCO 1998: 325-337
38 Dorit S. Hochbaum: Approximating Clique and Biclique Problems. J. Algorithms 29(1): 174-200 (1998)
37EEFabiá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)
1997
36 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)
35EEDorit S. Hochbaum, Dan Landy: Scheduling with Batching: Two Job Types. Discrete Applied Mathematics 72(1-2): 99-114 (1997)
34EEOlivier Goldschmidt, Dorit S. Hochbaum: k-edge Subgraph Problems. Discrete Applied Mathematics 74(2): 159-169 (1997)
33 Dorit S. Hochbaum, Anu Pathria: Path Costs in Evolutionary Tree Reconstruction. Journal of Computational Biology 4(2): 163-176 (1997)
1996
32EEDorit S. Hochbaum: An optimal test compression procedure for combinational circuits. IEEE Trans. on CAD of Integrated Circuits and Systems 15(10): 1294-1299 (1996)
31 Dorit S. Hochbaum, Joseph Naor: Approximation Algorithms for Network Design Problems on Bounded Subsets. J. Algorithms 21(2): 403-414 (1996)
30EEDorit S. Hochbaum, Anu Pathria: The bottleneck graph partition problem. Networks 28(4): 221-225 (1996)
29EEOlivier 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)
1995
28 Dorit S. Hochbaum, Sung-Pil Hong: About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Program. 69: 269-309 (1995)
1994
27EENaveen Garg, Dorit S. Hochbaum: An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane. STOC 1994: 432-438
26 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)
1993
25EEDorit S. Hochbaum: Why Should Biconnected Components be Identified First. Discrete Applied Mathematics 42(2): 203-210 (1993)
24 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)
23 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)
1992
22 Dorit S. Hochbaum, Joseph Naor: Simple and Fast Algorithms for Linear and Integer Programs with Two Variables Per Inequality. IPCO 1992: 44-59
21 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)
1990
20 Dorit S. Hochbaum: On the Impossibility of Strongly Polynomial Algorithms for the Allocation Problem and its Extensions. IPCO 1990: 261-273
19EEDorit S. Hochbaum, Ron Shamir: Minimizing the number of tardy job units under release time constraints. Discrete Applied Mathematics 28(1): 45-57 (1990)
18EEDorit S. Hochbaum, J. George Shanthikumar: Convex Separable Optimization Is Not Much Harder than Linear Optimization J. ACM 37(4): 843-862 (1990)
17 Olivier Goldschmidt, Dorit S. Hochbaum: A Fast Perfect-Matching Algorithm in Random Graphs. SIAM J. Discrete Math. 3(1): 48-57 (1990)
16 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)
1989
15EEDorit S. Hochbaum, J. George Shanthikumar: The Complexity of Nonlinear Separable Optimization. ICALP 1989: 461-472
14 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)
1988
13 Olivier Goldschmidt, Dorit S. Hochbaum: Polynomial Algorithm for the k-Cut Problem FOCS 1988: 444-451
12 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)
1987
11EEDorit S. Hochbaum, David B. Shmoys: Using dual approximation algorithms for scheduling problems theoretical and practical results. J. ACM 34(1): 144-162 (1987)
10 Dorit S. Hochbaum, Wolfgang Maass: Fast Approximation Algorithms for a Nonconvex Covering Problem. J. Algorithms 8(3): 305-323 (1987)
1986
9EEDorit S. Hochbaum, David B. Shmoys: A Polynomial Approximation Scheme for Machine Scheduling on Uniform Processors: Using the Dual Approximation Approach. FSTTCS 1986: 382-393
8EEDorit S. Hochbaum, David B. Shmoys: A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3): 533-550 (1986)
7 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)
1985
6 Dorit S. Hochbaum, David B. Shmoys: Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results FOCS 1985: 79-89
5EEDorit S. Hochbaum, Wolfgang Maass: Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI J. ACM 32(1): 130-136 (1985)
1984
4EEDorit S. Hochbaum, Wolfgang Maass: Approximation Schemes for Covering and Packing Problems in Robotics and VLSI. STACS 1984: 55-62
3 Dorit S. Hochbaum, David B. Shmoys: Powers of Graphs: A Powerful Approximation Technique for Bottleneck Problems STOC 1984: 324-333
1982
2 Dorit S. Hochbaum: Approximation Algorithms for the Set Covering and Vertex Cover Problems. SIAM J. Comput. 11(3): 555-556 (1982)
1980
1EEMarshall L. Fisher, Dorit S. Hochbaum: Database Location in Computer Networks. J. ACM 27(4): 718-735 (1980)

Coauthor Index

1Ravindra K. Ahuja [45] [58] [66]
2Bala G. Chandran [69]
3Fabián A. Chudak [37] [43]
4Marshall L. Fisher [1]
5Naveen Garg [27] [36]
6Michel X. Goemans [37]
7Olivier Goldschmidt [13] [16] [17] [24] [29] [34] [56]
8Sung-Pil Hong [28]
9Cor A. J. Hurkens [29]
10Klaus Jansen [42] [46]
11Dan Landy [35]
12Asaf Levin [56] [60] [62] [64] [70]
13Wolfgang Maass [4] [5] [10]
14Nimrod Megiddo [23]
15Erick Moreno-Centeno [67]
16Joseph Naor (Seffi Naor) [22] [23] [26] [31]
17Takao Nishizeki [7]
18Eli V. Olinick [52] [56]
19James B. Orlin [45] [58]
20Anu Pathria [30] [33] [47]
21Maurice Queyranne [48] [54]
22José D. P. Rolim [46]
23Ron Shamir [14] [19] [21]
24J. George Shanthikumar [15] [18] [21]
25David B. Shmoys [3] [6] [7] [8] [9] [11] [12]
26Alistair Sinclair [46]
27Arie Tamir [23]
28Paul A. Tucker [53]
29David P. Williamson [37]
30Gerhard J. Woeginger [44]
31Gang Yu [24] [29]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)