# Geometric Algorithms For The Minimum Cost Assignment Problem

*Back to Hochbaum main page*

Dorit S. Hochbaum and Sheng Liu. Adjacency-Clustering and its Application for Yield Prediction in Integrated Circuit Manufacturing. *Operations Research*, to appear 2018.

Dorit S. Hochbaum and Asaf Levin. Weighted matching with pair restrictions. *Optimization Letters*, (), 1-11, 2017. Online Nov 22, 2017.

Dorit S. Hochbaum and Cheng Lu. A faster algorithm solving a generalization of isotonic median regression and a class of fused lasso problems. *SIAM J. Optimization*, 27(4), 2563-2596, 2017.

P. Baumann, D. S. Hochbaum and Q. Spaen. High-Performance Geometric Algorithms for Sparse Computation in Big Data Analytics. * 2017 IEEE International Conference on Big Data.* Boston Ma, 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.

**A****L**ist of **T**echnical **R**eports

*Back to Hochbaum main page*

## Title: On the Minimum Cost Range Assignment Problem

Authors:Paz Carmi, Lilach Chaitman-Yerushalmi

(Submitted on 16 Feb 2015)

Abstract: We study the problem of assigning transmission ranges to radio stations placed arbitrarily in a $d$-dimensional ($d$-D) Euclidean space in order to achieve a strongly connected communication network with minimum total power consumption. The power required for transmitting in range $r$ is proportional to $r^\alpha$, where $\alpha$ is typically between $1$ and $6$, depending on various environmental factors. While this problem can be solved optimally in $1$D, in higher dimensions it is known to be $NP$-hard for any $\alpha \geq 1$.

For the $1$D version of the problem, i.e., radio stations located on a line and $\alpha \geq 1$, we propose an optimal $O(n^2)$-time algorithm. This improves the running time of the best known algorithm by a factor of $n$. Moreover, we show a polynomial-time algorithm for finding the minimum cost range assignment in $1$D whose induced communication graph is a $t$-spanner, for any $t \geq 1$.

In higher dimensions, finding the optimal range assignment is $NP$-hard; however, it can be approximated within a constant factor. The best known approximation ratio is for the case $\alpha=1$, where the approximation ratio is $1.5$. We show a new approximation algorithm with improved approximation ratio of $1.5-\epsilon$, where $\epsilon>0$ is a small constant.

## Submission history

From: Lilach Chaitman-Yerushalmi [view email]**[v1]**Mon, 16 Feb 2015 13:47:05 GMT (273kb,D)

Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)

## 0 Thoughts to “Geometric Algorithms For The Minimum Cost Assignment Problem”