# 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.

Algorithms for Chromatic Sums, Multicoloring, and Scheduling Dependent Jobs

Guy Kortsarz

Fixed parameter approximability and hardness,

Encyclopedia of algorithms, 2015.

Fixed parameter approximability and hardness

G. Kortsarz and Z. Nutov,

Approximating min-cost connectivity

problems,

Survey Chapter in Approximation

Algorithms and Metaheuristics, edited by Teo Gonzalez, 2006.

ApproximatingmMin-costConnectivitySurveyChapter

To keep the survey updated,

Zeev Nutov maintains a file that

discusses new results.

ChapterSurveyUpdates

**Network Design**

Michael Dinitz, Guy Kortsarz, Shi Li, Degrees and Network Design: New Problems and Approximations, APPROX 2024 to appear

Degrees and Network Design New Problems and Approximations

Michael Dinitz, Ama Koranteng, Guy Kortsarz, Zeev Nutov, Improved Approximations for Relative Survivable Network Design, The Workshop on Approximation and Online Algorithms (WAOA) 2023, 190-204

ImprovedApproximationsforRelativeSurvivableNetworkDesign

Michael Dinitz, Ama Koranteng, Guy Kortsarz,

Relative Survivable Network Design

APPROX/RANDOM 2022, pages 41:1-41:19

Relative Survivable Network Design

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.

On Approximating Degree-Bounded Network Design Problems

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

The minimum Degree Group Steiner Problem

Preliminary 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.

LP-relaxations for Tree Augmentation

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.

A simplified 1.5-approximation algorithm for

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.

Improved Approximation Algorithm for Steiner kForest with Uniform Weights

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.

On the Fixed Cost kFlow Problem and related

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.

Steiner Forest Orientation Problems

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.

On some network design problems with degree constrains

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.

Prize-Collecting Steiner Network Problems

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.

Approximating Fault-Tolerant Group-Steiner Problems

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.

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

G. Kortsarz and Z. Nutov,

Approximating some network design problems with node costs,

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

Approximating some network design problems with node costs

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.

Improved Approximation Algorithms for Directed Steiner Forest

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.

Approximating Buy-at-Bulk and Shallow-light k-Steiner trees

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,

A 1.8 Approximation Algorithm for Augmenting

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.

Approximating Minimum-Power Degree and Connectivity Problems

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

Two-stage Robust Network Design with Exponential Scenarios

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

Approximation Algorithms for Network Design Problems

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.

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design ∗

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.

Tight Approximation Algorithm for Connectivity

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

Power Optimization for Connectivity Problems

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.

Approximating k-node connected subgraphs via critical graphs

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

Integrality ratio for Group Steiner Trees and Directed Steiner Trees∗

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

A greedy approximation algorithm for the group Steiner problem

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.

Hardness of approximation for vertex-connectivity network design problems

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.

On network design fixed charge flows and the covering Steiner problem

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.

Approximating small vertex connectivity problems via Set-Covers

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.

Approximating the Weight of Shallow Steiner Trees

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

of best papers in Discrete Applied Math, in 1999.

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.

Approximating Spanners and Directed Steiner Forest Upper and Lower Bounds

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

Label Cover instances with large girth and the

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.

On the hardness of approximating spanners

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.

Generating low-degree 2-spanners

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.

Generating sparse 2-spanners

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.

Approximating activation edge-cover and facility location problems

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.

Improved approximation algorithms for minimum power covering problems

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.

Low-Risk Mechanism for Kidney Exchange Game

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

Approximation for source location and the star SNDP problem

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

On edge expansion problems and the small set expansion conjecture

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

Approximation Algorithms for Movement Repairman

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.

The Red-Blue Median Problem and its Generalization

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

A note on two source location problems

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.

Tight lower bounds for the asymmetric k-center problem

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.

An improved approximation algorithm for vertex cover with hard capacities

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.

Generalized submodular cover problems and applications

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.

How to allocate network centers

**Graph Partitioning Problems ****and Scheduling Problems**

Approximations and Hardness of Covering and

Packing Partially Ordered Items

