# zbMATH — the first resource for mathematics

## Hochbaum, Dorit S.

Compute Distance To:
 Author ID: hochbaum.dorit-s Published as: Hochbaum, D. S.; Hochbaum, Dorit; Hochbaum, Dorit S. External Links: MGP · Wikidata · GND
 Documents Indexed: 121 Publications since 1980, including 2 Books
all top 5

#### Co-Authors

 29 single-authored 10 Levin, Asaf 8 Shmoys, David B. 7 Goldschmidt, Olivier 5 Shamir, Ron 4 Ahuja, Ravindra K. 4 Orlin, James B. 4 Pathria, Anu 3 Landy, Dan 3 Maass, Wolfgang 3 Moreno-Centeno, Erick 3 Naor, Joseph Seffi 3 Rao, Xu 3 Velednitsky, Mark 2 Chang, Minjun 2 Chudak, Fabián A. 2 Cosares, Steven 2 Fisher, Marshall L. 2 Garg, Naveen Kumar 2 Hall, Nicholas G. 2 Hong, Sung-Pil 2 Lu, Cheng 2 Lyu, Cheng 2 Olinick, Eli V. 2 Queyranne, Maurice 2 Shanthikumar, Jeyaveerasingam George 2 Spaen, Quico 2 Yu, Gang 1 Adams, Joseph Brian 1 Alon, Noga M. 1 Atamtürk, Alper 1 Baumann, Pierre 1 Bertelli, Erik 1 Catena, Rodolfo A. 1 Chandran, Bala G. 1 Cui, Tingting 1 Feo, Thomas A. 1 Fishbain, Barak 1 Goemans, Michel X. 1 Hurkens, Cor A. J. 1 Jansen, Klaus 1 Liu, Sheng 1 Megiddo, Nimrod 1 Nishizeki, Takao 1 Ordóñez, Fernando 1 Qranfal, Joe 1 Rolim, José D. P. 1 Segev, Arie 1 Seshadri, Sridhar 1 Sinclair, Alistair 1 Steele, J. Michael 1 Tamir, Arie 1 Tanoh, Germain 1 Tucker, Paul A. 1 Wagner, Michael R. 1 Wigderson, Edna 1 Williamson, David P. 1 Woeginger, Gerhard Johannes 1 Yang, Yatao 1 Yelland, Phillip
all top 5

#### Serials

 13 Operations Research 10 Networks 9 Discrete Applied Mathematics 8 Operations Research Letters 7 European Journal of Operational Research 5 Mathematics of Operations Research 4 Journal of Algorithms 4 SIAM Journal on Discrete Mathematics 4 SIAM Journal on Optimization 3 Information Processing Letters 3 Journal of the Association for Computing Machinery 3 SIAM Journal on Computing 3 SIAM Journal on Algebraic and Discrete Methods 3 Annals of Operations Research 3 Mathematical Programming. Series A. Series B 2 Management Science 2 Algorithmica 1 Acta Informatica 1 Advances in Applied Probability 1 Mathematical Programming 1 Naval Research Logistics 1 Theoretical Computer Science 1 Linear Algebra and its Applications 1 INFORMS Journal on Computing 1 Theory of Computing Systems 1 Optimization Methods & Software 1 Journal of the ACM 1 4OR 1 Discrete Optimization 1 Lecture Notes in Computer Science 1 Algorithmic Operations Research 1 Optimization Letters 1 Numerical Mathematics: Theory, Methods and Applications 1 ACM Transactions on Algorithms 1 EURO Journal on Computational Optimization
all top 5

#### Fields

 91 Operations research, mathematical programming (90-XX) 53 Computer science (68-XX) 26 Combinatorics (05-XX) 6 Numerical analysis (65-XX) 5 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 4 Statistics (62-XX) 3 Convex and discrete geometry (52-XX) 3 Biology and other natural sciences (92-XX) 3 Information and communication theory, circuits (94-XX) 2 General and overarching topics; collections (00-XX) 1 Number theory (11-XX) 1 Probability theory and stochastic processes (60-XX)

#### Citations contained in zbMATH Open

