Dorit S. Hochbaum and Asaf Levin. Weighted matching with pair restrictions. To appear, *Optimization Letters*, 2017.
Preprint.

Dorit S. Hochbaum and Cheng Lu.
A faster algorithm solving a generalization of isotonic median regression and a class of fused lasso problems.
To appear, *SIAM J. Optimization*, 2017.

P. Baumann, D. S. Hochbaum and Q. Spaen.
High-Performance Geometric Algorithms for
Sparse Computation in Big Data Analytics. To appear,
* 2017 IEEE International Conference on Big Data.* Washington DC, Dec 2017.

Dorit S. Hochbaum. Submodular problems - approximations and algorithms. arXiv:1010.1945v2, Apr 2017.

Quico Spaen, Dorit S. Hochbaum, Roberto Asin. HNCcorr: A Novel Combinatorial Approach for Cell Identification in Calcium-Imaging Movies. arXiv:1703.01999 [q-bio.QM] March 2017.

D. S. Hochbaum. A Min cost flow on unit capacity networks and convex cost K-flow are as easy as the assignment problem with All-Min-Cuts algorithm. arXiv:1610.04012 [cs.DS], Oct 2016.

D.S. Hochbaum and P. Baumann.
Sparse Computation for Large-Scale Data Mining.
*IEEE Transactions on Big Data*, Vol 2, Issue 2, 151-174, 2016.

Dorit S. Hochbaum. A polynomial time repeated cuts algorithm for the time cost tradeoff problem: The linear and convex crashing cost deadline problem.
*Computers & Industrial Engineering*, Vol. 95, Pages 64-71, May 2016.

P. Baumann, D. S. Hochbaum and Q. Spaen. Sparse-Reduced Computation: Enabling Mining of Massively-Large Data Sets.
In M. De Marsico,G. Sanniti di Baja, and A. Fred, eds., *Proceedings of the 5th International Conference on Pattern Recognition Applications and Methods*, 224-231, Rome, 2016.

P. Baumann, R.J. Cooper, D.S. Hochbaum, N. Patel and
K. Shalia. Efficient deployment of mobile detectors for security
applications.
In: * Proceedings of the 2015 IEEE International Conference
on Industrial Engineering and Engineering Management*. Singapore,
2015.

Dorit S. Hochbaum and Michael Wagner.
Range Contracts: Risk Sharing and Beyond.
* European Journal of Operational Research*, Vol. 243(3), 16 June 2015, pp. 956-963.

Dorit S. Hochbaum and Michael Wagner. Production Cost Functions and Demand Uncertainty Effects in Price-Only Contracts.
* IIE Transactions*, (2015) Vol. 47, 190-202.
Appeared online Nov 2014.

D.S. Hochbaum and P. Baumann.
Sparse computation for large-scale data mining.
In: * 2014 IEEE International Conference on Big Data.* Washington DC, Oct, 2014, pp. 354-363.

Dorit S. Hochbaum, Cheng Lyu, Fernando Ordonez.
Security Routing Games with Multi-vehicle Chinese Postman Problem.
Vol. 64 Issue 3, 181-191, * Networks*, Oct 2014.

Yan Yang, Barak Fishbain, Dorit S. Hochbaum, Eric Norman, Erik Swanberg.
The Supervised Normalized Cut Method for Detecting, Classifying and Identifying Special Nuclear Materials.
* INFORMS J Computing*, Vol .26 Issue 1, Winter 2014, pp. 45-58.

Barak Fishbain, Dorit Hochbaum and Stefan Mueller.
A Competitive Study of the Pseudoflow algorithm for the Minimum s-t Cut
problem in Vision applications. * Journal of Real-Time Image Processing*, March 2016, Vol. 11, Issue 3, pp 589-609. (Online April 2013.) DOI 10.1007/s11554-013-0344-3.

Barak Fishbain, Dorit Hochbaum, and Yan Yang. A new approach for real-time target tracking in videos. * SPIE Newsroom*, DOI: 10.1117/2.1201301.004648, Jan 2013.
http://spie.org/x92064.xml

Dorit S. Hochbaum, Cheng Lu, Erik Bertelli. "Evaluating Performance of Image Segmentation Criteria and Techniques". * EURO Journal on Computational Optimization*, Vol 1:1-2, May 2013, pp. 155-180.

