The copyrights

have been transferred to the respective publishers.

Papers are divided into topics.

In every topic the publications are in reverse

chronological order

Magnus M. Halldorsson and G. Kortsarz,

Algorithms for Chromatic Sums, Multicoloring,

and Scheduling Dependent Jobs,

Survey Chapter in Approximation

Algorithms and Metaheuristics,

edited by Teo Gonzalez, 2017.

Guy Kortsarz

Fixed parameter approximability and hardness,

Encyclopedia of algorithms, 2015.

G. Kortsarz and Z. Nutov,

Approximating min-cost connectivity

problems,

Survey Chapter in Approximation

Algorithms and Metaheuristics, edited by Teo Gonzalez, 2006.

To keep the survey updated,

Zeev Nutov maintains a file that

discusses new results.

M. Halldorsson and G. Kortsarz,

Multicoloring: Problems and Techniques, a survey.

Mathematical foundation of computer science

(MFCS), pp 25-41. 2004

An LP with 7/4 integrality gap

for the tree augmentation problems.

APPROX-RANDOM 2016: 13:1-13:16

G. Kortsarz and Z. Nutov

A simplified 3/2 ratio approximation algorithm

for the tree augmentation problem.

Transaction on Algorithm, 12(2):23, 2016.

Preliminary version in

Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov.

A 3/2-Approximation Algorithm for Augmenting the

Edge-Connectivity of a Graph from 1 to 2

Using a Subset of a Given Edge Set.

RANDOM-APPROX 2001: 90-101

M Dinitz, G. Kortsarz and Z. Nutov.

Approximating the Steiner k-Forest problem

with nearly uniform weights.

Transaction of algorithms, 13(3): 40:1-40:16, 2017.

Preliminary version in RANDOM-APPROX 2014, 115--127.

M. Hajiaghayi, R. Khandekar, G, Kortsarz, and Z. Nutov

Approximation fixed cost k-flow problems.

Theory Comput. Syst. 58(1): 4-18 (2016)

Special issue for papers selected from WAOA 2014.

Preliminary version in

Workshop on Approximation and Online Algorithms (WAOA),

pages 49-60, 2013.

M. Cygan, G. Kortsarz and Z.Nutov.

Steiner Forest Orientation Problems.

Siam Journal on Discrete Math, 27(3):1503--1513, 2013.

Preliminary version in ESA, pages 361-372, 2012.

G. Kortsarz R. Khandekar and Zeev Nutov.

Approximating some network design problem with degree constrains.

Journal of Computing and Sciences (JCSS), 79(5)725-736. 2012.

Preliminary version in RANDOM-APPROX, pages 289-301, 2011.

M. Hajiaghayi and R. Khandekar and G. Kortsarz and Z. Nutov,

Prize collection Steiner Network Problem and extensions,

ACM Transactions on Algorithms, Vol. 9, No. 1, Article 2. 2011.

Preliminary version in IPCO, pp 71-84, 2010.

R. Khandekar and G. Kortsarz and Z. Nutov,

The fault-tolerant group Steiner problem,

Theoretical Computer Science, 416(27):55-64, January 2012.

Preliminary version in:

FSTTCS, pp 263-274, December 2009

G.Kortsarz and Z. Nutov.

Approximating Minimum-Power Edge-Covers and 2,3-Connectivity,

problems

Discrete Applied Math, 157(8):1840-1847, April 2009.

G. Kortsarz and Z. Nutov,

Approximating some network design problems with node costs,

Theor. Comput. Sci. 412(35): 4482-4492 2011.

Preliminary version in:

RANDOM-APPROX 2009, pp 231-244.

M. Feldman and G. Kortsarz and Z. Nutov,

Improved approximation for the directed Steiner forest problem,

JCSS,

78(1):279-292.

Preliminary version in SODA 2009, pages 922-931

M. Hajiaghayi, G. Kortsarz, M. Salavatipour.

Approximating k Shallow-light trees