Ilan Doron-Arad, Guy Kortsarz, Joseph(Seffi) Naor, Baruch Schieber, and Hadas Shachnai

Workshop on Graph Algorithms (WG) 2024, to appear

RuleCashing

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

The Densest k-Subhypergraph Problem

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

Bicovering Covering the edges with two small subsets of vertices

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

Matroid Secretary for Regular and Decomposable Matroids

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)

On a local protocol for Concurrent File transfers

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

Approximating Maximum Subgraphs Without Short Cycles

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.

Min Sum Edge Coloring in General Multigraphs via Configuration LP

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.

A lower bound for approximating Grundy numbering

No conference version

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

S. Sivasubramanian.

Complete Partitions of Graphs.

Combinatorica, 27(5):2008

Complete Partitions of Graphs

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.

Improved Bounds for Sum Multicoloring and Weighted CompletionTime of Dependent Jobs

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

Multicoloring Problems and Techniques, a survey

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.

Improved results for data migration and open-shop scheduling

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

The minimum shift design problem theory and practice

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

A Hybrid Network Flow Tabu Search Heuristic for the MinimumShift Design Problem

G. Kortsarz and S. Shende.

Approximating the achromatic number problem on bipartite graphs.

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

Approximating the achromatic number problem on bipartite graphs

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

Sum coloring interval graphs and k-claw free graphs withapplications for scheduling dependent jobs,

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

On the approximation of the achromatic number

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.

Approximating the domatic number.

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.

Tools for Multicoloring

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.

Sum Multicoloring Trees.

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.

Minimum Sum Multicoloring of Graphs

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 Matched Approximation Bound for the Sum of a Greedy Coloring

A. Bar-Noy and G. Kortsarz.

The minimum color-sum of bipartite graphs.

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

The minimum color-sum of bipartite graphs

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.

The Dense k-subgraph problem

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.

Traffic light scheduling on the grid

Preliminary version in the 6th International

Workshop on Distributed Algorithms (WDAG),

pp 238-252, 1992.

**Broadcasting Problems**

Daniel Hathcock, Guy Kortsarz, R. Ravi, The Telephone k-multicast problem, APPROX 2024, to appear

The Telephone k-multicast problem

M. M Halldorsson, G. Kortsarz, P. Mitra and T. Tonoyan.

Spanning Trees With Edge Conflicts and Wireless Connectivity.

Algorithmica. 83(11): 3469-3490, 2021

Spanning Trees With Edge Conflicts and Wireless Connectivity

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.

Approximating radio aggregation

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

An improved broadcast schedule for radio networks

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.

A sublogarithmic approximation algorithm

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

An approximation algorithm for the directed telephone multicast problem

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

Polylogarithmic additive inapproximability

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.

Combinatorial logarithmic

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

Polylogarithmic additive inapproximability

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

A logarithmic lower bound for radio broadcast

G. Kortsarz and D. Peleg.

Approximation algorithms for

minimum time broadcast,

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

Approximation algorithms

Preliminary version in the Israeli

conference on algorithms (ISTCS) 1992: 67-78

Cut Problems

Cut Problems

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

K. Sarpatwar. The tree with maximum profit on the leaves problem

and connections to Connected Max Cut Problems, IPL, 29: 31-34, 2020.

The tree with maximum profit on the leaves problem

Hajiaghayi, Kortsarz MacDavid, Purohit, and Sarpatwar.

Approximating the Connected Max Cut Problem.

Theoretical Computer Science, 74-85, 2020.

Approximating the Connected Max Cut Problem

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.

The checkpoint problem

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.

On the advantage of overlap clustering for minimizing the conductance

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.

Greedy Approximation algorithm for directed multicuts

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.

Approximating the Minimal Sensor Selection for Supervisory Control

Preliminary version in the seventh

Workshop on Discrete Event Systems (WODES), 2004

Fix Parameter Tractability

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.

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.

Tight boubnds for subexonentialapproximation for Set Cover

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)

A Tight Algorithm for Strongly ConnectedSteiner Subgraph On Two Terminals With Demands

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

Fixed Parameter and approximation algorithms a new look

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.