Dorit S. Hochbaum and Asaf Levin.
A minimization variant of the order preserving submatrices problem".
* ACM Transactions on Algorithms*, 9 (2): 1-12, 2013

Dorit S. Hochbaum.
Multi-label Markov Random Fields as an Efficient and Effective Tool for Image Segmentation, Total Variations and Regularization.
* Numerical Mathematics: Theory, Methods and Applications*,
Vol. 6, No. 1, pp. 169--198 Feb 2013,
doi: 10.4208/nmtma.2013.mssvm09

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 *, Vol. 61, No. 1, January-February 2013, pp. 184-198.

Dorit S. Hochbaum and James B. Orlin. Simplifications and speedups of the Pseudoflow algorithm. *Networks* Volume 61, Issue 1, pp. 40-57, January 2013.

Dorit S. Hochbaum, Chun-Nan Hsu, Yan T. Yang. Ranking of Multidimensional Drug Profiling Data by Fractional Adjusted Bi-Partitional Scores.
*Bioinformatics* (2012) 28 (12): 106-114.

Marjan Baghaie, D.S. Hochbaum, B. Krishnamachari.
On Hardness of Multiflow Transmission in Delay Constrained Cooperative Wireless Networks. *IEEE GLOBECOM* 2011 54th annual conference. Houston, Texas, Dec 2011.

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

Dorit S. Hochbaum.
An efficient and effective tool for image segmentation, total variations and regularization.
In Third International Conference on
*Scale Space and Variational Methods in Computer Vision (SSVM 2011)*
A.M. Bruckstein et al. (Eds.): SSVM 2011, LNCS 6667, pp. 338--349. Springer, Heidelberg (2011)

Bala G. Chandran and Dorit S. Hochbaum. Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm. arXiv:1105.1569v1 May 2011.

Dorit S. Hochbaum Erick Moreno-Centeno, Phillip Yelland and Rodolfo A. Catena.
Rating customers according to their promptness to adopt new products. * Operations Research*, 2011;59 1171-1183
Journal online

Ilan Adler and Dorit S. Hochbaum. Benchmark Problems for Totally Unimodular Set System Auction. arXiv:1102.3499 Feb 2011.

Dorit S. Hochbaum.
The separation, and separation-deviation methodology for group decision making and aggregate ranking. J. J. Hasenbein, ed.
* TutORials in Operations Research*, Vol. 7. INFORMS, Hanover, MD, pp. 116-141, 2010.

Dynamic stand-off 3d gamma-ray imaging. (With Mihailescu, L., B. Fishbain, J. Maltz, C.J. Moore, J. Rohel,
L. Supic, K. Vetter.)
In * 12th Symposium on Radiation Measurements and Applications (SORMA)*
106, 2010.

Barak Fishbain, Dorit S. Hochbaum, Stefan Mueller. Competitive Analysis of Minimum-Cut Maximum Flow Algorithms in Vision Problems. arXiv:1007.4531 Oct 2010.

Dorit S. Hochbaum. Replacing spectral techniques for expander ratio and normalized cut by combinatorial flow algorithms. arXiv:1010.4535v1 [math.OC]

Dorit S. Hochbaum and Barak Fishbain.
Nuclear Threat Detection with Mobile Distributed Sensor Networks.
* Annals of Operations Research* 187:1, 45-63, 2011.
online version

Dorit S. Hochbaum and Asaf Levin.
Covering the edges of bipartite graphs using K_{2,2} graphs
* Theoretical Computer Science *, 411, 1-9, 2010

Dorit S. Hochbaum and Asaf Levin.
How to allocate review tasks for robust ranking.
*Acta Informatica* Volume 47, Issue 5 (2010), Page 325-345.
online version

Tingting Cui and Dorit S. Hochbaum.
Complexity of Some Inverse Shortest Path Lengths Problems.
*Networks* Volume 56, Issue 1, August 2010, Pages: 20-29.

Dorit S. Hochbaum and Vikas Singh.
An efficient algorithm for co-segmentation.
*ICCV Oct 2009 *, Kyoto, Japan, the 12th IEEE Conference on Computer Vision.

Dorit S. Hochbaum.
Polynomial time algorithms for ratio regions and a variant of normalized cut.
*IEEE Transactions on Pattern Analysis and Machine
Intelligence*, 32 (5), 889-898, May 2010.

