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 noncommercial and personal use.
Surveys on Approximation Algorithms for MinCost Connectivity Problems
Z. Nutov.
NodeConnectivity Survivable Network Problems.
[pdf]
Z. Nutov.
The kConnected 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

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

Z. Nutov.
Erratum: Approximating minimumcost connectivity problems via uncrossable bifamilies.
[pdf]
Manuscript.

Z. Nutov.
Improved approximation algorithms for minimum cost nodeconnectivity augmentation problems.
[pdf]
To appear in CSR 2016.

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

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

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

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

T. Fukunaga, Z. Nutov, R. Ravi
Iterative rounding approximation algorithms for degreebounded nodeconnectivity network design
[pdf]
SIAM J. Comput. 44(5):12021229, 2015.

Z. Nutov.
Approximating minimumcost edgecovers of crossing biset families.
[pdf]
Combinatorica 34(1):95114, 2014.
(Preliminary version: An almost O(log k)approximation for kconnected subgraphs. SODA 2009, 912921. )

Z. Nutov.
Small ledgecovers in kconnected graphs.
[pdf]
Discrete Applied Mathematics 161(1314):21012106, 2013.

Z. Nutov.
DegreeConstrained NodeConnectivity Problems.
[pdf]
Algorithmica 70(2):340364, 2014.

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

N. Cohen and Z. Nutov.
Approximating minimumpower edgemulticovers.
[pdf]
J. Comb. Optim. 30(3):563578, 2015.
(Preliminary version in CSR 2012).

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

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

Z. Nutov.
Approximating Subset kConnectivity Problems.
[pdf]
WAOA 2011.
(Submitted for journal publication.)

N. Cohen and Z. Nutov.
A (1+ln 2)approximation algorithm for minimumcost 2edgeconnectivity augmentation
of trees of bounded radius.
[pdf]
APPROX 2011, 147157.

Z. Nutov.
Approximating minimumcost edgecovers of crossing biset families.
[pdf]
Submitted for journal publication.
(Preliminary version:
An almost O(log k)approximation for kconnected subgraphs. SODA 2009, 912921. )

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

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

M. Hajiaghayi, R. Khandekar, G. Kortsarz, and Z. Nutov.
PrizeCollecting Steiner Network Problems.
[pdf]
To appear in ACM Transactions on Algorithms.
(Preliminary version in IPCO 7184, 2010.)

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

Z. Nutov.
Approximating minimum power kconnectivity.
[pdf]
Ad Hoc & Sensor Wireless Networks 9(12):129137, 2010.
(Preliminary version in ADHOC NOW 2008, 8693.)

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

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

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

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

Z. Nutov.
Approximating NodeConnectivity Augmentation Problems.
[pdf]
To appear in Algorithmica.
(Preliminary version in APPROX 286297, 2009.)

Y. Lando and Z. Nutov.
Inapproximability of survivable networks.
[pdf]
Theoretical Computer Science 410(2123):21222125, 2009.
(Preliminary version in APPROX 2008, 146152.)

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, 922931.)

Z. Nutov.
Approximating steiner networks with nodeweights.
[pdf]
SIAM Journal on Computing 39(7):30013022, 2010.
(Preliminary version in LATIN 2008, 411422.)

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

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

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

Z. Nutov.
Approximating minimum power covers of intersecting families
and directed edgeconnectivity problems.
[pdf]
Theoretical Computer Science, 411(2628):25022512, 2010.
(Preliminary version in APPROX 2006, 236247.)

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

M. Krivelevich, Z. Nutov, and R. Yuster.
Approximation algorithms for cycle packing problems.
[pdf]
SODA 2005, 556561.
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.

Y. Kortsarz, G. Kortsarz, and Z. Nutov.
Greedy approximation algorithms for directed multicuts
[pdf]
Networks 45(4):214217, 2005.
(Preliminary version in WAOA 2004, 6167.)

G. Kortsarz, and Z. Nutov.
Approximating knode connected subgraphs via critical graphs.
[pdf]
SIAM J. on Computing 35(1):247257, 2005.
(Preliminary version in STOC 2004, 138145.)

J. Cheriyan, T. Jordan, and Z. Nutov.
On rooted nodeconnectivity problems.
[pdf]
Algorithmica 30(3):353375, 2001.
(Preliminary version in APPROX 1998, 7788).

G. Kortsarz, and Z. Nutov.
Approximating nodeconnectivity problems via set covers.
[pdf]
Algorithmica 37(2):7592, 2003.
(Preliminary version in APPROX 2000, 194205).

Ye. Dinitz and Z. Nutov.
A 2level cactus model for the minimum and minimum+1 edge cuts
in a graph and its incremental maintenance.
In STOC 1995, 509518.
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

Y. Lando and Z. Nutov.
On minimum power connectivity problems.
[pdf]
J. of Discrete Algorithms 8(2):164173, 2010.
(Preliminary version in ESA 2007, 8798.)

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

R. Khandekar, G. Kortsarz, and Z. Nutov.
Approximating FaultTolerant Group Steiner Problems.
[pdf]
To appear in Theoretical Computer Science.
(Preliminary version in FSTTCS 2009, 263274.)

Z. Nutov.
Listing minimal edgecovers of intersecting families
with applications to connectivity problems.
[pdf]
Discrete Applied Mathematics 157(1):112117, 2009.

G. Kortsarz and Z. Nutov.
Approximating minimum power edgecovers and 2,3connectivity.
[pdf]
Discrete Applied Mathematics 157(8):18401847, 2009.

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

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

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

M. Elkin, Y. Lando, Z. Nutov, M. Segal, and H. Shpungin.
Novel algorithms for the network lifetime problem in wireless setting .
[pdf]
In ADHOC NOW 2008, 425438.

Z. Nutov.
Approximating directed weighteddegree constrained networks.
[pdf]
Theoretical Computer Science 412(810):901912, 2011.
Preliminary version In APPROX 2008, 219232.)

Z. Nutov.
Approximating maximum integral flows in wireless sensor networks
via weighteddegree constrained kflows.
[pdf]
In DIAL MPOMPC 2008, 2934.

Z. Nutov.
On extremal koutconnected graphs.
[pdf]
Discrete Mathematics 308:25332543, 2008.

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

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

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

Z. Nutov and M. Tsugaki.
On (t,k)shredders in kconnected graphs.
[pdf]
Ars Combinatoria 83:213219, 2007.

Z. Nutov and R. Yuster.
Packing directed cycles efficiently.
[pdf]
Discrete Applied Mathematics 155(2):8291, 2007.
(Preliminary version in MFCS 2004, 310321.)

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

Z. Nutov.
Approximating rooted connectivity augmentation problems.
[pdf]
Algorithmica 44:213231, 2006.
(Preliminary version in APPROX 2003, 141152.)

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

Z. Nutov.
Approximating multiroot 3outconnected subgraphs.
[pdf]
Networks 36(3):172179, 2000.
(Preliminary version in SODA 1999, 951952.)

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

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

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

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

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):197208, 1997.

A. Borobia, Z. Nutov, and M. Penn.
Doubly stochastic matrices and dicycle packings and covers in Eulerian digraphs.
Linear Algebra and Its Applications 246(13):361371, 1996.

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:149159, 1996.

Z. Nutov, and M. Penn.
On the integral dicycle packings and covers and the Linear Ordering Polytope.
Discrete Applied Mathematics 60(13):293309, 1995.
In preparation
M. Feldman and Z. Nutov.
Greedy Methods in Approximation Algorithms.