Publications:

Remark: Most of the papers here are published.
The copyrights have been transfered to the respective publishers.

Papers are divided into topics.
In every topic the publications are in reverse chronological order

Network design:

M. Hajiaghayi and R. Khandekar and G. Kortsarz and Z. Nutov,
Prize collection Steiner Network Problem and extensions, manuscript, 2009.

R. Khandekar and G. Kortsarz and Z. Nutov,
The fault-tolerant group Steiner problem,
FSTTCS, 2009, to appear.

For a pdf file

G.Kortsarz and Z. Nutov.
Approximating Minimum-Power Edge-Covers and 2,3-Connectivity, problems
Discrete Applied Math, 157(8):1840-1847, April 2009.

For a postscript file

G. Kortsarz and Z. Nutov,
Approximating some network design problems with node costs,
Approx 2009, pages 231-244.

For a pdf file
Also submitted to Theoretical Computer Science

M. Feldman and G. Kortsarz and Z. Nutov,
Improved approximation for the directed Steiner forest problem,
SODA, pages 922-931, 2009.
Also ECCC Report TR07-120, accepted on December 5, 2007.
Also submitted to Transaction on Algorithms.

For a postscript file

M. Hajiaghayi, G. Kortsarz, M. Salavatipour.
Approximating k Shallow-light trees and buy at bulk K-Steiner trees,
Algorithmica, 51(3):89-103,2009.

For a postscript file
Preliminary version in APPROX, pages 152-163, 2006.

G. Even, G. Kortsarz and Z. Nutov,
A 1.5-approximation for augmenting a connected graph into a two-connected graph,
submitted to IPL.

For a PDF file
A previous weaker 1.8 ratio approximation appeared in:
Transaction on Algorithms, volume 5, number 2, 2009
A preliminary conference version appeared in APPROX 2001, pages 90--101

G. Kortsarz and V. Mirrokni and Z. Nutov and E. Tsanko.
Approximating min-power connectivity problems, LATIN, pages 423-435, 2008

For a postscript file
Also Algorithmica, to appear.

R. Khandekar and G. Kortsarz and V. Mirrokni and M. Salavatipour,
Approximation and hardness results for Robust Network design with
Exponential Scenarios,
ESA, pages 589-600, 2008.
Also submitted to Algorithmica.

For a postscript file

C. Chekuri, M. Hajiaghayi, G. Kortsarz, M. Salavatipour.
Approximation Algorithms for node weighted
buy at bulk network design, SODA 2007, pages 1265-1274

For a postscript file
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,
FOCS 2006, pages 677-686
Also SICOMP to appear

For a PDF file
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, volume 74, pages 662-670

For a postscript file
Preliminary version in ICALP 2006, pages 443--452.

G. Kortsarz and Z. Nutov, Approximating min-cost connectivity problems,
Survey Chapter in handbook on approximation, 2006.

For a pdf file

M. Hajiaghayi, G. Kortsarz, V. Mirrokni and Z. Nutov,
Power optimization for connectivity problems.
Math. Prog. B. (special IPCO 2005 issue), volume 110, number 1, pages 195-208

For a postscript file
Preliminary version in: Integer Programming & Combinatorial Optimization
(IPCO) 2005, pages 349-361.

G. Kortsarz and Z. Nutov,
Approximation Algorithms for k-node connected subgraphs, via critical graphs,
SIAM journal on Computing, volume 35, number 1, pages 247-257, 2005.

For a postscript file
Preliminary version in: STOC 2004, 138--145

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,
volume 36, number 5
pages 1494-1511, 2007

For a postscript file
Preliminary version in: SODA, pages 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

For a postscript file
The above journal version corrects the conference version in:
SODA 2002. pages. 49--58.

G. Kortsarz, R. Krauthgamer, J. Lee,
On the hardness of approximating vertex connectivity network design problems.
SIAM J. on Computing, volume 33, number 3, pages 704--720, 2003.

For a postscript file
Preliminary version in APPROX 2002, pages 185-199.

G. Even, G. Kortsarz and W. Slany,
On network design: fixed charge flows and the covering
Steiner problem.
Transaction on Algorithms, Volume 1, number 1, pages 74-101, 2005.

For a postscript file
Preliminary version in
Scandinavian Symposium on Approximation Algorithms (SWAT),
pages 318-329, 2002.

G. Kortsarz and Z. Nutov,
Approximating small vertex connectivity problems via Set-Covers.
Algorithmica, 37 (2003), 75--92.