96 Publications have been cited 1,665 times in 1,388 Documents Cited by Year
Approximation algorithms for NP-hard problems. Zbl 1368.68010
Hochbaum, Dorit S. (ed.)
1996
Approximation schemes for covering and packing problems in image processing and VLSI. Zbl 0633.68027
Hochbaum, Dorit S.; Maass, Wolfgang
1985
Approximation algorithms for the set covering and vertex cover problems. Zbl 0486.68067
Hochbaum, Dorit S.
1982
A best possible heuristic for the k-center problem. Zbl 0565.90015
Hochbaum, Dorit S.; Shmoys, David B.
1985
A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. Zbl 0647.68040
Hochbaum, Dorit S.; Shmoys, David B.
1988
Convex separable optimization is not much harder than linear optimization. Zbl 0721.90060
Hochbaum, Dorit S.; Shanthikumar, J. George
1990
Efficient bounds for the stable set, vertex cover and set packing problems. Zbl 0523.05055
Hochbaum, Dorit S.
1983
A polynomial algorithm for the $$k$$-cut problem for fixed $$k$$. Zbl 0809.90125
Goldschmidt, Olivier; Hochbaum, Dorit S.
1994
Scheduling semiconductor burn-in operations to minimize total flowtime. Zbl 0895.90116
Hochbaum, Dorit S.; Landy, Dan
1997
Simple and fast algorithms for linear and integer programs with two variables per inequality. Zbl 0831.90089
Hochbaum, Dorit S.; Naor, Joseph
1994
Heuristics for the fixed cost median problem. Zbl 0473.90029
Hochbaum, Dorit S.
1982
Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Zbl 0820.90082
Hochbaum, Dorit S.
1994
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Zbl 0802.90080
Hochbaum, Dorit S.; Megiddo, Nimrod; Naor, Joseph; Tamir, Arie
1993
A nonlinear knapsack problem. Zbl 0838.90092
Hochbaum, Dorit S.
1995
About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Zbl 0844.90061
Hochbaum, Dorit S.; Hong, Sung-Pil
1995
Strongly polynomial algorithms for the high multiplicity scheduling problem. Zbl 0736.90043
Hochbaum, Dorit S.; Shamir, Ron
1991
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Zbl 0920.90137
Chudak, Fabián A.; Goemans, Michel X.; Hochbaum, Dorit S.; Williamson, David P.
1998
A fast approximation algorithm for the multicovering problem. Zbl 0602.90110
Hall, Nicholas G.; Hochbaum, Dorit S.
1986
An efficient algorithm for image segmentation, Markov random fields and related problems. Zbl 1127.68474
Hochbaum, Dorit S.
2001
Approximating clique and biclique problems. Zbl 0919.68056
Hochbaum, Dorit S.
1998
The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Zbl 1167.90394
Hochbaum, Dorit S.
2008
Scheduling with batching: Minimizing the weighted number of tardy jobs. Zbl 0820.90052
Hochbaum, Dorit S.; Landy, Dan
1994
Database location in computer networks. Zbl 0445.68071
Fisher, Marshall L.; Hochbaum, Dorit S.
1980
Solving the convex cost integer dual network flow problem. Zbl 1232.90317
Ahuja, Ravindra K.; Hochbaum, Dorit S.; Orlin, James B.
2003
Efficient algorithms for the inverse spanning-tree problem. Zbl 1165.90658
Hochbaum, Dorit S.
2003
Capacity acquisition, subcontracting, and lot sizing. Zbl 1232.90008
Atamtürk, Alper; Hochbaum, Dorit S.
2001
Analysis of the greedy approach in problems of maximum $$k$$-coverage. Zbl 0938.90026
Hochbaum, Dorit S.; Pathria, Anu
1998
Analysis of a flow problem with fixed charges. Zbl 0673.90035
Hochbaum, Dorit S.; Segev, Arie
1989
Minimizing the number of tardy job units under release time constraints. Zbl 0707.90049
Hochbaum, Dorit S.; Shamir, Ron
1990
An algorithm for the detection and construction of Monge sequences. Zbl 0666.65044
Alon, Noga; Cosares, Steven; Hochbaum, Dorit S.; Shamir, Ron
1989
The SONET edge-partition problem. Zbl 1026.90076
Goldschmidt, Olivier; Hochbaum, Dorit S.; Levin, Asaf; Olinick, Eli V.
2003
A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Zbl 0958.90042
Chudak, Fabián A.; Hochbaum, Dorit S.
1999
Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources. Zbl 0802.90073
Cosares, Steven; Hochbaum, Dorit S.
1994
Minimizing a convex Cost closure set. Zbl 1041.68070
Hochbaum, Dorit S.; Queyranne, Maurice
2003
Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. Zbl 1001.90050
Hochbaum, Dorit S.
2002
Complexity and algorithms for nonlinear optimization problems. Zbl 1159.90485
Hochbaum, Dorit S.
2007
Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms. Zbl 1112.90023
Hochbaum, Dorit S.; Levin, Asaf
2006
Fast approximation algorithms for a nonconvex covering problem. Zbl 0636.68082
Hochbaum, Dorit S.; Maass, Wolfgang
1987
Probabilistic analysis of the planar K-median problem. Zbl 0435.90057
Fisher, M. L.; Hochbaum, D. S.
1980
A polynomial algorithm for an integer quadratic non-separable transportation problem. Zbl 0761.90061
Hochbaum, Dorit S.; Shamir, Ron; Shanthikumar, J. George
1992
The $$t$$-vertex cover problem: Extending the half integrality framework with budget constraints. Zbl 0908.90213
Hochbaum, Dorit S.
1998
A modified greedy heuristic for the set covering problem with improved worst case bound. Zbl 0811.68099
Goldschmidt, Olivier; Hochbaum, Dorit S.; Yu, Gang
1993
A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Zbl 1181.90271
Chandran, Bala G.; Hochbaum, Dorit S.
2009
Complexity and algorithms for convex network optimization and other nonlinear problems. Zbl 1099.90059
Hochbaum, Dorit S.
2005
$$k$$-edge subgraph problems. Zbl 0870.68111
Goldschmidt, Olivier; Hochbaum, Dorit S.
1997
A better than ”best possible” algorithm to edge color multigraphs. Zbl 0594.68041
Hochbaum, Dorit S.; Nishizeki, Takao; Shmoys, David B.
1986
An O$$(\log k)$$-approximation algorithm for the $$k$$ minimum spanning tree problem in the plane. Zbl 0866.68076
Garg, N.; Hochbaum, D. S.
1997
A new-old algorithm for minimum-cut and maximum-flow in closure graphs. Zbl 1044.90083
Hochbaum, Dorit S.
2001
An $$O(n \log^ 2\,n)$$ algorithm for the maximum weighted tardiness problem. Zbl 0672.68011
Hochbaum, Dorit S.; Shamir, Ron
1989
Optimizing over consecutive 1’s and circular 1’s constraints. Zbl 1165.90607
Hochbaum, Dorit S.; Levin, Asaf
2006
A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem. Zbl 1134.90512
Ahuja, Ravindra K.; Hochbaum, Dorit S.; Orlin, James B.
2004
Monotonizing linear programs with up to two nonzeroes per column. Zbl 1056.90105
Hochbaum, Dorit S.
2004
Generalized $$p$$-center problems: Complexity results and approximation algorithms. Zbl 0918.90098
Hochbaum, Dorit S.; Pathria, Anu
1997
Solving linear cost dynamic lot-sizing problems in $$O(n \log n)$$ time. Zbl 1167.90307
Ahuja, Ravindra K.; Hochbaum, Dorit S.
2008
Solving the convex cost integer dual network flow problem. Zbl 0948.90116
Ahuja, Ravindra K.; Hochbaum, Dorit S.; Orlin, James B.
1999
Approximation algorithms for the $$k$$-clique covering problem. Zbl 0857.05086
Goldschmidt, Olivier; Hochbaum, Dorit S.; Hurkens, Cor; Yu, Gang
1996
Steinhaus’s geometric location problem for random samples in the plane. Zbl 0501.60040
Hochbaum, Dorit; Steele, J. Michael
1982
A polynomial time algorithm for Rayleigh ratio on discrete variables: replacing spectral techniques for expander ratio, normalized cut, and Cheeger constant. Zbl 1267.90149
Hochbaum, Dorit S.
2013
Instant recognition of half integrality and 2-approximations. Zbl 0911.90261
Hochbaum, Dorit S.
1998
Why should biconnected components be identified first. Zbl 0789.90084
Hochbaum, Dorit S.
1993
An $$O(| V| ^ 2)$$ algorithm for the planar 3-cut problem. Zbl 0572.05040
Hochbaum, Dorit S.; Shmoys, David B.
1985
On the fractional solution to the set covering problem. Zbl 0518.90055
Hochbaum, Dorit S.
1983
Security routing games with multivehicle Chinese postman problem. Zbl 1390.90167
Hochbaum, Dorit S.; Lyu, Cheng; Ordóñez, Fernando
2014
Nuclear threat detection with mobile distributed sensor networks. Zbl 1225.90016
Hochbaum, Dorit S.; Fishbain, Barak
2011
Complexity of some inverse shortest path lengths problems. Zbl 1208.05141
Cui, Tingting; Hochbaum, Dorit S.
2010
The bounded cycle-cover problem. Zbl 1238.90131
Hochbaum, Dorit S.; Olinick, Eli V.
2001
A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources. Zbl 0956.90019
Hochbaum, Dorit S.; Woeginger, Gerhard J.
1999
The bottleneck graph partition problem. Zbl 0873.90102
Hochbaum, Dorit S.; Pathria, Anu
1996
On the complexity of the production-transportation problem. Zbl 0845.90087
Hochbaum, Dorit S.; Hong, Sung-Pil
1996
An $$O(\log k)$$ approximation algorithm for the $$k$$ minimum spanning tree problem in the plane. Zbl 1344.68285
Garg, Naveen; Hochbaum, Dorit S.
1994
A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximation approach. Zbl 0623.68033
Hochbaum, Dorit S.; Shmoys, David B.
1986
Easy solutions for the K-center problem or the dominating set problem on random graphs. Zbl 0562.68029
Hochbaum, Dorit S.
1985
Evaluating performance of image segmentation criteria and techniques. Zbl 1307.90006
Hochbaum, Dorit S.; Lyu, Cheng; Bertelli, Erik
2013
Multi-label Markov random fields as an efficient and effective tool for image segmentation, total variations and regularization. Zbl 1289.68201
Hochbaum, Dorit S.
2013
The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem. Zbl 0911.90154
Hochbaum, Dorit S.
1998
Scheduling with batching: Two job types. Zbl 0873.90050
Hochbaum, Dorit S.; Landy, Dan
1997
The multicovering problem. Zbl 0759.90072
Hall, Nicholas G.; Hochbaum, Dorit S.
1992
Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem. Zbl 0596.90093
Hochbaum, Dorit S.; Shmoys, David B.
1986
When are NP-hard location problems easy? Zbl 0671.90019
Hochbaum, Dorit S.
1984
Approximation schemes for covering and packing problems in robotics and VLSI. Zbl 0557.68035
Hochbaum, Dorit S.; Maass, Wolfgang
1984
The replenishment schedule to minimize peak storage problem: the gap between the continuous and discrete versions of the problem. Zbl 1444.90014
Hochbaum, Dorit S.; Rao, Xu
2019
Algorithms and complexity of range clustering. Zbl 1416.62341
Hochbaum, Dorit S.
2019
A comparative study of the leading machine learning techniques and two new optimization algorithms. Zbl 1403.90560
Baumann, P.; Hochbaum, D. S.; Yang, Y. T.
2019
A faster algorithm solving a generalization of isotonic median regression and a class of fused Lasso problems. Zbl 1383.90009
Hochbaum, Dorit S.; Lu, Cheng
2017
Approximation algorithms for a minimization variant of the order-preserving submatrices and for biclustering problems. Zbl 1301.68273
Hochbaum, Dorit S.; Levin, Asaf
2013
Simplifications and speedups of the pseudoflow algorithm. Zbl 1269.90129
Hochbaum, Dorit S.; Orlin, James B.
2013
Rating customers according to their promptness to adopt new products. Zbl 1233.90204
Hochbaum, Dorit S.; Moreno-Centeno, Erick; Yelland, Phillip; Catena, Rodolfo A.
2011
How to allocate review tasks for robust ranking. Zbl 1210.90166
Hochbaum, Dorit S.; Levin, Asaf
2010
Covering the edges of bipartite graphs using $$K_{2,2}$$ graphs. Zbl 1187.68343
Hochbaum, Dorit S.; Levin, Asaf
2010
Country credit-risk rating aggregation via the separation-deviation model. Zbl 1154.90335
Hochbaum, Dorit S.; Moreno-Centeno, Erick
2008
Covering the edges of bipartite graphs using $$K _{2,2}$$ graphs. Zbl 1130.90409
Hochbaum, Dorit S.; Levin, Asaf
2008
Minimax problems with bitonic matrices. Zbl 1020.90046
Hochbaum, Dorit S.; Tucker, Paul A.
2002
Minimizing a convex cost closure set. Zbl 0974.90016
Hochbaum, Dorit S.; Queyranne, Maurice
2000
Approximating a generalization of MAX 2SAT and MIN 2SAT. Zbl 0971.68070
Hochbaum, Dorit S.; Pathria, Anu
2000
The empirical performance of a polynomial algorithm for constrained nonlinear optimization. Zbl 0786.90066
1993
A fast perfect-matching algorithm in random graphs. Zbl 0733.05072
Goldschmidt, Oliver; Hochbaum, Dorit S.
1990
The replenishment schedule to minimize peak storage problem: the gap between the continuous and discrete versions of the problem. Zbl 1444.90014
Hochbaum, Dorit S.; Rao, Xu
2019
Algorithms and complexity of range clustering. Zbl 1416.62341
Hochbaum, Dorit S.
2019
A comparative study of the leading machine learning techniques and two new optimization algorithms. Zbl 1403.90560
Baumann, P.; Hochbaum, D. S.; Yang, Y. T.
2019
A faster algorithm solving a generalization of isotonic median regression and a class of fused Lasso problems. Zbl 1383.90009
Hochbaum, Dorit S.; Lu, Cheng
2017
Security routing games with multivehicle Chinese postman problem. Zbl 1390.90167
Hochbaum, Dorit S.; Lyu, Cheng; Ordóñez, Fernando
2014
A polynomial time algorithm for Rayleigh ratio on discrete variables: replacing spectral techniques for expander ratio, normalized cut, and Cheeger constant. Zbl 1267.90149
Hochbaum, Dorit S.
2013
Evaluating performance of image segmentation criteria and techniques. Zbl 1307.90006
Hochbaum, Dorit S.; Lyu, Cheng; Bertelli, Erik
2013
Multi-label Markov random fields as an efficient and effective tool for image segmentation, total variations and regularization. Zbl 1289.68201
Hochbaum, Dorit S.
2013
Approximation algorithms for a minimization variant of the order-preserving submatrices and for biclustering problems. Zbl 1301.68273
Hochbaum, Dorit S.; Levin, Asaf
2013
Simplifications and speedups of the pseudoflow algorithm. Zbl 1269.90129
Hochbaum, Dorit S.; Orlin, James B.
2013
Nuclear threat detection with mobile distributed sensor networks. Zbl 1225.90016
Hochbaum, Dorit S.; Fishbain, Barak
2011
Rating customers according to their promptness to adopt new products. Zbl 1233.90204
Hochbaum, Dorit S.; Moreno-Centeno, Erick; Yelland, Phillip; Catena, Rodolfo A.
2011
Complexity of some inverse shortest path lengths problems. Zbl 1208.05141
Cui, Tingting; Hochbaum, Dorit S.
2010
How to allocate review tasks for robust ranking. Zbl 1210.90166
Hochbaum, Dorit S.; Levin, Asaf
2010
Covering the edges of bipartite graphs using $$K_{2,2}$$ graphs. Zbl 1187.68343
Hochbaum, Dorit S.; Levin, Asaf
2010
A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Zbl 1181.90271
Chandran, Bala G.; Hochbaum, Dorit S.
2009
The pseudoflow algorithm: A new algorithm for the maximum-flow problem. Zbl 1167.90394
Hochbaum, Dorit S.
2008
Solving linear cost dynamic lot-sizing problems in $$O(n \log n)$$ time. Zbl 1167.90307
Ahuja, Ravindra K.; Hochbaum, Dorit S.
2008
Country credit-risk rating aggregation via the separation-deviation model. Zbl 1154.90335
Hochbaum, Dorit S.; Moreno-Centeno, Erick
2008
Covering the edges of bipartite graphs using $$K _{2,2}$$ graphs. Zbl 1130.90409
Hochbaum, Dorit S.; Levin, Asaf
2008
Complexity and algorithms for nonlinear optimization problems. Zbl 1159.90485
Hochbaum, Dorit S.
2007
Cyclical scheduling and multi-shift scheduling: complexity and approximation algorithms. Zbl 1112.90023
Hochbaum, Dorit S.; Levin, Asaf
2006
Optimizing over consecutive 1’s and circular 1’s constraints. Zbl 1165.90607
Hochbaum, Dorit S.; Levin, Asaf
2006
Complexity and algorithms for convex network optimization and other nonlinear problems. Zbl 1099.90059
Hochbaum, Dorit S.
2005
A cut-based algorithm for the nonlinear dual of the minimum cost network flow problem. Zbl 1134.90512
Ahuja, Ravindra K.; Hochbaum, Dorit S.; Orlin, James B.
2004
Monotonizing linear programs with up to two nonzeroes per column. Zbl 1056.90105
Hochbaum, Dorit S.
2004
Solving the convex cost integer dual network flow problem. Zbl 1232.90317
Ahuja, Ravindra K.; Hochbaum, Dorit S.; Orlin, James B.
2003
Efficient algorithms for the inverse spanning-tree problem. Zbl 1165.90658
Hochbaum, Dorit S.
2003
The SONET edge-partition problem. Zbl 1026.90076
Goldschmidt, Olivier; Hochbaum, Dorit S.; Levin, Asaf; Olinick, Eli V.
2003
Minimizing a convex Cost closure set. Zbl 1041.68070
Hochbaum, Dorit S.; Queyranne, Maurice
2003
Solving integer programs over monotone inequalities in three variables: A framework for half integrality and good approximations. Zbl 1001.90050
Hochbaum, Dorit S.
2002
Minimax problems with bitonic matrices. Zbl 1020.90046
Hochbaum, Dorit S.; Tucker, Paul A.
2002
An efficient algorithm for image segmentation, Markov random fields and related problems. Zbl 1127.68474
Hochbaum, Dorit S.
2001
Capacity acquisition, subcontracting, and lot sizing. Zbl 1232.90008
Atamtürk, Alper; Hochbaum, Dorit S.
2001
A new-old algorithm for minimum-cut and maximum-flow in closure graphs. Zbl 1044.90083
Hochbaum, Dorit S.
2001
The bounded cycle-cover problem. Zbl 1238.90131
Hochbaum, Dorit S.; Olinick, Eli V.
2001
Minimizing a convex cost closure set. Zbl 0974.90016
Hochbaum, Dorit S.; Queyranne, Maurice
2000
Approximating a generalization of MAX 2SAT and MIN 2SAT. Zbl 0971.68070
Hochbaum, Dorit S.; Pathria, Anu
2000
A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Zbl 0958.90042
Chudak, Fabián A.; Hochbaum, Dorit S.
1999
Solving the convex cost integer dual network flow problem. Zbl 0948.90116
Ahuja, Ravindra K.; Hochbaum, Dorit S.; Orlin, James B.
1999
A linear-time algorithm for the bottleneck transportation problem with a fixed number of sources. Zbl 0956.90019
Hochbaum, Dorit S.; Woeginger, Gerhard J.
1999
A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs. Zbl 0920.90137
Chudak, Fabián A.; Goemans, Michel X.; Hochbaum, Dorit S.; Williamson, David P.
1998
Approximating clique and biclique problems. Zbl 0919.68056
Hochbaum, Dorit S.
1998
Analysis of the greedy approach in problems of maximum $$k$$-coverage. Zbl 0938.90026
Hochbaum, Dorit S.; Pathria, Anu
1998
The $$t$$-vertex cover problem: Extending the half integrality framework with budget constraints. Zbl 0908.90213
Hochbaum, Dorit S.
1998
Instant recognition of half integrality and 2-approximations. Zbl 0911.90261
Hochbaum, Dorit S.
1998
The pseudoflow algorithm and the pseudoflow-based simplex for the maximum flow problem. Zbl 0911.90154
Hochbaum, Dorit S.
1998
Scheduling semiconductor burn-in operations to minimize total flowtime. Zbl 0895.90116
Hochbaum, Dorit S.; Landy, Dan
1997
$$k$$-edge subgraph problems. Zbl 0870.68111
Goldschmidt, Olivier; Hochbaum, Dorit S.
1997
An O$$(\log k)$$-approximation algorithm for the $$k$$ minimum spanning tree problem in the plane. Zbl 0866.68076
Garg, N.; Hochbaum, D. S.
1997
Generalized $$p$$-center problems: Complexity results and approximation algorithms. Zbl 0918.90098
Hochbaum, Dorit S.; Pathria, Anu
1997
Scheduling with batching: Two job types. Zbl 0873.90050
Hochbaum, Dorit S.; Landy, Dan
1997
Approximation algorithms for NP-hard problems. Zbl 1368.68010
Hochbaum, Dorit S. (ed.)
1996
Approximation algorithms for the $$k$$-clique covering problem. Zbl 0857.05086
Goldschmidt, Olivier; Hochbaum, Dorit S.; Hurkens, Cor; Yu, Gang
1996
The bottleneck graph partition problem. Zbl 0873.90102
Hochbaum, Dorit S.; Pathria, Anu
1996
On the complexity of the production-transportation problem. Zbl 0845.90087
Hochbaum, Dorit S.; Hong, Sung-Pil
1996
A nonlinear knapsack problem. Zbl 0838.90092
Hochbaum, Dorit S.
1995
About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Zbl 0844.90061
Hochbaum, Dorit S.; Hong, Sung-Pil
1995
A polynomial algorithm for the $$k$$-cut problem for fixed $$k$$. Zbl 0809.90125
Goldschmidt, Olivier; Hochbaum, Dorit S.
1994
Simple and fast algorithms for linear and integer programs with two variables per inequality. Zbl 0831.90089
Hochbaum, Dorit S.; Naor, Joseph
1994
Lower and upper bounds for the allocation problem and other nonlinear optimization problems. Zbl 0820.90082
Hochbaum, Dorit S.
1994
Scheduling with batching: Minimizing the weighted number of tardy jobs. Zbl 0820.90052
Hochbaum, Dorit S.; Landy, Dan
1994
Strongly polynomial algorithms for the quadratic transportation problem with a fixed number of sources. Zbl 0802.90073
Cosares, Steven; Hochbaum, Dorit S.
1994
An $$O(\log k)$$ approximation algorithm for the $$k$$ minimum spanning tree problem in the plane. Zbl 1344.68285
Garg, Naveen; Hochbaum, Dorit S.
1994
Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality. Zbl 0802.90080
Hochbaum, Dorit S.; Megiddo, Nimrod; Naor, Joseph; Tamir, Arie
1993
A modified greedy heuristic for the set covering problem with improved worst case bound. Zbl 0811.68099
Goldschmidt, Olivier; Hochbaum, Dorit S.; Yu, Gang
1993
Why should biconnected components be identified first. Zbl 0789.90084
Hochbaum, Dorit S.
1993
The empirical performance of a polynomial algorithm for constrained nonlinear optimization. Zbl 0786.90066
1993
A polynomial algorithm for an integer quadratic non-separable transportation problem. Zbl 0761.90061
Hochbaum, Dorit S.; Shamir, Ron; Shanthikumar, J. George
1992
The multicovering problem. Zbl 0759.90072
Hall, Nicholas G.; Hochbaum, Dorit S.
1992
Strongly polynomial algorithms for the high multiplicity scheduling problem. Zbl 0736.90043
Hochbaum, Dorit S.; Shamir, Ron
1991
Convex separable optimization is not much harder than linear optimization. Zbl 0721.90060
Hochbaum, Dorit S.; Shanthikumar, J. George
1990
Minimizing the number of tardy job units under release time constraints. Zbl 0707.90049
Hochbaum, Dorit S.; Shamir, Ron
1990
A fast perfect-matching algorithm in random graphs. Zbl 0733.05072
Goldschmidt, Oliver; Hochbaum, Dorit S.
1990
Analysis of a flow problem with fixed charges. Zbl 0673.90035
Hochbaum, Dorit S.; Segev, Arie
1989
An algorithm for the detection and construction of Monge sequences. Zbl 0666.65044
Alon, Noga; Cosares, Steven; Hochbaum, Dorit S.; Shamir, Ron
1989
An $$O(n \log^ 2\,n)$$ algorithm for the maximum weighted tardiness problem. Zbl 0672.68011
Hochbaum, Dorit S.; Shamir, Ron
1989
A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach. Zbl 0647.68040
Hochbaum, Dorit S.; Shmoys, David B.
1988
Fast approximation algorithms for a nonconvex covering problem. Zbl 0636.68082
Hochbaum, Dorit S.; Maass, Wolfgang
1987
A fast approximation algorithm for the multicovering problem. Zbl 0602.90110
Hall, Nicholas G.; Hochbaum, Dorit S.
1986
A better than ”best possible” algorithm to edge color multigraphs. Zbl 0594.68041
Hochbaum, Dorit S.; Nishizeki, Takao; Shmoys, David B.
1986
A polynomial approximation scheme for machine scheduling on uniform processors: Using the dual approximation approach. Zbl 0623.68033
Hochbaum, Dorit S.; Shmoys, David B.
1986
Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem. Zbl 0596.90093
Hochbaum, Dorit S.; Shmoys, David B.
1986
Approximation schemes for covering and packing problems in image processing and VLSI. Zbl 0633.68027
Hochbaum, Dorit S.; Maass, Wolfgang
1985
A best possible heuristic for the k-center problem. Zbl 0565.90015
Hochbaum, Dorit S.; Shmoys, David B.
1985
An $$O(| V| ^ 2)$$ algorithm for the planar 3-cut problem. Zbl 0572.05040
Hochbaum, Dorit S.; Shmoys, David B.
1985
Easy solutions for the K-center problem or the dominating set problem on random graphs. Zbl 0562.68029
Hochbaum, Dorit S.
1985
When are NP-hard location problems easy? Zbl 0671.90019
Hochbaum, Dorit S.
1984
Approximation schemes for covering and packing problems in robotics and VLSI. Zbl 0557.68035
Hochbaum, Dorit S.; Maass, Wolfgang
1984
Efficient bounds for the stable set, vertex cover and set packing problems. Zbl 0523.05055
Hochbaum, Dorit S.
1983
On the fractional solution to the set covering problem. Zbl 0518.90055
Hochbaum, Dorit S.
1983
Approximation algorithms for the set covering and vertex cover problems. Zbl 0486.68067
Hochbaum, Dorit S.
1982
Heuristics for the fixed cost median problem. Zbl 0473.90029
Hochbaum, Dorit S.
1982
Steinhaus’s geometric location problem for random samples in the plane. Zbl 0501.60040
Hochbaum, Dorit; Steele, J. Michael
1982
Database location in computer networks. Zbl 0445.68071
Fisher, Marshall L.; Hochbaum, Dorit S.
1980
Probabilistic analysis of the planar K-median problem. Zbl 0435.90057
Fisher, M. L.; Hochbaum, D. S.
1980
all top 5