Dorit S. Hochbaum.
An Efficient and Effective Image Segmentation Interactive Tool. *Proceedings of BIOSIGNALS* 2009.
2nd International conference on bio-inspired systems and signal processing.
Porto Portugal, 459-461. INSTICC Press.

Dorit S. Hochbaum.
The multi-sensor nuclear threat detection problem.
In * Operations Research and Cyber-Infrastructure*, *Proceedings of the Eleventh INFORMS Computing Society (ICS) Conference
* J. Chinneck, B. Kristjansson and M. Saltzman eds.
OR/CS Interfaces, pp. 389-399, Springer, 2009.

Dorit S. Hochbaum and Erick Moreno-Centeno.
Country credit-risk rating aggregation via the separation-deviation model
* Optimization Methods and Software.
* 23:5, 741-762, (Oct) 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. arXiv:0803.0146v1

Bala Chandran and Dorit S. Hochbaum.
A Computational Study of the Pseudoflow and Push-relabel Algorithms for the
Maximum Flow Problem. * Operations Research * Vol. 57, No. 2, March-April 2009, pp. 358-376.

Dorit S. Hochbaum and Asaf Levin.
The multi-integer set cover and the facility terminal cover problem
* Networks*, 53:1, pp. 63 - 66, 2008.
online version

Dorit S. Hochbaum and Asaf Levin. Covering the edges of bipartite graphs using K_{2,2} graphs In , C. Kaklamanis and M. Skutella (Eds.): WAOA 2007, LNCS 4927, pp. 116-127, 2008. Springer-Verlag Berlin Heidelberg 2008.

Dorit S. Hochbaum.
"The Inequality-Satisfiability problem." (with Erick Moreno).
*Operations Research Letters* 36 (2008) 229-233.
Available from journal, here

Dorit S. Hochbaum.
"Dynamic evolution of economically preferred facilities."
*European J. of Operational Research.* 193 (2009) 649-659.

Dorit S. Hochbaum.
"Ranking sports teams and the inverse equal paths problem."
*Proceedings 2nd international Workshop on Internet & Network Economics*
WINE06 Dec 2006. LNCS4286, pp 307-318

Dorit S. Hochbaum.
"Complexity and algorithms for nonlinear optimization problems."
*Annals of Operations Research* 153, 257-296. 2007

Dorit S. Hochbaum.
"The Pseudoflow algorithm: A new algorithm for the maximum flow
problem" * Operations Research *, Vol 58(4) 992-1009, July-Aug (2008).

Dorit S. Hochbaum and Asaf Levin.
"Cyclical scheduling and multi-shift
scheduling: complexity and approximation algorithms"
*Discrete optimization *, Volume 3, Issue 4 , 1 December 2006, Pages 327-340

Ravi Ahuja and Dorit S. Hochbaum.
"Solving Linear Cost Dynamic Lot Sizing Problems in O(n log n) Time" * Operations Research *, 56:1 Jan-Feb 2008, 255-261.

Dorit S. Hochbaum and Asaf Levin.
"Methodologies for the group rankings decision" *Management Science *,
Vol. 52, No. 9, September 2006, pp. 1394-1408.

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

Dorit S. Hochbaum and Asaf Levin.
"Optimizing over consecutive 1's and circular 1's constraints" (With Asaf Levin.).
*SIAM J on Optimization *, Vol. 17, No. 2, pp. 311--330, 2006.

Dorit S. Hochbaum.
"Selection, Provisioning, Shared Fixed Costs,
Maximum Closure, and Implications on Algorithmic Methods Today"
*Management Science* Vol 50:6, pp 709-723, 2004.

"Due Date Quotation Models and Algorithms". (with P. Kaminsky)
*Handbook on Scheduling Algorithms, Methods, and Models*, Joseph Y. Leung
(ed.), Chapman Hall/CRC Press 2004. pp 20-1 -- 20-22.

Dorit S. Hochbaum.
"Monotonizing linear programs with up to two nonzeroes per column".
*Operations Research Letters*,
2004, 32:1 pp 49-58.

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

Dorit S. Hochbaum.
"Efficient algorithms for the inverse spanning tree problem".
*Operations Research*,
September-October 2003, 51,:5, 785-797.

Ravi K. Ahuja, Dorit S. Hochbaum and James B. Orlin.
"Solving the convex cost integer dual of minimum cost network flow problem".
*Management Science*, 49:7, (2003) 950-964.

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