and buy at bulk k-Steiner trees,

Algorithmica, 51(3):89-103,2009.

Preliminary version in

RANDOM-APPROX, pp 152-163, 2006.

G. Even, John Feldman, G. Kortsarz and

Z. Nutov,

A 1.8-approximation for augmenting a connected graph into a two-connected graph,

Transaction on Algorithms, volume 5, number 2, 2009

G. Even, G. Kortsarz and

Z. Nutov,

A 1.5-approximation for

augmenting a connected graph into a two-connected graph,

Inf. Process. Lett. 111(6):296-300, 2011

Preliminary version, RANDOM-APPROX 2001, pp 90-101

G. Kortsarz and V. Mirrokni and Z. Nutov and E. Tsanko.

Approximating min-power connectivity problems,

Algorithmica, volume 60(4):735--742,

May 2011.

A preliminary version appeared in LATIN, pp 423-435, 2008

R. Khandekar and G. Kortsarz and

V. Mirrokni and M. Salavatipour,

Approximation and hardness results for Robust Network design with

exponential Scenarios, Algorithmica, 63(4): 795-814, January 2013

Preliminary version in ESA, pp 589-600, 2008.

C. Chekuri, M. Hajiaghayi, G. Kortsarz, M. Salavatipour.

Approximation Algorithms for node weighted

buy at bulk network design,

SODA 2007, pp 1265-1274

Remark: This paper has no journal version

(Merged with the FOCS 2006 paper)

C. Chekuri, M. Hajiaghayi, G. Kortsarz, M. Salavatipour.

Polylogarithmic approximation algorithm

for non-uniform multicommodity buy at bulk,

SIAM Journal on computation 39(5):1772-1798. January 2010.

Preliminary version in FOCS pp 677-686 2006.

Remark: contains the vertex version of the problem as well.

G. Kortsarz and Z. Nutov.

Tight bounds for connectivity augmentation

problems,

Journal of Computing and System Sciences, 74:662-670. 2008.

Preliminary version in ICALP 2006, pp 443--452.

M. Hajiaghayi, G. Kortsarz, V. Mirrokni and Z. Nutov,

Power optimization for connectivity problems.

Math. Prog. B. (special issue of papers selected from IPCO 2005),

volume 110(1):195-208. 2007

Preliminary version in:

Integer Programming & Combinatorial Optimization

(IPCO) pp 349-361. 2005

G. Kortsarz and Z. Nutov,

Approximation Algorithms for k-node connected subgraphs, via

critical graphs,

SIAM journal on Computing, volume 35(1):247-257, 2005.

Preliminary version in:

STOC 138--145. 2004

E. Halperin, G. Kortsarz, R. Krauthgamer,

A. Srinivasan and N. Wang,

Integrality ratio for Group Steiner

Trees and Directed Steiner Trees,

SIAM Journal on Computing,

36(5) :(1494-1511), 2007

Preliminary version in:

SODA, pp 275-284, 2003.

C. Chekuri, G. Even, G. Kortsarz.

A combinatorial approximation algorithm for the Group Steiner problem.

Discrete Applied Math, volume 154(1):15-34, 2005

The above journal version corrects the conference version in:

SODA 2002. pp. 49--58.

G. Kortsarz, R. Krauthgamer, J. Lee,

On the hardness of approximating vertex connectivity network design problems.

SIAM J. on Computing, 33(3):704--720, 2003.

Preliminary version in RANDOM-APPROX 2002, pp 185-199.

G. Even, G. Kortsarz and W. Slany,

On network design: fixed charge flows and the covering

Steiner problem.

Transaction on Algorithms, 1(1):74-101, 2005.

Preliminary version in

Scandinavian Symposium on Approximation Algorithms (SWAT),

pp 318-329, 2002.

G. Kortsarz and Z. Nutov,

Approximating small vertex connectivity problems via Set-Covers.

Algorithmica, 37:75--92, 2003.