#### Cited by 2,325 Authors

 36 Hochbaum, Dorit S. 15 Levin, Asaf 14 Subramani, Krishnan 14 Zhang, Zhao 13 Cheng, Tai-Chiu Edwin 13 Das, Gautam Kumar 13 Paschos, Vangelis Th. 11 Xu, Dachuan 10 Du, Ding-Zhu 10 Wu, Weili 9 Chan, Timothy Moon-Yew 9 Hassin, Refael 9 Jansen, Klaus 9 Kovalyov, Mikhail Yakovlevich 9 Nandy, Subhas Chandra 9 Pardalos, Panos M. 9 Shioura, Akiyoshi 9 Strusevich, Vitaly A. 9 Woeginger, Gerhard Johannes 8 Chen, Jian-er 8 Shakhlevich, Natalia V. 8 Tamir, Arie 8 Trystram, Denis R. 8 Xu, Chao 7 Brauner, Nadia 7 Epstein, Leah 7 Guan, Xiucui 7 Ibaraki, Toshihide 7 Rawitz, Dror 7 Ray, Saurabh 7 Sun, Xiaoling 7 Wang, Jianxin 7 Wu, Chenchen 6 Crama, Yves 6 Du, Donglei 6 Escoffier, Bruno 6 Fujito, Toshihiro 6 Hermelin, Danny 6 Huang, Wenqi 6 Jallu, Ramesh K. 6 Kakimura, Naonori 6 Kellerer, Johann 6 Krumke, Sven Oliver 6 Li, Duan 6 Marathe, Madhav V. 6 Murota, Kazuo 6 Mustafa, Nabil Hassan 6 Razzazi, Mohammadreza 6 Rudolf, Rudiger 6 Segev, Danny 6 Shachnai, Hadas 6 Steiner, George 6 Tu, Jianhua 6 Vohra, Rakesh V. 6 Wang, Lusheng 6 Zhang, Jianzhong 6 Zhang, Jiawei 5 Atamtürk, Alper 5 Burkard, Rainer E. 5 Chambolle, Antonin 5 Chekuri, Chandra S. 5 Demange, Marc 5 El Ouali, Mourad 5 Fellows, Michael Ralph 5 Fiorini, Samuel 5 Goldreich, Oded 5 Grigoriev, Alexander 5 Ito, Takehiro 5 Klasing, Ralf 5 Kortsarz, Guy 5 Leung, Joseph Y.-T. 5 Li, Guojun 5 Lingas, Andrzej 5 Mastrolilli, Monaldo 5 Milis, Ioannis 5 Monnot, Jérôme 5 Ng, Chi To 5 Parekh, Ojas 5 Peleg, David 5 Shamir, Ron 5 Shetty, Bala 5 Srivastav, Anand 5 Sung, Chang Sup 5 Teo, Chungpiaw 5 Wang, Wei 5 Xiao, Mingyu 5 Yagiura, Mutsunori 5 Yuan, Jinjiang 5 Zissimopoulos, Vassilis 4 Agnetis, Alessandro 4 Bar-Yehuda, Reuven 4 Basappa, Manjanna 4 Bertsimas, Dimitris John 4 Bretthauer, Kurt M. 4 Bus, Norbert 4 Carmi, Paz 4 Chen, Zhizhong 4 Damaschke, Peter 4 Darbon, Jerome 4 Detti, Paolo ...and 2,225 more Authors
