Zeev Nutov's Publications (updated July 17)

Copyright Notice: Most of these papers were published in journals or conference proceedings, and the copyright
has been transferred to the publisher. The posting here is only for non-commercial and personal use.

Surveys on Approximation Algorithms for Min-Cost Connectivity Problems

Z. Nutov.
Node-Connectivity Survivable Network Problems. [pdf]

Z. Nutov.
The k-Connected Subgraph Problem. [pdf]

Z. Nutov.
Activation Network Design Problems. [pdf]

G. Kortsarz and Z. Nutov.
Approximating Minimum Cost Connectivity Problems. [pdf]
Ch. 58 In Handbook on Approximation Algorithms and Metaheuristics.
Ed. T. F. Gonzalez, Chapman & Hall/CRC.

Some updates to the chapter (let me know if I missed something):
Z. Nutov. Approximability status of Survivable Network problems. [pdf]


Selected and Recent Papers

  1. Z. Nutov.
    On the Tree Augmentation Problem. [pdf]
    To appear in ESA 2017.

  2. Z. Nutov.
    Erratum: Approximating minimum-cost connectivity problems via uncrossable bifamilies. [pdf]
    Manuscript.

  3. Z. Nutov.
    Improved approximation algorithms for minimum cost node-connectivity augmentation problems. [pdf]
    To appear in CSR 2016.

  4. G. Kortzars and Z. Nutov.
    A simplified 1.5 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. [pdf]
    ACM Trans. Algorithms 12(2):23, 2015. Submitted in 2014, published online May 2015.

  5. G. Kortsarz and Z. Nutov
    An LP 7/4-approximation for the Tree Augmentation Problem [pdf]
    November 2014.

  6. N. Cohen and Z. Nutov
    Approximating Steiner Trees and Forests with Minimum Number of Steiner Points [pdf]
    WAOA 2014. (Submitted for journal publication).

  7. G. Kortsarz and Z. Nutov
    Approximating Source Location and Star Survivable Network Problems [pdf]
    WAOA 2015. (Submitted for journal publication).

  8. T. Fukunaga, Z. Nutov, R. Ravi
    Iterative rounding approximation algorithms for degree-bounded node-connectivity network design [pdf]
    SIAM J. Comput. 44(5):1202-1229, 2015.

  9. Z. Nutov.
    Approximating minimum-cost edge-covers of crossing biset families. [pdf]
    Combinatorica 34(1):95-114, 2014.
    (Preliminary version: An almost O(log k)-approximation for k-connected subgraphs. SODA 2009, 912--921. )

  10. Z. Nutov.
    Small l-edge-covers in k-connected graphs. [pdf]
    Discrete Applied Mathematics 161(13-14):2101-2106, 2013.

  11. Z. Nutov.
    Degree-Constrained Node-Connectivity Problems. [pdf]
    Algorithmica 70(2):340-364, 2014.

  12. Z. Nutov.
    Survivable Network Activation Problems. [pdf]
    Theor. Comput. Sci. 514:105-115, 2013.
    (Preliminary version in LATIN 2012.)

  13. N. Cohen and Z. Nutov.
    Approximating minimum-power edge-multicovers. [pdf]
    J. Comb. Optim. 30(3):563-578, 2015.
    (Preliminary version in CSR 2012).

  14. M. Cygan, G. Kortsarz, and Z. Nutov.
    Steiner Forest Orientation Problems. [pdf]
    SIAM J. Discrete Math. 27(3):1503-1513, 2013.
    Preliminary version in ESA 2012.

  15. R. Khandekar, G. Kortsarz, and Z. Nutov,
    On some network design problems with degree constraints. [pdf]
    J. Comput. Syst. Sci. 79(5):725-736, 2013.
    (Preliminary version in APPROX 2011, 289-301.)

  16. Z. Nutov.
    Approximating Subset k-Connectivity Problems. [pdf]
    WAOA 2011.
    (Submitted for journal publication.)

  17. N. Cohen and Z. Nutov.
    A (1+ln 2)-approximation algorithm for minimum-cost 2-edge-connectivity augmentation of trees of bounded radius. [pdf]
    APPROX 2011, 147-157.

  18. Z. Nutov.
    Approximating minimum-cost edge-covers of crossing biset families. [pdf]
    Submitted for journal publication.
    (Preliminary version: An almost O(log k)-approximation for k-connected subgraphs. SODA 2009, 912--921. )

  19. G. Even, J. Feldman, G. Kortzars, and Z. Nutov.
    A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. [pdf]
    Transactions on Algorithms 5(2) 2009.
    (Preliminary version in APPROX 2001, 90-101.)

  20. Z. Nutov
    Approximating minimum cost connectivity problems via uncrossable bifamilies. [pdf]
    Submitted for journal publication.
    (Preliminary version in FOCS 417-426, 2009.)

  21. M. Hajiaghayi, R. Khandekar, G. Kortsarz, and Z. Nutov.
    Prize-Collecting Steiner Network Problems. [pdf]
    To appear in ACM Transactions on Algorithms.
    (Preliminary version in IPCO 71-84, 2010.)

  22. L. Kamma and Z. Nutov.
    Approximating Survivable Networks with Minimum Number of Steiner Points. [pdf]
    In WAOA 2010, 154-165.
    (Submitted for journal publication.)

  23. Z. Nutov.
    Approximating minimum power k-connectivity. [pdf]
    Ad Hoc & Sensor Wireless Networks 9(1-2):129-137, 2010.
    (Preliminary version in AD-HOC NOW 2008, 86-93.)

  24. G. Kortsarz, M. Langberg, and Z. Nutov.
    Approximating maximum subgraphs without short cycles. [pdf]
    SIAM Journal on Discrete Mathematics 24(1):255-269, 2010.
    (Preliminary version in APPROX 2008, 118-131.)

  25. Z. Nutov.
    Approximating connectivity augmentation problems. [pdf]
    ACM Transactions on Algorithms 6(1), 2009.
    (Preliminary version in SODA 2005, 176-185.)

  26. Y. Maduel and Z. Nutov
    Covering a laminar family by leaf to leaf links. [pdf]
    Discrete Applied Mathematics 158(13):1424-1432, 2010.

  27. Z. Nutov and A. Yaroshevitch.
    Wireless network design via 3-decompositions. [pdf]
    Information Processing Letters 109(19):1136-1140, 2009.

  28. Z. Nutov.
    Approximating Node-Connectivity Augmentation Problems. [pdf]
    To appear in Algorithmica.
    (Preliminary version in APPROX 286-297, 2009.)

  29. Y. Lando and Z. Nutov.
    Inapproximability of survivable networks. [pdf]
    Theoretical Computer Science 410(21-23):2122-2125, 2009.
    (Preliminary version in APPROX 2008, 146-152.)

  30. M. Feldman, G. Kortsarz, and Z. Nutov.
    Improved approximation algorithms for directed steiner forest. [pdf]
    To appear in J. of Computer and System Sciences.
    (Preliminary version in SODA 2009, 922-931.)

  31. Z. Nutov.
    Approximating steiner networks with node-weights. [pdf]
    SIAM Journal on Computing 39(7):3001-3022, 2010.
    (Preliminary version in LATIN 2008, 411-422.)

  32. G. Kortsarz, V. S. Mirrokni, Z. Nutov, and E. Tsanko.
    Approximating minimum power degree and connectivity problems. [pdf]
    Algorithmica 60(4):735-742, 2011.
    (Preliminary version in LATIN 2008, 423-435.)

  33. G. Kortsarz and Z. Nutov.
    Approximating some network design problems with node costs. [pdf]
    Theoretical Computer Science 412(35):4482-4492, 2011.
    In APPROX 2009, 231-243. (Submitted for journal publication.)

  34. G. Liberman and Z. Nutov.
    On shredders and vertex connectivity augmentation. [pdf]
    J. of Discrete Algorithms 5(1):91-101, 2007.

  35. Z. Nutov.
    Approximating minimum power covers of intersecting families and directed edge-connectivity problems. [pdf]
    Theoretical Computer Science, 411(26-28):2502-2512, 2010.
    (Preliminary version in APPROX 2006, 236-247.)

  36. G. Kortsarz and Z. Nutov.
    Tight approximation algorithm for connectivity augmentation problems. [pdf]
    J. Comput. Syst. Sci. 74(5):662-670, 2008.
    (Preliminary version in ICALP 2006, 443-452.)

  37. M. Krivelevich, Z. Nutov, and R. Yuster.
    Approximation algorithms for cycle packing problems. [pdf]
    SODA 2005, 556-561.
    The full version
    M. Krivelevich, Z. Nutov, M. R . Salavatipour, J. Verstraete, and R. Yuster.
    Approximation algorithms and hardness results for cycle packing problems. [pdf]
    ACM Transactions of Algorithms 3(4), 2007.

  38. Y. Kortsarz, G. Kortsarz, and Z. Nutov.
    Greedy approximation algorithms for directed multicuts [pdf]
    Networks 45(4):214-217, 2005.
    (Preliminary version in WAOA 2004, 61-67.)

  39. G. Kortsarz, and Z. Nutov.
    Approximating k-node connected subgraphs via critical graphs. [pdf]
    SIAM J. on Computing 35(1):247-257, 2005.
    (Preliminary version in STOC 2004, 138-145.)

  40. J. Cheriyan, T. Jordan, and Z. Nutov.
    On rooted node-connectivity problems. [pdf]
    Algorithmica 30(3):353-375, 2001.
    (Preliminary version in APPROX 1998, 77-88).

  41. G. Kortsarz, and Z. Nutov.
    Approximating node-connectivity problems via set covers. [pdf]
    Algorithmica 37(2):75-92, 2003.
    (Preliminary version in APPROX 2000, 194-205).

  42. Ye. Dinitz and Z. Nutov.
    A 2-level cactus model for the minimum and minimum+1 edge cuts
    in a graph and its incremental maintenance.

    In STOC 1995, 509-518.
    This paper has no journal version, but a full (unpublished) version in two parts is:
    - Part I: The odd case. [pdf]
    - Part II: The even case. [pdf]
    A related (unpublished) manuscript is:
    - Cactus tree type models for families of bisections of a set. [pdf]