Preliminary version in the Third International Workshop RANDOM-APPROX

pp 194--205, 2000.

G. Kortsarz and D. Peleg,

Approximating the Weight of Shallow Steiner Trees,

Discrete Applied Math, vol 93:265-285, 1999.

Remark: This paper was chosen into a special edition of Editors choice

of best papers in Discrete Applied Math, in 1999.

See: http://www.elsevier.com/inca/publications/store/5/0/5/6/0/9/

Preliminary version in Symposium on discrete algorithms (SODA),

pp 103-110, 1997.

Approximating Spanners and Directed Steiner Forest:

Upper and Lower Bounds,SODA, pages 534-553 2017.

M Dinitz, G. Kortsarz and R. Raz

Label Cover instances with large girth and the

hardness of approximating spanners. Transaction on Algorithms, 12(2):25 2016

Preliminary version in ICALP pages 290-301. 2012.

G. Kortsarz. On the hardness of approximating spanners,

Algorithmica, special issue of papers selected from APPROX-98, 30(3):432-450, 2001.

Preliminary version in APPROX 1998, 135-146

D. Handke and G. Kortsarz.

The Steiner Tree-Spanner problem and related tree-covering problems.

The 26th International Workshop on Graph-Theoretic Concepts in

Computer Science (WG) 2000.

Remark: this paper has no journal version.

G. Kortsarz and D. Peleg.

Generating low-degree 2-spanners,

SIAM journal on computing, 27(5):1438-1456, 1998.

Preliminary version in Symposium on discrete algorithms (SODA),

pp 556-563, 1994.

G. Kortsarz and D. Peleg.

Generating sparse 2-spanners,

Journal of algorithms, 17:222-236, 1994.

Preliminary version in Proc. 3rd Scandinavian

Workshop on Algorithm Theory (SWAT),

pp 73-82, 1992.

Hossein Esfandiar and G. Kortsarz.

Low-Risk Mechanism for Kidney Exchange Game,

LATIN, Pages 416-428, 2016

2 pages brief announcement

on Algorithmic Game Theory (SAGT), 2015, 303-304.

G. Kortsarz and Z. Nutov.

Approximation for source location and the star SNDP problem.

Theor. Comput. Sci. 674: 32-42, 2017

Preliminary version in:

Workshop on Graph theoretic concepts in computer science (WG)

203-218, 2015.

Rajiv Gandhi and Guy Kortsarz,

On edge expansion problems and the small set expansion conjecture.

Discrete Applied Math. 194: 93-101, 2015

Preliminary version in:

Workshop on Graph theory (WG) 2014,

pages 189-200 2014.

Approximation Algorithms for Movement Repairman,

M. Hajiaghayi, Rohit Khandekar, M.R Khani and G. Kortsarz

TALG 12(4): 54, 2016

Preliminary version in RANDOM-APPROX 2013, pages 218--232, 2013.

M. Hajiaghayi, R. Khandekar and G. Kortsarz,

The Red-Blue Median Problem and its Generalization,

Algorithmica volume 68 number 4, pages 795-814, 2012.

Special issue of papers selected of

ESA 2010.

Preliminary version in:

ESA, 314-325, 2010.

Guy Kortsarz and Zeev Nutov,

A note on two source location problems

Journal on discrete algorithms,

6:520-525, 2008

J. Chuzhoy and S. Guha and E. Halperin and S. Khanna and

G. Kortsarz and R. Krauthgamer and S. Naor.

Tight lower bounds for the asymmetric k-center problem.

Journal of Association Computing Machinery,

52(4):538-551, 2005.

Preliminary version in STOC 2004, pp 21--27

R. Gandhi and E. Halperin and S. Khuller and G. Kortsarz and A. Srinivasan.

An improved approximation algorithm for vertex cover with hard capacities,

Journal of Computing and System Sciences, pp 16-33, 2006.

Preliminary version in the thirtieth International Colloquium on

Automata, Languages and computing

(ICALP) pp 164-175 2003.