all top 5

#### Cited in 176 Serials

 123 European Journal of Operational Research 121 Theoretical Computer Science 88 Discrete Applied Mathematics 75 Algorithmica 57 Information Processing Letters 54 Journal of Combinatorial Optimization 47 Mathematical Programming. Series A. Series B 46 Computers & Operations Research 44 Operations Research Letters 36 Discrete Optimization 34 Annals of Operations Research 32 Journal of Scheduling 28 Journal of Computer and System Sciences 23 Computational Geometry 19 International Journal of Foundations of Computer Science 18 Networks 18 Journal of Global Optimization 17 Theory of Computing Systems 14 Journal of Discrete Algorithms 12 Discrete Mathematics 12 Mathematics of Operations Research 12 Optimization Letters 11 International Journal of Computational Geometry & Applications 10 SIAM Journal on Computing 10 RAIRO. Operations Research 9 Operations Research 8 Discrete & Computational Geometry 8 SIAM Journal on Optimization 7 International Journal of Production Research 7 Computational Optimization and Applications 7 Top 7 INFORMS Journal on Computing 6 Information Sciences 6 Naval Research Logistics 6 SIAM Journal on Discrete Mathematics 5 Artificial Intelligence 5 Applied Mathematics and Computation 5 Optimization 5 Games and Economic Behavior 5 Linear Algebra and its Applications 5 Journal of Heuristics 5 OR Spectrum 5 SIAM Journal on Imaging Sciences 5 Discrete Mathematics, Algorithms and Applications 4 Journal of Optimization Theory and Applications 4 Information and Computation 4 Journal of Parallel and Distributed Computing 4 Applied Mathematical Modelling 4 4OR 4 Journal of Industrial and Management Optimization 4 Computer Science Review 3 BIT 3 Computing 3 Journal of Combinatorial Theory. Series B 3 Journal of Computational and Applied Mathematics 3 Advances in Applied Mathematics 3 Combinatorica 3 Journal of Computer Science and Technology 3 Asia-Pacific Journal of Operational Research 3 Formal Aspects of Computing 3 Random Structures & Algorithms 3 International Journal of Computer Mathematics 3 Distributed Computing 3 International Journal of Computer Vision 3 Optimization Methods & Software 3 Mathematical Methods of Operations Research 3 Data Mining and Knowledge Discovery 3 Mathematical Programming Computation 3 Journal of the Operations Research Society of China 2 Acta Informatica 2 Journal of Mathematical Physics 2 Chaos, Solitons and Fractals 2 Mathematica Slovaca 2 Statistica Neerlandica 2 European Journal of Combinatorics 2 OR Spektrum 2 SIAM Journal on Algebraic and Discrete Methods 2 Acta Mathematicae Applicatae Sinica. English Series 2 Graphs and Combinatorics 2 Mathematical and Computer Modelling 2 Queueing Systems 2 Real-Time Systems 2 The Annals of Applied Probability 2 Discrete Event Dynamic Systems 2 Computational Statistics and Data Analysis 2 Applied Mathematics. Series B (English Edition) 2 Combinatorics, Probability and Computing 2 Annals of Mathematics and Artificial Intelligence 2 Wuhan University Journal of Natural Sciences (WUJNS) 2 International Journal of Applied Mathematics and Computer Science 2 RAIRO. Theoretical Informatics and Applications 2 Trudy Instituta Matematiki 2 Sādhanā 2 JMMA. Journal of Mathematical Modelling and Algorithms 2 Acta Numerica 2 Computational Management Science 2 The Annals of Applied Statistics 2 Algorithms 1 Applicable Analysis 1 Computers & Mathematics with Applications ...and 76 more Serials
all top 5

#### Cited in 27 Fields

 878 Operations research, mathematical programming (90-XX) 652 Computer science (68-XX) 326 Combinatorics (05-XX) 60 Numerical analysis (65-XX) 58 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 31 Statistics (62-XX) 29 Convex and discrete geometry (52-XX) 14 Biology and other natural sciences (92-XX) 13 Calculus of variations and optimal control; optimization (49-XX) 13 Probability theory and stochastic processes (60-XX) 13 Information and communication theory, circuits (94-XX) 7 Systems theory; control (93-XX) 6 Linear and multilinear algebra; matrix theory (15-XX) 6 Partial differential equations (35-XX) 5 General and overarching topics; collections (00-XX) 4 Mathematical logic and foundations (03-XX) 4 Statistical mechanics, structure of matter (82-XX) 3 Number theory (11-XX) 2 Order, lattices, ordered algebraic structures (06-XX) 2 Differential geometry (53-XX) 2 General topology (54-XX) 2 Geophysics (86-XX) 1 Algebraic geometry (14-XX) 1 Functional analysis (46-XX) 1 Operator theory (47-XX) 1 Manifolds and cell complexes (57-XX) 1 Mechanics of particles and systems (70-XX)

#### Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.