For a postscript file
Preliminary version in the Third International Workshop APPROX (APPROX),
pages 194--205, 2000.

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. On the hardness of approximating spanners,
Algorithmica, special APPROX-98 issue, 30(3): 432-450 (2001).

For a postscript file
Preliminary version in the first
International Workshop on Approximation Algorithms (APPROX),
pages 135-146, 1998.

G. Kortsarz and D. Peleg,
Approximating the Weight of Shallow Steiner Trees,
Discrete Applied Math, vol 93, pages 265-285, 1999.

For a postscript file
Remark: This paper was chosen into a special edition of Editors choice papers of
1999 for Discrete Applied Math.
See: http://www.elsevier.com/inca/publications/store/5/0/5/6/0/9/
Preliminary version in Symposium on discrete algorithms (SODA),
pages 103-110, 1997.

G. Kortsarz and D. Peleg.
Generating low-degree 2-spanners,
SIAM journal on computing, vol 27, No. 5, pages 1438-1456, 1998.

For a postscript file
Preliminary version in Symposium on discrete algorithms (SODA),
pages 556-563, 1994.

G. Kortsarz and D. Peleg.
Generating sparse 2-spanners,
Journal of algorithms, vol 17, pages 222-236, 1994.

For a postscript file
Preliminary version in Proc. 3rd Scandinavian
Workshop on Algorithm Theory (SWAT),
pages 73-82, 1992.

Facility Location:

M. Hajiaghayi, R. Khandekar and G. Kortsarz,
The Red-Blue Median Problem and its Generalization,
manuscript, 2009.

A note on two source location problems
Journal on discrete algorithms,
6:520-525, 2008

For a postscript file

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

For a postscript file
Preliminary version in STOC 2004, pages 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, pages 16--33, 2006.

For a postscript file
Preliminary version in the thirtieth International Colloquium on
Automata, Languages and computing
(ICALP) 2003, pages 164-175.

J. Bar-Ilan, G. Kortsarz and D. Peleg,
Generalized submodular cover problems and applications,
Theoretical Computer Science, 250, pages 179-200, 2001.

For a postscript file
Preliminary version in the Israeli Symp. on the Theory of
Computing and System
(ISTCS), pages 110-118, 1996.

J. Bar-Ilan, G. Kortsarz and D. Peleg.
Information Center Allocation,
The Electronic Library, vol 12, pages 361-365, 1994.

J. Bar-Ilan, G. Kortsarz and D. Peleg.
How to allocate network centers,
J. of Algorithms, vol 15, pages 385-415, 1993.

For a postscript file

Packing and scheduling:

G. Kortsarz, M. Landberg and Z. Nutov,
Approximating Maximum Subgraphs Without Short
Cycles, RANDOM-APPROX, pages 118-131, 2008.

For a postscript file
Also accepted to SIAM journal on Discrete Math subject to minor revisions.

M. Halldorsson, G. Kortsarz and M. Sviridenko.
Min Sum Edge Coloring in General Multigraphs via Configuration LP,
IPCO 359-373, 2008.
Also submitted to Transaction on Algorithms

For a postscript file

G. Kortsarz. A lower bound for approximating Grundy numbering,
2006, Discrete Mathematics and Theoretical Computer Science (DMTCS),
volume 9, number 1, pages 7-22.

For a postscript file

M. Elkin and G. Kortsarz,
An improved broadcast schedule for radio networks.
Transaction on Algorithms, volume 3, number 1, 2007

For a postscript file
Preliminary version in Symposium on Discrete Algorithms
(SODA), 2005, 222-231.

M. M. Halldorsson, G. Kortsarz, J. Radhakrishnan and
S. Sivasubramanian.
Complete Partitions of Graphs.
Combinatorica, 27(5)2008

For a postscript file
Preliminary version in Symposium on Discrete Algorithms
(SODA), 2005, 860-869.

M. Halldorsson and G. Kortsarz,
Multicoloring: Problems and Techniques.
Mathematical foundation of computer science
(MFCS), 2004, pages 25-41 (survey paper).

M. Elkin and G. Kortsarz.
Polylogarithmic additive inapproximability of the radio broadcast problem.
Siam Journal on Discrete Mathematics, volume 19, pages 881-899.

For a postscript file
Preliminary version in APPROX 2004, pages 105--116.

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, volume 4, number 1, 2008.

For a postscript file
Preliminary version in second Workshop on Approximation and
Online Algorithms (WAOA), pages 68-82, 2004.

M. Elkin and G. Kortsarz
A logarithmic lower bound for radio broadcast.
J. Algorithms, vol 52, num 1, 8-25, 2004

For a postscript file