Dorit S. Hochbaum and Paul A. Tucker.
"Minimax problems with bitonic matrices"
*Networks*. Vol 40, No 3, 2002 pp. 113-124.

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, 2002, pp. 291-321.

Dorit S. Hochbaum.
"An efficient algorithm for image segmentation, Markov Random Fields and related problems".
*Journal of the ACM*. Vol 48, No 2, July 2001 pp. 686 - 701.

Book: Young Hae Lee, Mitsuo Gen and Dorit S. Hochbaum (eds.) "A focused issue on Supply Chain Management", Computers and Industrial Engineering Volume 43, Issue 1-2, Elsevier, (2002).

Alper Atamturk and Dorit S. Hochbaum.
"Capacity acquisition, subcontracting, and lot sizing". *Management Science*, Vol 47, No 8 August 2001 pp. 1-20.

Dorit S. Hochbaum.
"A new-old algorithm for minimum cut in closure graphs," *Networks,* Special 30th anniversary paper, Vol 37, No 4, 2001 171-193.

Dorit S. Hochbaum. "Instant recognition of polynomial time solvability, half integrality and 2-approximations." Lecture Notes in Computer Science 1913, K.~Jansen and S.~Khuller (eds.). APPROX2000 proceedings pp 2-14, Sep 2000.

Dorit S. Hochbaum. "Instant recognition of polynomial time solvability, half integrality and 2-approximations." EURO 17, Budapest 2000, pp 31-33.

Dorit S. Hochbaum and Anna Chen.
"Improved Planning for the Open - Pit Mining Problem,"
*Operations Research*, 48:6, Nov -Dec 2000, 894-914,

Dorit S. Hochbaum and Maurice Queyranne.
"Minimizing a convex cost closure set".
*Siam Journal on Discrete Mathematics*
16:2, 2003, pp 192-207.
Extended abstract appeared in *Lecture Notes in Computer Science* 1879, M.
Paterson (ed.), 8th Annual European Symposium on Algorithms - ESA 2000
proceedings pp 256-267.

Dorit S. Hochbaum and Eli Olinick.
"The Bounded Cycle Cover Problem"
*Informs Journal on Computing*, 13:2 spring 2001 104-119.

Ilan Adler, Alan Erera, Dorit S. Hochbaum and Eli Olinick.
"Baseball, Optimization and the World Wide Web".
*Interfaces* 32:2 March-April 2002, pp. 12-22.

Book: Dorit S. Hochbaum, Klaus Jansen, Jose Rolim and Alistair Sinclair
(eds.) "Randomization, Approximation and Combinatorial Optimization:
Algorithms and Technique" *Lecture Notes in Computer Science* 1671,
1999.

"Approximating a Generalization of MAX 2SAT and MIN 2SAT".
(with A. Pathria).
*Discrete Applied Mathematics*, 107 (1-3) (2000) pp. 41-59.

"A half-integral linear programming relaxation for scheduling
precedence-constrained jobs on a single machine" (with Fabian
Chudak),
*Operations Research Letters*, 25, (1999), 199-204.

"Solving a convex dual of minimum cost flow" (with Ravindra K. Ahuja and James B. Orlin). June 1999, Lecture Notes in Computer Science 1610, Cornuejols, Burkard and Woeginger (eds.). IPCO99 proceedings pp 31-44.

Dorit S. Hochbaum and Gerhard J. Woeginger.
"An optimal algorithm for the Bottleneck transportation problem
with a fixed number of sources".
*Operations Research Letters*, 24, (1999), 25-28.

Dorit S. Hochbaum.
"Approximating clique and biclique Problems".
*Journal of Algorithms* 29, 1998, 174-200.

Dorit S. Hochbaum.
"The pseudoflow algorithm and the pseudoflow-based simplex for the
maximum flow problem"
*Procdeedings of Integer Programming and Combinatorial Optimization* 6th
International IPCO conference, Houston Texas, June 1998, 325-337.

Dorit S. Hochbaum.
Instant recognition of half integrality and 2-approximation. "
*Procdeedings of APPROX98* Aalborg Denmark, July 1998.

Dorit S. Hochbaum.
"The t- vertex cover problem: Extending the half integrality
framework with budget constraints."
*Procdeedings of APPROX98* Aalborg Denmark, July 1998.

F. Chudak, M. Goemans, Dorit S. Hochbaum and D. Williamson.
"A primal-dual interpretation of recent 2-approximation algorithms for
the feedback vertex set in undirected graphs".
*Operations Research Letters*
22, 111-118, (1998).