Other Papers

  1. Y. Lando and Z. Nutov.
    On minimum power connectivity problems. [pdf]
    J. of Discrete Algorithms 8(2):164-173, 2010.
    (Preliminary version in ESA 2007, 87-98.)

  2. Z. Nutov and M. Segal.
    Improved approximation algorithm for maximum lifetime problems in wireless networks. [pdf]
    ALGOSENSORS 2009, 41-51. (Submitted for journal publication.)

  3. R. Khandekar, G. Kortsarz, and Z. Nutov.
    Approximating Fault-Tolerant Group Steiner Problems. [pdf]
    To appear in Theoretical Computer Science.
    (Preliminary version in FSTTCS 2009, 263-274.)

  4. Z. Nutov.
    Listing minimal edge-covers of intersecting families with applications to connectivity problems. [pdf]
    Discrete Applied Mathematics 157(1):112-117, 2009.

  5. G. Kortsarz and Z. Nutov.
    Approximating minimum power edge-covers and 2,3-connectivity. [pdf]
    Discrete Applied Mathematics 157(8):1840-1847, 2009.

  6. Z. Nutov.
    A Note on Rooted Survivable Networks. [pdf]
    Information Processing Letters 109(19):1114-1119, 2009.

  7. Z. Nutov and A. Sadeh
    Distributed primal-dual approximation algorithms for network design problems. [pdf]
    Manuscript, 2009. (Submitted for journal publication.)

  8. J. David and Z. Nutov.
    Approximating survivable networks with beta-metric costs. [pdf]
    To appear in Journal of Discrete Algorithms.

  9. M. Elkin, Y. Lando, Z. Nutov, M. Segal, and H. Shpungin.
    Novel algorithms for the network lifetime problem in wireless setting . [pdf]
    In AD-HOC NOW 2008, 425-438.

  10. Z. Nutov.
    Approximating directed weighted-degree constrained networks. [pdf]
    Theoretical Computer Science 412(8-10):901-912, 2011.
    Preliminary version In APPROX 2008, 219-232.)

  11. Z. Nutov.
    Approximating maximum integral flows in wireless sensor networks via weighted-degree constrained k-flows. [pdf]
    In DIAL M-POMPC 2008, 29-34.

  12. Z. Nutov.
    On extremal k-outconnected graphs. [pdf]
    Discrete Mathematics 308:2533-2543, 2008.

  13. Z. Nutov and D. Reichman.
    Approximating maximum satisfiable linear equation systems of bounded width. [pdf]
    Inf. Process. Lett. 106(5):203-207, 2008.

  14. G. Kortzars and Z. Nutov.
    A note on two source location problems. [pdf]
    J. of Discrete Algorithms 6(3):520-525, 2008.

  15. I. Beniaminy, Z. Nutov, and M. Ovadia.
    Approximating interval scheduling problems with bounded profits. [pdf]
    In ESA 2007, 487-497.

  16. Z. Nutov and M. Tsugaki.
    On (t,k)-shredders in k-connected graphs. [pdf]
    Ars Combinatoria 83:213-219, 2007.

  17. Z. Nutov and R. Yuster.
    Packing directed cycles efficiently. [pdf]
    Discrete Applied Mathematics 155(2):82-91, 2007.
    (Preliminary version in MFCS 2004, 310-321.)

  18. M. T. Hajiaghayi, G. Kortsarz, V. S. Mirrokni, and Z. Nutov.
    Power optimization for connectivity problems. [pdf]
    Math. Programming 110(1):195-208, 2007.
    (Preliminary version in IPCO 2005, 349-361.)

  19. Z. Nutov.
    Approximating rooted connectivity augmentation problems. [pdf]
    Algorithmica 44:213-231, 2006.
    (Preliminary version in APPROX 2003, 141-152.)

  20. Z. Nutov, I. Binyaminy, and R. Yuster.
    A (1 - 1/e)-approximation algorithm for the generalized assignment problem. [pdf]
    Operations Research Letters 34:283-288, 2006.

  21. Z. Nutov.
    Approximating multiroot 3-outconnected subgraphs. [pdf]
    Networks 36(3):172-179, 2000.
    (Preliminary version in SODA 1999, 951-952.)

  22. Z. Nutov and M. Penn.
    On integrality, stability, and compositions of dicycle packings and covers. [pdf]
    J. of Combinatorial Optimization 4(2):235-251,2000.

  23. V. Auletta, Ye. Dinitz, Z. Nutov, and D. Parente.
    A 2-approximation algorithm for finding an optimum 3-vertex connected spanning subgraph. [pdf]
    Journal of Algorithms 32(1):21-30, 1999.
    (Preliminary version in CIAC 1997, 13-24.)

  24. Ye. Dinitz and Z. Nutov
    A 3-approximation algorithm for finding optimum 4,5-vertex connected spanning subgraphs. [pdf]
    Journal of Algorithms 32(1):31-40, 1999.
    (Preliminary version in CIAC 1997, 13-24.)

  25. Z. Nutov and M. Penn.
    Faster approximation algorithms for weighted triconnectivity augmentation problems.
    Operations Research Letters, 21(5):219-223, 1997.

  26. Z. Nutov, M. Penn, and D. Sinreich.
    On mobile robots flow in locally uniform networks.
    Canadian Journal of Information Systems and Operational Research 35(4):197-208, 1997.

  27. A. Borobia, Z. Nutov, and M. Penn.
    Doubly stochastic matrices and dicycle packings and covers in Eulerian digraphs.
    Linear Algebra and Its Applications 246(1-3):361-371, 1996.

  28. Z. Nutov, and M. Penn.
    On non-{0,1,1/2} extreme points of the Generalized Transitive Tournament Polytope.
    Linear Algebra and Its Applications 233:149-159, 1996.

  29. Z. Nutov, and M. Penn.
    On the integral dicycle packings and covers and the Linear Ordering Polytope.
    Discrete Applied Mathematics 60(1-3):293-309, 1995.

In preparation

  • M. Feldman and Z. Nutov.
    Greedy Methods in Approximation Algorithms.