Publications:

Remark: Most of the papers here are published.
The copyrights
have been transferred to the respective publishers.
Please respect this.
Papers are divided into topics.
In every topic the publications are in reverse
chronological order

Survey Chapters in books

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.

For a pdf file

Guy Kortsarz
Fixed parameter approximability and hardness,
Encyclopedia of algorithms, 2015.

For a pdf file

G. Kortsarz and Z. Nutov,
Approximating min-cost connectivity
problems,
Survey Chapter in Approximation
Algorithms and Metaheuristics, edited by Teo Gonzalez, 2006.

For a pdf file
To keep the survey updated,
Zeev Nutov maintains a file that
discusses new results.

For a pdf file

Network design:

M. Dinitz, A. Koranteng and Guy Kortsarz,
Relative Survivable Network Design
APPROX 2022. to apppear.

X. Guo, G. Kortsarz, B Laekhanukit, S. Li and D. Vaz J,
Bounded Degree Steiner Tree and Bounded Degree Group Steiner tree.
Algorithmica, 84(5): 1252-1278 2022.

For a pdf file
Preliminary version in
RANDOM-APPROX, pages 39:1-39:24, 2020

Guy Kortsarz and Zeev Nutov.
Bounded-Degree Group Steiner problems,
Discrete Applied Math, 2022, 309: 229-239, 2022

For a pdf file
Prelimnnry version in
31st International Workshop on Combinatorial Algorithms
(IWOCA), pages 243 254, 2020.

G. Kortsarz and N. Nutov.
An LP with 7/4 integrality gap for the tree augmentation problems.
Discrete Applied Math, 239:94-105, 2018.

For a pdf file
Preliminary version in APPROX-RANDOM, pages 13:1-13:16, 2016.

G. Kortsarz and Z. Nutov
A simplified 3/2 ratio approximation algorithm
for the tree augmentation problem.
Transaction on Algorithm, 12(2):23, 2016.

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

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

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

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

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

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

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

For a pdf file

G. Kortsarz and Z. Nutov,
Approximating some network design problems with node costs,
Theor. Comput. Sci. 412(35): 4482-4492 2011.

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

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

For a pdf file
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,

For a pdf file
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
This paper has a mistaken definition.
A full correct version appeared only in 2016 in TALG

G. Kortsarz and V. Mirrokni and Z. Nutov and E. Tsanko.
Approximating min-power connectivity problems,
Algorithmica, volume 60(4):735--742,
May 2011.

For a pdf file
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

For a pdf file
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

For a pdf 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,
SIAM Journal on computation 39(5):1772-1798. January 2010.

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

For a pdf file
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

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

For a pdf file
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

For a pdf file
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

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

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

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

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

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

Spanner problems:

E. Chlamtac, M. Dinitz, G. Kortsarz and B. Laekhanukit,
Approximating Spanners and Directed Steiner Forest:
Upper and Lower Bounds.
ACM Transactions on Algorithms June 2020.

For a pdf file
Preliminary version in 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

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

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

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

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

Facility Location:

Zeev Nutov, Guy Kortsarz and Eli Shalom.
Approximating activation edge-cover and facility location problems.
Theoretical Computer Science
to appear.

For a pdf file
Preliminary version in MFCS, pages 20:1-20:14, 2019.

Gruia Calinescu, Guy Kortsarz and Zeev Nutov
Improved approximation algorithms for minimum power covering problems
Theoretical Computer Science. 795: 785-300, 2019.

For a pdf file
Perliminary version in
Workshop on Approximation and On-Line algorithms (WAOA),
Pages 134-148, 2018.

Hossein Esfandiar and G. Kortsarz.
Low-Risk Mechanism for Kidney Exchange Game,
Discrete Applied Math, 243:6-53, 2018.

For a pdf file
Preliminary version in LATIN, Pages 416-428, 2016
Also Symposium
on Algorithmic Game Theory (SAGT), pages 303-304 2016.

G. Kortsarz and Z. Nutov.
Approximation for source location and the star SNDP problem.
Theor. Comput. Sci. 674: 32-42, 2017

For a pdf file
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

For a pdf file
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

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

For a pdf file
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

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

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

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

For a pdf file

Graph partitioning problems
and scheduling problems

E. Chlamtac, M. Dinitz, C. Konrad
G. Kortsarz and G. Rabanca
The Densest k-Subhypergraph Problem
SIAM Journal on Discrete Math, 239: 94-105, 2018

For a pdf file
Preliminary version in 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
SIAM Journal on Discrete Math, 31(4): 2626-2646, 2017

For a pdf file
Preliminary version in 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

For a pdf file
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)

For a pdf file
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

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

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

For a pdf file
No conference version

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

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

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

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

For a pdf file

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.

For a pdf file
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

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

For a pdf file

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

For a pdf file
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

For a pdf file
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

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

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

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

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

For a pdf file

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

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

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

For a pdf file
Preliminary version in the 6th International
Workshop on Distributed Algorithms (WDAG),
pp 238-252, 1992.

Broadcasting problems

M. M Halldorsson, G. Kortsarz, P. Mitra and T. Tonoyan.
Spanning Trees With Edge Conflicts and Wireless Connectivity.
Algorithmica. 83(11): 3469-3490, 2021

For a pdf file
Preliminary version in ICALP, pages 158:1-158:15, 2018.

Approximating radio aggregation
Theoretical Computer Science, 840: 143-153, 2020.
A special issue of papers
selected from ALGOSENSORS 2015 and 2016.

For a pdf file
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

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

For a pdf file
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

For a pdf file
Preliminary version in
(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

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

For a pdf file
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

For a pdf file
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

For a pdf file

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

For a pdf file
Preliminary version in the Israeli
conference on algorithms (ISTCS) 1992: 67-78

Cut problems:

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, 29: 31-34, 2020.

For a pdf file

Hajiaghayi, Kortsarz MacDavid, Purohit, and Sarpatwar.
Approximating the Connected Max Cut Problem.
Theoretical Computer Science, 74-85, 2020.

For a pdf file
Preliminary version 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.

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

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

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

For a pdf file
Preliminary version in the seventh
Workshop on Discrete Event Systems (WODES), 2004

Fix parameter tractability

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. SICOMP, 49(4): 772-810 2020.

For a pdf file.
Preliminary version FOCS, pages 743-754, 2017

M. Cygan, M. Halldorsson and G. Kortsarz
Tight boubnds for subexonential
approximation for Set Cover.
WAOA 2020, pages 159-173, 2020.

For a pdf file
Not submitted to a journal
The conference version has
all the details.

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)

For a pdf file
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

For a pdf file
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.
The first paper top prove super exponential time
super constant hardness for Set Cover and Clique.