Dorit S. Hochbaum and Anu Pathria.
"Analysis of the Greedy Approach in Covering Problems,"
*Naval Research Quarterly* 45 (1998) 615-627.

Dorit S. Hochbaum and Anu Pathria.
"Locating centers in dynamically changing network and related
problems"
*Location Science*, 6 (1998) 243-256.

Dorit S. Hochbaum and Anu Pathria.
"Path Costs in Evolutionary Tree Reconstruction"
*Journal of computational biology* 4(2), 1997, 163-175.

Dorit S. Hochbaum and Anu Pathria.
"Generalized p-Center Problems: Complexity Results and
Approximation Algorithms,"
*European Journal of Operational Research* 100:3 1997, 594-607.

Dorit S. Hochbaum and Anu Pathria.
"Forest Harvesting and Minimum Cuts,"
*Forest Science*, 43:4, Nov 1997, 544-554.

Dorit S. Hochbaum and Anu Pathria.
"The bottleneck Graph Partition Problem,"
*Networks* 28:4, Dec 1996, 221-225.

Dorit S. Hochbaum.
"An Optimal Test Compression Procedure for
Combinational circuits", *IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems*,
15:10, 1294-1299.

Olivier Goldschmidt and Dorit S. Hochbaum.
"k-edge Subgraph Problems," (with O. Goldschmidt).
*Discrete Applied Math* Vol. 74, No. 2, pp. 159-169 (1997).

Olivier Goldschmidt, Dorit S. Hochbaum, C. Hurken and Gang Yu.
"Approximation algorithms for the k-Clique Covering Problem".
*SIAM J. of Discrete Math*, Vol 9:3, 492-509, August (1996).

Jeniffer Adams and Dorit S. Hochbaum.
"A new and fast approach to very large scale integrated sequential
circuits test generation,",
*Operations Research* 45:6, 842-856, (1997).

"Approximation Algorithms for Network Design Problems
on Bounded Subsets," (with Seffi Naor).
*J. of Algorithms*, 21, 403-414 (1996).

Dorit S. Hochbaum and Dan Landy.
"Algorithms and Heuristics for Scheduling
Semiconductor Burn-in Operations,"
*Operations Research* 45:6, 874-885, (1997).

Dorit S. Hochbaum and Dan Landy.
"Scheduling with Batching: Two Job Types".
*Discrete Applied Math*, 72, 99-114,
(1997).

Dorit S. Hochbaum.
"A Nonlinear Knapsack Problem,",
*Operations Research Letters* 17 (1995) 103-110.

"About Strongly Polynomial Time Algorithms for Quadratic
Optimization Over Submodular Constraints,", (with S.P. Hong).
*Mathematical Programming* 69, (1995) 269-309.

"On the Complexity of the Production-Transportation Problem, (with
S.P. Hong). *SIAM J. on optimization*, Vol 6, No 1, 250-264, (1996).

"Scheduling with Batching:
Minimizing the Weighted Number of Tardy Jobs," (with D. Landy),
*Operations Research Letters*, 16 (1994) 79-86.

"An O(log k) approximation algorithm for the k-minimum spanning
tree problem in the plane," (with N. Garg).
Proceedings of the 26th Annual ACM
Symposium on the Theory of Computing (STOC) (1994) 432-438.
*Algorithmica* 18(1):111-121, 1997.

"A Modified Greedy Heuristic for the Set Covering Problem with
Improved Worst Case Bound" (with O. Goldschmidt, and G. Yu),
*Information Processing Letters* 48 (1993) 305-310.

"Complexity and Algorithms for Logical Constraints with Applications to VLSI Layout, Compaction and Clocking". Studies in Locational Analysis, ISOLDE VI proceedings, 159-164 June (1993).

Tight Bounds and 2-approximation Algorithms for Integer Programs
with Two Variables Per Inequality.
(with N. Megiddo, J. Naor and A. Tamir), *Mathematical Programming*, 62 (1993) 69-83.

"Polynomial Algorithms for Convex Network Optimization," in
*Network Optimization Problems: Algorithms, Complexity
and Applications*, edited by D. Du and P. M. Pardalos, World
Scientific, 63-92, (1993).

"Lower and Upper Bounds for the Allocation Problem and Other
Nonlinear Optimization Problems,"
*Mathematics of Operations
Research*, Vol. 19, No 2, 390-409, May (1994).
"Errata"

