Skip to main content

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

 

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

 

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.