J. Bar-Ilan, G. Kortsarz and D. Peleg,

Generalized submodular cover problems and applications,

Theoretical Computer Science, 250:179-200, 2001.

Preliminary version in the Israeli Symp. on the Theory of

Computing and System

(ISTCS), pp 110-118, 1996.

J. Bar-Ilan, G. Kortsarz and D. Peleg.

Information Center Allocation,

The Electronic Library, 12:361-365, 1994.

J. Bar-Ilan, G. Kortsarz and D. Peleg.

How to allocate network centers,

J. of Algorithms, 15:385-415, 1993.

and scheduling problems

E. Chlamtac, M. Dinitz, C. Konrad

G. Kortsarz and G. Rabanca

The Densest k-Subhypergraph Problem

RANDOM-APPROX, 6:1-6:19. 2016.

A. Bhangale, R. Gandhi, M Hajiaghayi, R. Khandekar, G Kortsarz.

Bicovering: Covering the

edges with two small subsets of vertices

ICALP pages, 601-612, 2016.

Michael Dinitz and Guy Kortsarz,

Matroid Secretary for Regular and Decomposable Matroids,

SIAM Journal on Computing, 43(5):1807-1830, 2014

Preliminary version in SODA, pages 108--117, 2013.

M. Hajiaghayi and R. Khandekar and G. Kortsarz and V. Liaghat,

On a local protocol for Concurrent File transfers,

Theory of Computing. Special issue

of papers selected from SPAA 2011.

55(3): 613-636 (2014)

Preliminary version on:

23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),

pp 269--278, June 2011.

G. Kortsarz, M. Landberg and Z. Nutov,

Approximating Maximum Subgraphs Without Short

Cycles. SIAM J. Discrete Math. 24(1):255-269, 2010

Preliminary version in RANDOM-APPROX, pp 118-131, 2008.

M. Halldorsson, G. Kortsarz and M. Sviridenko.

Min Sum Edge Coloring in General Multigraphs via Configuration LP,

Transaction on algorithms, 7(2):22-, March 2011.

Preliminary version in

IPCO, pp 359-373, 2008.

G. Kortsarz. A lower bound for approximating Grundy numbering,

Discrete Mathematics and Theoretical Computer Science (DMTCS).

9(1):7-22. 2006.

No conference version

M. M. Halldorsson, G. Kortsarz, J. Radhakrishnan and

S. Sivasubramanian.

Complete Partitions of Graphs.

Combinatorica, 27(5):2008

Preliminary version in Symposium on Discrete Algorithms

(SODA), pp 860-869. 2005.

R. Gandhi, M. Halldorsson and G. Kortsarz and H. Shachnai.

Improved Bounds for Sum Multicoloring and Weighted Completion

Time of Dependent Jobs,

Transaction on Algorithm, 4(1), 2008.

Preliminary version in second Workshop on Approximation and

Online Algorithms (WAOA), pp 68-82, 2004.

R. Gandhi, M. Halldorsson and G. Kortsarz and H. Shachnai,

Improved results for data migration and open-shop scheduling.

Transaction on Algorithms, 2(1):116-129, 2006.

Preliminary version in Symposium on Automata, Languages

and Programming (ICALP) pp 658-669. 2004.

Remark: the above is not the original journal paper.

Sviridenko found a mistake and we corrected it

and improved the ratio in the process.

The above PDF is a self contained description

of the technical details.

L. D. Gaspero and J. Ga"rtner and

G. Kortsarz and N. Musliu

and A. Schaerf and W. Slany,

The minimum shift design problem: theory and practice.

Annals on Operations Research

(special Volume on "Personnel Scheduling and Planning"),

155(1):119-142 2006

Preliminary version in the European Symposium on Algorithms

(ESA) 2003, pp 593--604. 2004

L. D. Gaspero, J. Gartner,

G. Kortsarz, N. Musliu,

A. Schaerf and W. Slany,