"A Polynomial Algorithm for the K-Cut Problem" (with 0.
Goldschmidt), *Mathematics of Operations
Research* Vol 19. No. 1 Feb (1994) 24-37.

"The Empirical Performance of a Polynomial Algorithm for
Constrained Nonlinear Optimization" (with S. Seshadri),
*Annals of Operations
Research*, Vol. 43 (eds. G. Mitra and I. Maros), 229-248, (1993).

"Simple and Fast Algorithms for Linear and Integer Programs
with Two Variables per Inequality," (with J. Naor)
*SIAM Journal on Computing* vol 23 No. 6, (1994), 1179-1192.
(earlier version in *Proceedings of
IPCO*, Second Integer Programming and Combinatorial Optimization
Conference, Carnegie Mellon University, May 1992, 41-60.)

"A Strongly Polynomial Algorithm for the Quadratic Transportation
Problem with Fixed Number of Suppliers" (with S. Cosares),
*Mathematics of Operations Research* Vol
19. No. 1 Feb (1994) 94-111.

"An Exact Sublinear Algorithm for the Max-Flow, Vertex Disjoint
Paths and Communication Problems on Random Graphs,"
*Operations Research*, Vol. 40, No. 5, pp. 923-935, (1992).

"Why Should Biconnected Components Be Identified First,"
*Discrete Applied Mathematics*, 42, (1993), 203-210.

"The Multicovering Problem" (with N. Hall),
*European Journal on Operational Research*, 62, (1992) 323-339.

"A Polynomial Algorithm for an Integer Quadratic Nonseparable
Transportation Problem" (with J. G. Shanthikumar and R. Shamir),
*Mathematical Programming*, Vol. 55, No. 3, pp. 359-372, (1992).

"On the Impossibility of Strongly Polynomial Algorithms for the Allocation Problem and its Extensions," Proceedings of the Integer Programming and Combinatorial Optimization Conference, May 1990, 261- 274.

"Strongly Polynomial Algorithms for the High Multiplicity
Scheduling Problems" (with R. Shamir), *Operations Research*, Vol.
39, No. 4, (1991), 648-653.

"Nonlinear Separable Optimization is Not Much Harder than Linear
Optimization" (with J.G. Shanthikumar), *Journal of ACM*, Vol. 37,
No. 4 (1990), 843-862.

"The Complexity of Nonlinear Optimization" (with J. G. Shanthikumar), Lecture Notes in Computer Science, 372, Springer-Verlag, July 1989, pp. 461-472.

"Asymptotically Optimal Linear Algorithms for the Minimum K-Cut in
a Random Graph" (with O. Goldschmidt), *SIAM J. on Discrete
Mathematics*, February 1990, Vol. 3, No. 1, pp. 58-73.

"A Fast Perfect Matching Algorithm in Random Graphs" (with O.
Goldschmidt), *SIAM J. on Discrete Mathematics*, February 1990,
Vol. 3, No. 1, pp. 48-57.

Minimizing the Number of Tardy Job Limits under Release Time
Contraints.
(with R. Shamir), *Discrete Applied Mathematics*, Vol.
28 (1990), 45-57.

"O(nlog^2 n) Algorithm for the Maximum Weighted Tardiness Problem"
(with R. Shamir), *Information Processing Letters*, 31 (1989),
215-219.

"An Algorithm for the Detection and Construction of Monge
Sequences" (with A. Alon, S. Cosares and R. Shamir), *Linear Algebra
and its Applications*, 114/115 (1989), 669-680.

"A Polynomial Algorithm for the K-cut Problem" (with O.
Goldschmidt), *Proceedings of 29th Annual Symposium on Foundations of
Computer Science* (October 1988), pp. 444-451.

"A Best Possible Parallel Approximation Algorithm to a Graph
Theoretic Problem" (with D. Shmoys), *Operational Research*
(1987), 933- 938.

"Analysis of a Flow Problem with Fixed Charges" (with A. Segev),
*Networks*, Vol. 19 (1989), 291-312.

"A Polynomial Approximation Scheme for Machine Scheduling on
Uniform Processors: Using the Dual Approximation Approach" (with D.
Shmoys), *SIAM J. on Computing*, 17:3 (1988), 539-551.