R. Gandhi, M. Halldorsson and G. Kortsarz and H. Shachnai,
Improved results for data migration and open-shop scheduling.
Transaction on Algorithms, vol 2, number 1, pages 116-129, 2006.

For a postscript file
Preliminary version in Symposium on Automata, Languages
and Programming (ICALP) 2004, pages 658-669.

M. Elkin and G. Kortsarz.
An approximation algorithm for the directed telephone multicast problem.
Algorithmica, volume 45, number 4, pages 569-583, 2006.

For a postscript file
Preliminary version in Thirtieth International Colloquium on
Automata, Languages and Programming
(ICALP) 2003, pages 212-223.

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

For a postscript file
Preliminary version in the European Symposium on Algorithms
(ESA) 2003, pages 593--604.

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.

For a postscript file

G. Kortsarz and S. Shende.
Approximating the achromatic number problem on bipartite graphs.
SIAM Journal on Discrete Math, volume 21, number 2, pages 361-373

For a postscript file
Preliminary version in the European Symposium on
Algorithms (ESA) 2003, pages 385--396.

M. Elkin and G. Kortsarz. A sublogarithmic approximation algorithm
for undirected telephone multicast
Journal of Computing and System Sciences, pages 648-659, 2006.

For a postscript file
Preliminary version in SODA 2003. Pages 76-85.

M. Elkin and G. Kortsarz.
Combinatorial logarithmic approximation algorithm for the
directed telephone broadcast problem.
SIAM journal on Computing, volume 35, number 3, pages 672--689.

For a postscript file
Preliminary version on STOC 2002, pages 438--447.

M. Halldorsson and G. Kortsarz and H. Shachnai,
Sum coloring interval graphs and k-claw free graphs with
applications for scheduling dependent jobs,
Algorithmica, vol 37, pages 187-209.

For a postscript file
Preliminary version in APPROX-2001, 114--126.

G. Kortsarz and R. Krauthgamer,
On the approximation of the achromatic number.
Siam Journal of discrete methods, vol 14, No. 3, pages: 408--422, 2001

For a postscript file
Preliminary version in the Symposium on discrete algorithms
(SODA) 2001, pages 309--318.

U. Feige, M. Halldorsson, G. Kortsarz and A. Srinivasan.
Approximating the domatic number.
Siam journal on computing 32(1), 172--195, 2002.

For a postscript file
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.

For a postscript file
Preliminary version in the second International
Workshop on Approximation (APPROX), pages 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.

For a postscript file
Preliminary version in the Fifth Annual International
Computing and Combinatorics Conference
(COCOON), pages 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.

For a postscript file
Preliminary version in the European Symposium
on Algorithms, 1999 (ESA), pages 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, pages 135-140.

For a postscript file

A. Bar-Noy and G. Kortsarz.
The minimum color-sum of bipartite graphs.
J. of Algorithms, vol 28, no. 2, pages 339-365, 1998.

For a postscript file
Preliminary version in Symposium on Automata,
Languages and Programming (ICALP),
pages 738-748, 1997.

U. Feige, G. Kortsarz and D. Peleg.
The Dense k-subgraph problem,
Algorithmica, 29(3): 410-421, 2001.

For a postscript file
Preliminary version in the Proc. 34-th IEEE Symp. on
Foundations of Computer Science
(FOCS), pages 692-701, 1993.

G. Kortsarz and D. Peleg.
Traffic light scheduling on the grid,
Discrete applied math, vol 53, pages 211-234, 1994.

Preliminary version in the 6th International
Workshop on Distributed Algorithms (WDAG),
pages 238-252, 1992.

G. Kortsarz and D. Peleg.
Approximation algorithms for minimum time broadcast,
SIAM journal on discrete methods, vol 8, pages 401-427, 1995.

Preliminary version in the first Israeli Symp. on the
Theory of Computing and System (ISTCS),
pages 67-78, 1992.

Cuts and flow problems:

M. Hajiaghayi and R. Khandekar and G. Kortsarz and J. Mestre,
The checkpoint problem, manuscript, 2009.

R. Khandekar and G. Kortsarz and V. Mirrokni,
Overlapping vs. Non-overlapping Clustering: Conductance and Density,
manuscript, 2009

Y. Kortsarts and G. Kortsarz and Z. Nutov,
Greedy Approximation algorithm for directed multicuts,
Networks, 45(4):214-217, 2005.

For a postscript file
Preliminary version in the
second Workshop on Approximation and Online Algorithms
(WAOA), pages 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, pages 149--178.

For a postscript file
Preliminary version in the seventh
Workshop on Discrete Event Systems (WODES), 2004
pages 85-90.