A Hybrid Network Flow Tabu Search Heuristic for the Minimum

Shift Design Problem.

In the fifth Metahueristics International Conference, Kyoto, Japan, 2003 (no journal version).

G. Kortsarz and S. Shende.

Approximating the achromatic number problem on bipartite graphs.

SIAM Journal on Discrete Math, 21(2):361-373. 2005

Preliminary version in the European Symposium on

Algorithms (ESA) 2003, pp 385--396.

M. Halldorsson and G. Kortsarz and H. Shachnai,

Sum coloring interval graphs and k-claw free graphs with

applications for scheduling dependent jobs,

Algorithmica, 37:187-209. 2003

Preliminary version in RANDOM-APPROX 114--126. 2001

G. Kortsarz and R. Krauthgamer,

On the approximation of the achromatic number.

Siam Journal of discrete methods, vol 14, No. 3, pp: 408--422, 2001

Preliminary version in the Symposium on discrete algorithms

(SODA) pp 309--318 2001.

U. Feige, M. Halldorsson, G. Kortsarz and A. Srinivasan.

Approximating the domatic number.

Siam journal on computing 32(1), 172--195, 2002.

Preliminary version in the

Thirty Second Symposium on the Theory of Computer Science

(STOC), 134--143, 2000.

M. Halldorsson and G. Kortsarz.

Tools for Multicoloring with

applications to Planar Graphs and Partial k-trees.

J. of Algorithms, 42,334-366, 2002.

Preliminary version in the second International

RANDOM-APPROX pp 73-84, 1999.

M. Halldorsson, G. Kortsarz, A. Proskurowski,

R. Salman, H. Shachnai and J. A. Telle.

Sum Multicoloring Trees.

Information and computing, vol. 180, 113--129, 2003.

Preliminary version in the Fifth Annual International

Computing and Combinatorics Conference

(COCOON), pp 171-180, 1999.

A. Bar-Noy, M. Halldorsson, G. Kortsarz,

R. Salman and H. Shachnai,

Minimum Sum Multicoloring of Graphs.

J. of Algorithms, 37(2):422-450, 2000.

Preliminary version in the European Symposium

on Algorithms, 1999 (ESA), pp 390-401, 1999.

A. Bar-Noy, M. Halldorsson, G. Kortsarz,

A Matched Approximation Bound for the Sum of a Greedy Coloring,

Information Processing letters, vol 71, 1999, pp 135-140.

A. Bar-Noy and G. Kortsarz.

The minimum color-sum of bipartite graphs.

J. of Algorithms, vol 28, no. 2, pp 339-365, 1998.

Preliminary version in Symposium on Automata,

Languages and Programming (ICALP),

pp 738-748, 1997.

U. Feige, G. Kortsarz and D. Peleg.

The Dense k-subgraph problem,

Algorithmica, 29(3): 410-421, 2001.

Preliminary version in the Proc. 34-th IEEE Symp. on

Foundations of Computer Science

(FOCS), pp 692-701, 1993.

G. Kortsarz and D. Peleg.

Traffic light scheduling on the grid,

Discrete applied math, vol 53, pp 211-234, 1994.

Preliminary version in the 6th International

Workshop on Distributed Algorithms (WDAG),

pp 238-252, 1992.

Approximating radio aggregation

Theoretical Computer Science, pages 1--13, 2016.

Special issue for papers

selected from ALGOSENSORS 2015 and 2016.

Preliminary version in ALGOSENSORS, pages 169-182, 2015.

M. Elkin and G. Kortsarz.

An improved broadcast schedule for radio networks.

Transaction on Algorithms, 3(1), 2007

Preliminary version in

SODA pp 76-85. 2003.

M. Elkin and G. Kortsarz. A sublogarithmic approximation algorithm

for undirected telephone multicast

Journal of Computing and System Sciences, 72(4):648-659, 2006.

Preliminary version in

SODA, pp 76-85, 2003.

M. Elkin and G. Kortsarz.