"The Concept of Best Possibility on the Analysis of Approximation Algorithms," Proceedings of the Israel Mathematical Union Conference, Tel-Aviv University, Israel (1987), 36-42.

"Fast Approximation Algorithms for a Non-Convex Covering Problem"
(with W. Maass), *Journal of Algorithms*, 8 (1987), 305-323.

"Lagrangian Relaxation for Testing Infeasibility in VLSI Routing"
(with T. Feo), *Operations Research*, 34:6 (1986).

"A Fast Approximation Algorithm for the Multicovering Problem"
(with N. Hall), *Discrete Applied Mathematics*, 15 (1986), 35-40.

"A Packing Problem You Can Almost Solve by Sitting on Your
Suitcase" (with D. Shmoys), *SIAM Journal on Algebraic and Discrete
Methods*, 7:2 (April 1986), 247-257.

"Using Dual Approximation Algorithms for Scheduling Problems:
Practical and Theoretical Results" (with D. Shmoys), *Journal of
ACM*, 34:1 (January 1987), 144-162.

"The Linzertorte Problem - Or a Unified Approach to Painting,
Baking and Weaving" (with E. Wigderson), *Discrete Applied
Mathematics*, 14 (1986), 17-32.

"A Unified Approach to Approximation Algorithms for Bottleneck
Problems" (with D. Shmoys), *Journal of ACM*, 33:3 (July 1986),
533-550.

"An O(V2) Algorithm for the Planar 3-Cut Problem" (with D.
Shmoys), *SIAM Journal on Algebraic and Discrete Methods*, 6:4 (1985),
707-712.

"A Better than 'Best Possible' Algorithm to Edge Color
Multigraphs" (with D. Shmoys and T. Nishizeki), *Journal of Algorithms*,
7:1 (March 1986), 79-104.

"A Best Possible Heuristic for the K-Center Problem" (with D.
Shmoys), *Mathematics of Operations Research*, 10:2 (May 1985), 180-184.

"Approximation Schemes for Covering and Packing Problems in Image
Processing and VLSI" (with W. Maass), *Journal of ACM*, 32:1 (January
1985), 130-136.

"Best Possible Heuristics for the Bottleneck Wandering Salesperson
and Bottleneck Vehicle Routing Problems" (with D. Shmoys), *European
Journal of Operational Research*, 26 (1986), 380-384.

"Easy Solutions for the K-Center Problem or the Dominating Set Problem on Random Graphs," Annals of Discrete Mathematics, 25 (1985), 189-210.

"Approximation Schemes for Covering and Packing Problems in Robotics and VLSI" (with W. Maass), Springer-Verlag Lecture Notes in Computer Science, 166 (April 1984).

"Powers of Graphs: A Powerful Approximation Algorithm Technique" (with D. Shmoys), Proceedings of the Symposium on Theory of Computing, May 1984.

"When are NP-hard Location Problems Easy," Annals of Operations Research, 1 (1984), 201-214.

D.S. Hochbaum.
"Efficient Bounds for the Stable Set, Vertex Cover and Set Packing
Problems,"
* Discrete Applied Mathematics*, 6 (1983), 243-254.

D.S. Hochbaum.
"On the Fractional Solution to the Set Covering Problem," * SIAM
Journal of Algebraic and Discrete Methods*, 4:2 (1983), 221-222.

D.S. Hochbaum.
"Approximation Algorithms for the Weighted Set Covering and Node
Cover Problems," GSIA Working Paper No. 64-79-80, April 1980; also,
*SIAM Journal of Computing *, 11:3 (1982), 555-556.

D.S. Hochbaum.
"Steinhaus' Geometric Location Problem for Random Samples in the
Plane" (with J. Michael Steele), *Advanced Applied Probability*, 14
(1982), 56-67.

D.S. Hochbaum.
"Heuristics for the Fixed Cost Median Problem," *Mathematical
Programming*, 22:2 (1982), 148-162.

D.S. Hochbaum.
"Database Location in Computer Networks" (with M.L. Fisher),
*Journal of the Association for the Computing Machinery*, 27:4 (October
1980).

D.S. Hochbaum.
"Probabilistic Analysis of the Euclidean K-Median Problem" (with
M.L. Fisher), *Mathematics of Operations Research*, 5:1 (February 1980).

"A Quantitative Analysis of Astigmatism Induced by Pterygium"
(with S. Moskowitz and J. Wirtschafter), *Journal of Biomechanics*, 10
(1977), 735-46.