An approximation algorithm for the directed telephone multicast problem.

Algorithmica, volume 45(4)569-583,2006

Preliminary version in Thirtieth International Colloquium on

Automata, Languages and Programming

(ICALP) pp 212-223 2003.

M. Elkin and G. Kortsarz,

Polylogarithmic additive inapproximability

for the radio broadcast problem.

Siam Journal on Discrete Mathematics,

19:881-899 2005

Preliminary version in

RANDOM-APPROX, pp 105--116, 2004

M. Elkin and G. Kortsarz.

Combinatorial logarithmic

approximation algorithm for the

directed telephone broadcast

problem.

SIAM journal on Computing, 35(3):672--689, 2005.

Preliminary version on

STOC 2002, pp 438--447.

M. Elkin and G. Kortsarz.

Polylogarithmic additive inapproximability of

the radio broadcast problem.

Siam Journal on Discrete Mathematics, 19:881-899 2005

Preliminary version in

RANDOM-APPROX 105-116, 2004.

M. Elkin and G. Kortsarz.

A logarithmic lower bound for radio broadcast.

J. Algorithms, 52(1):8-25, 2004

G. Kortsarz and D. Peleg.

Approximation algorithms for

minimum time broadcast,

SIAM journal on discrete methods, vol 8, pp 401-427, 1995.

Preliminary version in the Israeli

conference on algorithms (ISTCS) 1992: 67-78

The tree with maximum profit on the leaves problem

and connections to Connected Max Cut Problems.

R. Gandhi, M .Hajiaghayi, G. Kortsarz, M Purohit, and

K. Sarpatwar. IPL, to appear.

Hajiaghayi, Kortsarz MacDavid, Purohit, and Sarpatwar.

Approximating the Connected Max Cut Problem.

ESA, pages 693-704 2015.

M. Hajiaghayi and R. Khandekar and G. Kortsarz and J. Mestre,

The checkpoint problem,

Theoretical Computer Science 452:88-99, 2012.

Preliminary version in RANDOM-APPROX 2010, pages 219-231.

R. Khandekar and G. Kortsarz and V. Mirrokni,

On the advantage of overlap clustering for minimizing the conductance.

Algorithmica, 69(4):844-863, 2014.

Preliminary version in LATIN 2012, 495-505.

Y. Kortsarts and G. Kortsarz and Z. Nutov,

Greedy Approximation algorithm for directed multicuts,

Networks, 45(4):214-217, 2005.

Preliminary version in the

second Workshop on Approximation and Online Algorithms

(WAOA), pp 61-67, 2004.

S. Khuller and G. Kortsarz and K. R. Rohloff.

Approximating the Minimal Sensor Selection for Supervisory Control.

Journal of Discrete Event Dynamic Systems: Theory and Applications

(special issue for papers selected

from WODES 2004), volume 16, pp 149--178.

Preliminary version in the seventh

Workshop on Discrete Event Systems (WODES), 2004

P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit,

P. Manurangsi and D. Nanogkai and Luva Trevisan.

From Gap-ETH to FPT-Inapproximability:

Clique, Dominating Set, and More. FOCS 2017 to appear.

,

M. Cygan. B. Laekhanukit G. Kortsarz

Tight running time for approximating the

directed Steiner tree problem.

Manuscript.

Chitnis, Esfandiari, Hajiaghayi,

Khandekar, Kortsarz and Seddighin

A Tight Algorithm for Strongly Connected

Steiner Subgraph On Two Terminals With Demands

Algorithmica,

77(4): 1216-1239 (2017)

Preliminary version in

IPEC 2014, pages 159-171. 2014.

Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Guy Kortsarz:

Fixed Parameter and approximation algorithms: a new look.

In IPEC, 110-122, 2013

This paper has no journal version.

M.T. Hajiaghayi and R. Khandekar G. Kortsarz

Super expoential time FPT hardness for Set Cover and Clique.

Unpublished manuscript.