{"id":363,"date":"2020-07-09T16:51:59","date_gmt":"2020-07-09T16:51:59","guid":{"rendered":"http:\/\/sites.rutgers.edu\/guy-kortsarz\/?page_id=363"},"modified":"2024-07-01T18:46:37","modified_gmt":"2024-07-01T18:46:37","slug":"publications","status":"publish","type":"page","link":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/","title":{"rendered":"Publications"},"content":{"rendered":"

Remark: Most of the papers here are published.
\nThe copyrights\u00a0have been transferred to the respective publishers.
\nPlease respect this.
\nPapers are divided into topics.
\nIn every topic the publications are in reverse\u00a0chronological order<\/p>\n

<\/h4>\n

 <\/p>\n

Survey Chapters in Books<\/strong><\/h4>\n

 <\/p>\n

Magnus M. Halldorsson and G. Kortsarz,
\nAlgorithms for Chromatic Sums, Multicoloring,
\nand Scheduling Dependent Jobs,
\nSurvey Chapter in Approximation
\nAlgorithms and Metaheuristics,
\nedited by Teo Gonzalez, 2017.
\nAlgorithms for Chromatic Sums, Multicoloring, and Scheduling Dependent Jobs<\/a><\/p>\n

Guy Kortsarz
\nFixed parameter approximability and hardness,
\nEncyclopedia of algorithms, 2015.
\nFixed parameter approximability and hardness<\/a><\/p>\n

G. Kortsarz and Z. Nutov,
\nApproximating min-cost connectivity
\nproblems,
\nSurvey Chapter in Approximation
\nAlgorithms and Metaheuristics, edited by Teo Gonzalez, 2006.
\nApproximatingmMin-costConnectivitySurveyChapter<\/a><\/p>\n

To keep the survey updated,
\nZeev Nutov maintains a file that
\ndiscusses new results.
\nChapterSurveyUpdates<\/a><\/p>\n

<\/h4>\n

 <\/p>\n

Network Design<\/strong><\/h4>\n

Michael Dinitz, Guy Kortsarz, Shi Li, Degrees and Network Design: New Problems and Approximations, APPROX 2024 to appear
\nDegrees and Network Design New Problems and Approximations<\/a><\/p>\n

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
\nImprovedApproximationsforRelativeSurvivableNetworkDesign<\/a><\/p>\n

Michael Dinitz, Ama Koranteng, Guy Kortsarz,
\nRelative Survivable Network Design
\nAPPROX\/RANDOM 2022, pages 41:1-41:19
\nRelative Survivable Network Design<\/a><\/p>\n

X. Guo, G. Kortsarz, B Laekhanukit, S. Li and D. Vaz J,
\nBounded Degree Steiner Tree and Bounded Degree Group Steiner tree.
\nAlgorithmica, 84(5): 1252-1278 2022.
\nOn Approximating Degree-Bounded Network Design Problems<\/a>
\nPreliminary version in
\nRANDOM-APPROX, pages 39:1-39:24, 2020<\/p>\n

Guy Kortsarz and Zeev Nutov.
\nBounded-Degree Group Steiner problems,
\nDiscrete Applied Math, 2022, 309: 229-239, 2022
\nThe minimum Degree Group Steiner Problem<\/a>
\nPreliminary version in
\n31st International Workshop on Combinatorial Algorithms
\n(IWOCA), pages 243 254, 2020.<\/p>\n

G. Kortsarz and N. Nutov.
\nAn LP with 7\/4 integrality gap for the tree augmentation problems.
\nDiscrete Applied Math, 239:94-105, 2018.
\nLP-relaxations for Tree Augmentation<\/a>
\nPreliminary version in APPROX-RANDOM, pages 13:1-13:16, 2016.<\/p>\n

G. Kortsarz and Z. Nutov
\nA simplified 3\/2 ratio approximation algorithm
\nfor the tree augmentation problem.
\nTransaction on Algorithm, 12(2):23, 2016.
\nA simplified 1.5-approximation algorithm for<\/a>
\nPreliminary version in
\nGuy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov.
\nA 3\/2-Approximation Algorithm for Augmenting the
\nEdge-Connectivity of a Graph from 1 to 2
\nUsing a Subset of a Given Edge Set.
\nRANDOM-APPROX 2001: 90-101<\/p>\n

M Dinitz, G. Kortsarz and Z. Nutov.
\nApproximating the Steiner k-Forest problem
\nwith nearly uniform weights.
\nTransaction of algorithms, 13(3): 40:1-40:16, 2017.
\nImproved Approximation Algorithm for Steiner kForest with Uniform Weights<\/a>
\nPreliminary version in RANDOM-APPROX 2014, 115–127.<\/p>\n

M. Hajiaghayi, R. Khandekar, G, Kortsarz, and Z. Nutov
\nApproximation fixed cost k-flow problems.
\nTheory Comput. Syst. 58(1): 4-18 (2016)
\nSpecial issue for papers selected from WAOA 2014.
\nOn the Fixed Cost kFlow Problem and related<\/a>
\nPreliminary version in
\nWorkshop on Approximation and Online Algorithms (WAOA),
\npages 49-60, 2013.<\/p>\n

M. Cygan, G. Kortsarz and Z.Nutov.
\nSteiner Forest Orientation Problems.
\nSiam Journal on Discrete Math, 27(3):1503–1513, 2013.
\nSteiner Forest Orientation Problems<\/a>
\nPreliminary version in ESA, pages 361-372, 2012.<\/p>\n

G. Kortsarz R. Khandekar and Zeev Nutov.
\nApproximating some network design problem with degree constrains.
\nJournal of Computing and Sciences (JCSS), 79(5)725-736. 2012.
\nOn some network design problems with degree constrains<\/a>
\nPreliminary version in RANDOM-APPROX, pages 289-301, 2011.<\/p>\n

M. Hajiaghayi and R. Khandekar and G. Kortsarz and Z. Nutov,
\nPrize collection Steiner Network Problem and extensions,
\nACM Transactions on Algorithms, Vol. 9, No. 1, Article 2. 2011.
\nPrize-Collecting Steiner Network Problems<\/a>
\nPreliminary version in IPCO, pp 71-84, 2010.<\/p>\n

R. Khandekar and G. Kortsarz and Z. Nutov,
\nThe fault-tolerant group Steiner problem,
\nTheoretical Computer Science, 416(27):55-64, January 2012.
\nApproximating Fault-Tolerant Group-Steiner Problems<\/a>
\nPreliminary version in:
\nFSTTCS, pp 263-274, December 2009<\/p>\n

G.Kortsarz and Z. Nutov.
\nApproximating Minimum-Power Edge-Covers and 2,3-Connectivity,
\nproblems
\nDiscrete Applied Math, 157(8):1840-1847, April 2009.
\nApproximating Minimum-Power Edge-Covers and 2, 3-Connectivity<\/a><\/p>\n

G. Kortsarz and Z. Nutov,
\nApproximating some network design problems with node costs,
\nTheor. Comput. Sci. 412(35): 4482-4492 2011.
\nApproximating some network design problems with node costs<\/a>
\nPreliminary version in:
\nRANDOM-APPROX 2009, pp 231-244.<\/p>\n

M. Feldman and G. Kortsarz and Z. Nutov,
\nImproved approximation for the directed Steiner forest problem,
\nJCSS,
\n78(1):279-292.
\nImproved Approximation Algorithms for Directed Steiner Forest<\/a>
\nPreliminary version in SODA 2009, pages 922-931<\/p>\n

M. Hajiaghayi, G. Kortsarz, M. Salavatipour.
\nApproximating k Shallow-light trees
\nand buy at bulk k-Steiner trees,
\nAlgorithmica, 51(3):89-103,2009.
\nApproximating Buy-at-Bulk and Shallow-light k-Steiner trees<\/a>
\nPreliminary version in
\nRANDOM-APPROX, pp 152-163, 2006.<\/p>\n

G. Even, John Feldman, G. Kortsarz and
\nZ. Nutov,
\nA 1.8-approximation for augmenting a connected graph into a two-connected graph,
\nA 1.8 Approximation Algorithm for Augmenting<\/a>
\nTransaction on Algorithms, volume 5, number 2, 2009<\/p>\n

G. Even, G. Kortsarz and
\nZ. Nutov,
\nA 1.5-approximation for
\naugmenting a connected graph into a two-connected graph,
\nInf. Process. Lett. 111(6):296-300, 2011
\nPreliminary version, RANDOM-APPROX 2001, pp 90-101
\nThis paper has a mistaken definition.
\nA full correct version appeared only in 2016 in TALG<\/p>\n

G. Kortsarz and V. Mirrokni and Z. Nutov and E. Tsanko.
\nApproximating min-power connectivity problems,
\nAlgorithmica, volume 60(4):735–742,
\nMay 2011.
\nApproximating Minimum-Power Degree and Connectivity Problems<\/a>
\nA preliminary version appeared in LATIN, pp 423-435, 2008<\/p>\n

R. Khandekar and G. Kortsarz and
\nV. Mirrokni and M. Salavatipour,
\nApproximation and hardness results for Robust Network design with
\nexponential Scenarios, Algorithmica, 63(4): 795-814, January 2013
\nTwo-stage Robust Network Design with Exponential Scenarios<\/a>
\nPreliminary version in ESA, pp 589-600, 2008.<\/p>\n

C. Chekuri, M. Hajiaghayi, G. Kortsarz, M. Salavatipour.
\nApproximation Algorithms for node weighted
\nbuy at bulk network design,
\nSODA 2007, pp 1265-1274
\nApproximation Algorithms for Network Design Problems<\/a>
\nRemark: This paper has no journal version
\n(Merged with the FOCS 2006 paper)<\/p>\n

C. Chekuri, M. Hajiaghayi, G. Kortsarz, M. Salavatipour.
\nPolylogarithmic approximation algorithm
\nfor non-uniform multicommodity buy at bulk,
\nSIAM Journal on computation 39(5):1772-1798. January 2010.
\nApproximation Algorithms for Non-Uniform Buy-at-Bulk Network Design \u2217<\/a>
\nPreliminary version in FOCS pp 677-686 2006.
\nRemark: contains the vertex version of the problem as well.<\/p>\n

G. Kortsarz and Z. Nutov.
\nTight bounds for connectivity augmentation
\nproblems,
\nJournal of Computing and System Sciences, 74:662-670. 2008.
\nTight Approximation Algorithm for Connectivity<\/a>
\nPreliminary version in ICALP 2006, pp 443–452.<\/p>\n

M. Hajiaghayi, G. Kortsarz, V. Mirrokni and Z. Nutov,
\nPower optimization for connectivity problems.
\nMath. Prog. B. (special issue of papers selected from IPCO 2005),
\nvolume 110(1):195-208. 2007
\nPower Optimization for Connectivity Problems<\/a>
\nPreliminary version in:
\nInteger Programming & Combinatorial Optimization
\n(IPCO) pp 349-361. 2005<\/p>\n

G. Kortsarz and Z. Nutov,
\nApproximation Algorithms for k-node connected subgraphs, via
\ncritical graphs,
\nSIAM journal on Computing, volume 35(1):247-257, 2005.
\nApproximating k-node connected subgraphs via critical graphs<\/a>
\nPreliminary version in:
\nSTOC 138–145. 2004<\/p>\n

E. Halperin, G. Kortsarz, R. Krauthgamer,
\nA. Srinivasan and N. Wang,
\nIntegrality ratio for Group Steiner
\nTrees and Directed Steiner Trees,
\nSIAM Journal on Computing,
\n36(5) :(1494-1511), 2007
\nIntegrality ratio for Group Steiner Trees and Directed Steiner Trees\u2217<\/a>
\nPreliminary version in:
\nSODA, pp 275-284, 2003.<\/p>\n

C. Chekuri, G. Even, G. Kortsarz.
\nA combinatorial approximation algorithm for the Group Steiner problem.
\nDiscrete Applied Math, volume 154(1):15-34, 2005
\nA greedy approximation algorithm for the group Steiner problem<\/a>
\nThe above journal version corrects the conference version in:
\nSODA 2002. pp. 49–58.<\/p>\n

G. Kortsarz, R. Krauthgamer, J. Lee,
\nOn the hardness of approximating vertex connectivity network design problems.
\nSIAM J. on Computing, 33(3):704–720, 2003.
\nHardness of approximation for vertex-connectivity network design problems<\/a>
\nPreliminary version in RANDOM-APPROX 2002, pp 185-199.<\/p>\n

G. Even, G. Kortsarz and W. Slany,
\nOn network design: fixed charge flows and the covering
\nSteiner problem.
\nTransaction on Algorithms, 1(1):74-101, 2005.
\nOn network design fixed charge flows and the covering Steiner problem<\/a>
\nPreliminary version in
\nScandinavian Symposium on Approximation Algorithms (SWAT),
\npp 318-329, 2002.<\/p>\n

G. Kortsarz and Z. Nutov,
\nApproximating small vertex connectivity problems via Set-Covers.
\nAlgorithmica, 37:75–92, 2003.
\nApproximating small vertex connectivity problems via Set-Covers<\/a>
\nPreliminary version in the Third International Workshop RANDOM-APPROX
\npp 194–205, 2000.<\/p>\n

G. Kortsarz and D. Peleg,
\nApproximating the Weight of Shallow Steiner Trees,
\nDiscrete Applied Math, vol 93:265-285, 1999.
\nApproximating the Weight of Shallow Steiner Trees<\/a>
\nRemark: This paper was chosen into a special edition of Editors choice
\nof best papers in Discrete Applied Math, in 1999.<\/p>\n

Preliminary version in Symposium on discrete algorithms (SODA),
\npp 103-110, 1997.<\/p>\n

<\/h3>\n

 <\/p>\n

Spanner Problems<\/strong><\/h4>\n

 <\/p>\n

E. Chlamtac, M. Dinitz, G. Kortsarz and B. Laekhanukit,
\nApproximating Spanners and Directed Steiner Forest:
\nUpper and Lower Bounds.
\nACM Transactions on Algorithms June 2020.
\nApproximating Spanners and Directed Steiner Forest Upper and Lower Bounds<\/a>
\nPreliminary version in SODA, pages 534-553 2017.<\/p>\n

M Dinitz, G. Kortsarz and R. Raz
\nLabel Cover instances with large girth and the
\nhardness of approximating spanners. Transaction on Algorithms, 12(2):25 2016
\nLabel Cover instances with large girth and the<\/a>
\nPreliminary version in ICALP pages 290-301. 2012.<\/p>\n

G. Kortsarz. On the hardness of approximating spanners,
\nAlgorithmica, special issue of papers selected from APPROX-98, 30(3):432-450, 2001.
\nOn the hardness of approximating spanners<\/a>
\nPreliminary version in APPROX 1998, 135-146<\/p>\n

D. Handke and G. Kortsarz.
\nThe Steiner Tree-Spanner problem and related tree-covering problems.
\nThe 26th International Workshop on Graph-Theoretic Concepts in
\nComputer Science (WG) 2000.
\nRemark: this paper has no journal version.<\/p>\n

G. Kortsarz and D. Peleg.
\nGenerating low-degree 2-spanners,
\nSIAM journal on computing, 27(5):1438-1456, 1998.
\nGenerating low-degree 2-spanners<\/a>
\nPreliminary version in Symposium on discrete algorithms (SODA),
\npp 556-563, 1994.<\/p>\n

G. Kortsarz and D. Peleg.
\nGenerating sparse 2-spanners,
\nJournal of algorithms, 17:222-236, 1994.
\nGenerating sparse 2-spanners<\/a>
\nPreliminary version in Proc. 3rd Scandinavian
\nWorkshop on Algorithm Theory (SWAT),
\npp 73-82, 1992.<\/p>\n

<\/h3>\n

 <\/p>\n

Facility Location<\/strong><\/h4>\n

 <\/p>\n

Zeev Nutov, Guy Kortsarz and Eli Shalom.
\nApproximating activation edge-cover and facility location problems.
\nTheoretical Computer Science
\nto appear.
\nApproximating activation edge-cover and facility location problems<\/a>
\nPreliminary version in MFCS, pages 20:1-20:14, 2019.<\/p>\n

Gruia Calinescu, Guy Kortsarz and Zeev Nutov
\nImproved approximation algorithms for minimum power covering problems
\nTheoretical Computer Science. 795: 785-300, 2019.
\nImproved approximation algorithms for minimum power covering problems<\/a>
\nPerliminary version in
\nWorkshop on Approximation and On-Line algorithms (WAOA),
\nPages 134-148, 2018.<\/p>\n

Hossein Esfandiar and G. Kortsarz.
\nLow-Risk Mechanism for Kidney Exchange Game,
\nDiscrete Applied Math, 243:6-53, 2018.
\nLow-Risk Mechanism for Kidney Exchange Game<\/a>
\nPreliminary version in LATIN, Pages 416-428, 2016
\nAlso Symposium
\non Algorithmic Game Theory (SAGT), pages 303-304 2016.<\/p>\n

G. Kortsarz and Z. Nutov.
\nApproximation for source location and the star SNDP problem.
\nTheor. Comput. Sci. 674: 32-42, 2017
\nApproximation for source location and the star SNDP problem<\/a>
\nPreliminary version in:
\nWorkshop on Graph theoretic concepts in computer science (WG)
\n203-218, 2015.<\/p>\n

Rajiv Gandhi and Guy Kortsarz,
\nOn edge expansion problems and the small set expansion conjecture.
\nDiscrete Applied Math. 194: 93-101, 2015
\nOn edge expansion problems and the small set expansion conjecture<\/a>
\nPreliminary version in:
\nWorkshop on Graph theory (WG) 2014,
\npages 189-200 2014.<\/p>\n

Approximation Algorithms for Movement Repairman,
\nM. Hajiaghayi, Rohit Khandekar, M.R Khani and G. Kortsarz
\nTALG 12(4): 54, 2016
\nApproximation Algorithms for Movement Repairman<\/a>
\nPreliminary version in RANDOM-APPROX 2013, pages 218–232, 2013.<\/p>\n

M. Hajiaghayi, R. Khandekar and G. Kortsarz,
\nThe Red-Blue Median Problem and its Generalization,
\nAlgorithmica volume 68 number 4, pages 795-814, 2012.
\nSpecial issue of papers selected of
\nESA 2010.
\nThe Red-Blue Median Problem and its Generalization<\/a>
\nPreliminary version in:
\nESA, 314-325, 2010.<\/p>\n

Guy Kortsarz and Zeev Nutov,
\nA note on two source location problems
\nJournal on discrete algorithms,
\n6:520-525, 2008
\nA note on two source location problems<\/a><\/p>\n

J. Chuzhoy and S. Guha and E. Halperin and S. Khanna and
\nG. Kortsarz and R. Krauthgamer and S. Naor.
\nTight lower bounds for the asymmetric k-center problem.
\nJournal of Association Computing Machinery,
\n52(4):538-551, 2005.
\nTight lower bounds for the asymmetric k-center problem<\/a>
\nPreliminary version in STOC 2004, pp 21–27<\/p>\n

R. Gandhi and E. Halperin and S. Khuller and G. Kortsarz and A. Srinivasan.
\nAn improved approximation algorithm for vertex cover with hard capacities,
\nJournal of Computing and System Sciences, pp 16-33, 2006.
\nAn improved approximation algorithm for vertex cover with hard capacities<\/a>
\nPreliminary version in the thirtieth International Colloquium on
\nAutomata, Languages and computing
\n(ICALP) pp 164-175 2003.<\/p>\n

J. Bar-Ilan, G. Kortsarz and D. Peleg,
\nGeneralized submodular cover problems and applications,
\nTheoretical Computer Science, 250:179-200, 2001.
\nGeneralized submodular cover problems and applications<\/a>
\nPreliminary version in the Israeli Symp. on the Theory of
\nComputing and System
\n(ISTCS), pp 110-118, 1996.<\/p>\n

J. Bar-Ilan, G. Kortsarz and D. Peleg.
\nInformation Center Allocation,
\nThe Electronic Library, 12:361-365, 1994.<\/p>\n

J. Bar-Ilan, G. Kortsarz and D. Peleg.
\nHow to allocate network centers,
\nJ. of Algorithms, 15:385-415, 1993.
\nHow to allocate network centers<\/a><\/p>\n

<\/h4>\n

 <\/p>\n

Graph Partitioning Problems <\/strong>and Scheduling Problems<\/strong><\/h4>\n

Approximations and Hardness of Covering and
\nPacking Partially Ordered Items
\nIlan Doron-Arad, Guy Kortsarz, Joseph(Seffi) Naor, Baruch Schieber, and Hadas Shachnai
\nWorkshop on Graph Algorithms (WG) 2024, to appear
\nRuleCashing<\/a><\/p>\n

E. Chlamtac, M. Dinitz, C. Konrad
\nG. Kortsarz and G. Rabanca
\nThe Densest k-Subhypergraph Problem
\nSIAM Journal on Discrete Math, 239: 94-105, 2018
\nThe Densest k-Subhypergraph Problem<\/a>
\nPreliminary version in RANDOM-APPROX, 6:1-6:19. 2016.<\/p>\n

A. Bhangale, R. Gandhi, M Hajiaghayi, R. Khandekar, G Kortsarz.
\nBicovering: Covering the
\nedges with two small subsets of vertices
\nSIAM Journal on Discrete Math, 31(4): 2626-2646, 2017
\nBicovering Covering the edges with two small subsets of vertices<\/a>
\nPreliminary version in ICALP, pages, 601-612, 2016.<\/p>\n

Michael Dinitz and Guy Kortsarz,
\nMatroid Secretary for Regular and Decomposable Matroids,
\nSIAM Journal on Computing, 43(5):1807-1830, 2014
\nMatroid Secretary for Regular and Decomposable Matroids<\/a>
\nPreliminary version in SODA, pages 108–117, 2013.<\/p>\n

M. Hajiaghayi and R. Khandekar and G. Kortsarz and V. Liaghat,
\nOn a local protocol for Concurrent File transfers,
\nTheory of Computing. Special issue
\nof papers selected from SPAA 2011.
\n55(3): 613-636 (2014)
\nOn a local protocol for Concurrent File transfers<\/a>
\nPreliminary version on:
\n23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
\npp 269–278, June 2011..<\/p>\n

G. Kortsarz, M. Landberg and Z. Nutov,
\nApproximating Maximum Subgraphs Without Short
\nCycles. SIAM J. Discrete Math. 24(1):255-269, 2010
\nApproximating Maximum Subgraphs Without Short Cycles<\/a>
\nPreliminary version in RANDOM-APPROX, pp 118-131, 2008.<\/p>\n

M. Halldorsson, G. Kortsarz and M. Sviridenko.
\nMin Sum Edge Coloring in General Multigraphs via Configuration LP,
\nTransaction on algorithms, 7(2):22-, March 2011.
\nMin Sum Edge Coloring in General Multigraphs via Configuration LP<\/a>
\nPreliminary version in
\nIPCO, pp 359-373, 2008.<\/p>\n

G. Kortsarz. A lower bound for approximating Grundy numbering,
\nDiscrete Mathematics and Theoretical Computer Science (DMTCS).
\n9(1):7-22. 2006.
\nA lower bound for approximating Grundy numbering<\/a>
\nNo conference version<\/p>\n

M. M. Halldorsson, G. Kortsarz, J. Radhakrishnan and
\nS. Sivasubramanian.
\nComplete Partitions of Graphs.
\nCombinatorica, 27(5):2008
\nComplete Partitions of Graphs<\/a>
\nPreliminary version in Symposium on Discrete Algorithms
\n(SODA), pp 860-869. 2005.<\/p>\n

R. Gandhi, M. Halldorsson and G. Kortsarz and H. Shachnai.
\nImproved Bounds for Sum Multicoloring and Weighted Completion
\nTime of Dependent Jobs,
\nTransaction on Algorithm, 4(1), 2008.
\nImproved Bounds for Sum Multicoloring and Weighted CompletionTime of Dependent Jobs<\/a>
\nPreliminary version in second Workshop on Approximation and
\nOnline Algorithms (WAOA), pp 68-82, 2004.<\/p>\n

M. Halldorsson and G. Kortsarz,
\nMulticoloring: Problems and Techniques, a survey.
\nMathematical foundation of computer science
\n(MFCS), pp 25-41. 2004. Invited Talk
\nMulticoloring Problems and Techniques, a survey<\/a><\/p>\n

R. Gandhi, M. Halldorsson and G. Kortsarz and H. Shachnai,
\nImproved results for data migration and open-shop scheduling.
\nTransaction on Algorithms, 2(1):116-129, 2006.
\nImproved results for data migration and open-shop scheduling<\/a>
\nPreliminary version in Symposium on Automata, Languages
\nand Programming (ICALP) pp 658-669. 2004.
\nRemark: the above is not the original journal paper.
\nSviridenko found a mistake and we corrected it
\nand improved the ratio in the process.
\nThe above PDF is a self contained description
\nof the technical details.<\/p>\n

L. D. Gaspero and J. Ga”rtner and
\nG. Kortsarz and N. Musliu
\nand A. Schaerf and W. Slany,
\nThe minimum shift design problem: theory and practice.
\nAnnals on Operations Research
\n(special Volume on “Personnel Scheduling and Planning”),
\n155(1):119-142 2006
\nThe minimum shift design problem theory and practice<\/a>
\nPreliminary version in the European Symposium on Algorithms
\n(ESA) 2003, pp 593–604. 2004<\/p>\n

L. D. Gaspero, J. Gartner,
\nG. Kortsarz, N. Musliu,
\nA. Schaerf and W. Slany,
\nA Hybrid Network Flow Tabu Search Heuristic for the Minimum
\nShift Design Problem.
\nIn the fifth Metahueristics International Conference, Kyoto, Japan, 2003 (no journal version).
\nA Hybrid Network Flow Tabu Search Heuristic for the MinimumShift Design Problem<\/a><\/p>\n

G. Kortsarz and S. Shende.
\nApproximating the achromatic number problem on bipartite graphs.
\nSIAM Journal on Discrete Math, 21(2):361-373. 2005
\nApproximating the achromatic number problem on bipartite graphs<\/a>
\nPreliminary version in the European Symposium on
\nAlgorithms (ESA) 2003, pp 385–396.<\/p>\n

M. Halldorsson and G. Kortsarz and H. Shachnai,
\nSum coloring interval graphs and k-claw free graphs with
\napplications for scheduling dependent jobs,
\nAlgorithmica, 37:187-209. 2003
\nSum coloring interval graphs and k-claw free graphs withapplications for scheduling dependent jobs,<\/a>
\nPreliminary version in RANDOM-APPROX 114–126. 2001<\/p>\n

G. Kortsarz and R. Krauthgamer,
\nOn the approximation of the achromatic number.
\nSiam Journal of discrete methods, vol 14, No. 3, pp: 408–422, 2001
\nOn the approximation of the achromatic number<\/a>
\nPreliminary version in the Symposium on discrete algorithms
\n(SODA) pp 309–318 2001.<\/p>\n

U. Feige, M. Halldorsson, G. Kortsarz and A. Srinivasan.
\nApproximating the domatic number.
\nSiam journal on computing 32(1), 172–195, 2002.
\nApproximating the domatic number.<\/a>
\nPreliminary version in the
\nThirty Second Symposium on the Theory of Computer Science
\n(STOC), 134–143, 2000.<\/p>\n

M. Halldorsson and G. Kortsarz.
\nTools for Multicoloring with
\napplications to Planar Graphs and Partial k-trees.
\nJ. of Algorithms, 42,334-366, 2002.
\nTools for Multicoloring<\/a>
\nPreliminary version in the second International
\nRANDOM-APPROX pp 73-84, 1999.<\/p>\n

M. Halldorsson, G. Kortsarz, A. Proskurowski,
\nR. Salman, H. Shachnai and J. A. Telle.
\nSum Multicoloring Trees.
\nInformation and computing, vol. 180, 113–129, 2003.
\nSum Multicoloring Trees.<\/a>
\nPreliminary version in the Fifth Annual International
\nComputing and Combinatorics Conference
\n(COCOON), pp 171-180, 1999.<\/p>\n

A. Bar-Noy, M. Halldorsson, G. Kortsarz,
\nR. Salman and H. Shachnai,
\nMinimum Sum Multicoloring of Graphs.
\nJ. of Algorithms, 37(2):422-450, 2000.
\nMinimum Sum Multicoloring of Graphs<\/a>
\nPreliminary version in the European Symposium
\non Algorithms, 1999 (ESA), pp 390-401, 1999.<\/p>\n

A. Bar-Noy, M. Halldorsson, G. Kortsarz,
\nA Matched Approximation Bound for the Sum of a Greedy Coloring,
\nInformation Processing letters, vol 71, 1999, pp 135-140.
\nA Matched Approximation Bound for the Sum of a Greedy Coloring<\/a><\/p>\n

A. Bar-Noy and G. Kortsarz.
\nThe minimum color-sum of bipartite graphs.
\nJ. of Algorithms, vol 28, no. 2, pp 339-365, 1998.
\nThe minimum color-sum of bipartite graphs<\/a>
\nPreliminary version in Symposium on Automata,
\nLanguages and Programming (ICALP),
\npp 738-748, 1997.<\/p>\n

U. Feige, G. Kortsarz and D. Peleg.
\nThe Dense k-subgraph problem,
\nAlgorithmica, 29(3): 410-421, 2001.
\nThe Dense k-subgraph problem<\/a>
\nPreliminary version in the Proc. 34-th IEEE Symp. on
\nFoundations of Computer Science
\n(FOCS), pp 692-701, 1993.<\/p>\n

G. Kortsarz and D. Peleg.
\nTraffic light scheduling on the grid,
\nDiscrete applied math, vol 53, pp 211-234, 1994.
\nTraffic light scheduling on the grid<\/a>
\nPreliminary version in the 6th International
\nWorkshop on Distributed Algorithms (WDAG),
\npp 238-252, 1992.<\/p>\n

<\/h4>\n

 <\/p>\n

Broadcasting Problems<\/strong><\/h4>\n

Daniel Hathcock, Guy Kortsarz, R. Ravi, The Telephone k-multicast problem, APPROX 2024, to appear
\nThe Telephone k-multicast problem<\/a><\/p>\n

M. M Halldorsson, G. Kortsarz, P. Mitra and T. Tonoyan.
\nSpanning Trees With Edge Conflicts and Wireless Connectivity.
\nAlgorithmica. 83(11): 3469-3490, 2021
\nSpanning Trees With Edge Conflicts and Wireless Connectivity<\/a>
\nPreliminary version in ICALP, pages 158:1-158:15, 2018.<\/p>\n

Approximating radio aggregation
\nTheoretical Computer Science, 840: 143-153, 2020.
\nA special issue of papers
\nselected from ALGOSENSORS 2015 and 2016.
\nApproximating radio aggregation<\/a>
\nPreliminary version in ALGOSENSORS, pages 169-182, 2015.<\/p>\n

M. Elkin and G. Kortsarz.
\nAn improved broadcast schedule for radio networks.
\nTransaction on Algorithms, 3(1), 2007
\nAn improved broadcast schedule for radio networks<\/a>
\nPreliminary version in
\nSODA pp 76-85. 2003.<\/p>\n

M. Elkin and G. Kortsarz. A sublogarithmic approximation algorithm
\nfor undirected telephone multicast
\nJournal of Computing and System Sciences, 72(4):648-659, 2006.
\nA sublogarithmic approximation algorithm<\/a>
\nPreliminary version in
\nSODA, pp 76-85, 2003.<\/p>\n

M. Elkin and G. Kortsarz.
\nAn approximation algorithm for the directed telephone multicast problem.
\nAlgorithmica, volume 45(4)569-583,2006
\nAn approximation algorithm for the directed telephone multicast problem<\/a>
\nPreliminary version in
\n(ICALP) pp 212-223 2003.<\/p>\n

M. Elkin and G. Kortsarz,
\nPolylogarithmic additive inapproximability
\nfor the radio broadcast problem.
\nSiam Journal on Discrete Mathematics,
\n19:881-899 2005
\nPolylogarithmic additive inapproximability<\/a>
\nPreliminary version in
\nRANDOM-APPROX, pp 105–116, 2004<\/p>\n

M. Elkin and G. Kortsarz.
\nCombinatorial logarithmic
\napproximation algorithm for the
\ndirected telephone broadcast
\nproblem.
\nSIAM journal on Computing, 35(3):672–689, 2005.
\nCombinatorial logarithmic<\/a>
\nPreliminary version on
\nSTOC 2002, pp 438–447.<\/p>\n

M. Elkin and G. Kortsarz.
\nPolylogarithmic additive inapproximability of
\nthe radio broadcast problem.
\nSiam Journal on Discrete Mathematics, 19:881-899 2005
\nPolylogarithmic additive inapproximability<\/a>
\nPreliminary version in
\nRANDOM-APPROX 105-116, 2004.<\/p>\n

M. Elkin and G. Kortsarz.
\nA logarithmic lower bound for radio broadcast.
\nJ. Algorithms, 52(1):8-25, 2004
\nA logarithmic lower bound for radio broadcast<\/a><\/p>\n

G. Kortsarz and D. Peleg.
\nApproximation algorithms for
\nminimum time broadcast,
\nSIAM journal on discrete methods, vol 8, pp 401-427, 1995.
\nApproximation algorithms<\/a>
\nPreliminary version in the Israeli
\nconference on algorithms (ISTCS) 1992: 67-78<\/p>\n


\nCut Problems<\/strong><\/h3>\n

 <\/p>\n

R. Gandhi, M .Hajiaghayi, G. Kortsarz, M Purohit, and
\nK. Sarpatwar. The tree with maximum profit on the leaves problem
\nand connections to Connected Max Cut Problems, IPL, 29: 31-34, 2020.
\nThe tree with maximum profit on the leaves problem<\/a><\/p>\n

Hajiaghayi, Kortsarz MacDavid, Purohit, and Sarpatwar.
\nApproximating the Connected Max Cut Problem.
\nTheoretical Computer Science, 74-85, 2020.
\nApproximating the Connected Max Cut Problem<\/a>
\nPreliminary version ESA, pages 693-704 2015.<\/p>\n

M. Hajiaghayi and R. Khandekar and G. Kortsarz and J. Mestre,
\nThe checkpoint problem,
\nTheoretical Computer Science 452:88-99, 2012.
\nThe checkpoint problem<\/a>
\nPreliminary version in RANDOM-APPROX 2010, pages 219-231.<\/p>\n

R. Khandekar and G. Kortsarz and V. Mirrokni,
\nOn the advantage of overlap clustering for minimizing the conductance.
\nAlgorithmica, 69(4):844-863, 2014.
\nOn the advantage of overlap clustering for minimizing the conductance<\/a>
\nPreliminary version in LATIN 2012, 495-505.<\/p>\n

Y. Kortsarts and G. Kortsarz and Z. Nutov,
\nGreedy Approximation algorithm for directed multicuts,
\nNetworks, 45(4):214-217, 2005.
\nGreedy Approximation algorithm for directed multicuts<\/a>
\nPreliminary version in the
\nsecond Workshop on Approximation and Online Algorithms
\n(WAOA), pp 61-67, 2004.<\/p>\n

S. Khuller and G. Kortsarz and K. R. Rohloff.
\nApproximating the Minimal Sensor Selection for Supervisory Control.
\nJournal of Discrete Event Dynamic Systems: Theory and Applications
\n(special issue for papers selected
\nfrom WODES 2004), volume 16, pp 149–178.
\nApproximating the Minimal Sensor Selection for Supervisory Control<\/a>
\nPreliminary version in the seventh
\nWorkshop on Discrete Event Systems (WODES), 2004<\/p>\n

<\/h4>\n


\nFix Parameter Tractability<\/strong><\/h4>\n

 <\/p>\n

P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit,
\nP. Manurangsi and D. Nanogkai and Luva Trevisan.
\nFrom Gap-ETH to FPT-Inapproximability:
\nClique, Dominating Set, and More. SICOMP, 49(4): 772-810 2020.
\nPreliminary version FOCS, pages 743-754, 2017<\/p>\n

M. Cygan, M. Halldorsson and G. Kortsarz
\nTight boubnds for subexonential
\napproximation for Set Cover.
\nWAOA 2020, pages 159-173, 2020.
\nTight boubnds for subexonentialapproximation for Set Cover<\/a>
\nNot submitted to a journal
\nThe conference version has
\nall the details.<\/p>\n

Chitnis, Esfandiari, Hajiaghayi,
\nKhandekar, Kortsarz and Seddighin
\nA Tight Algorithm for Strongly Connected
\nSteiner Subgraph On Two Terminals With Demands
\nAlgorithmica,
\n77(4): 1216-1239 (2017)
\nA Tight Algorithm for Strongly ConnectedSteiner Subgraph On Two Terminals With Demands<\/a>
\nPreliminary version in
\nIPEC 2014, pages 159-171. 2014.<\/p>\n

Rajesh Hemant Chitnis, MohammadTaghi Hajiaghayi, Guy Kortsarz:
\nFixed Parameter and approximation algorithms: a new look.
\nIn IPEC, 110-122, 2013
\nFixed Parameter and approximation algorithms a new look<\/a>
\nThis paper has no journal version.<\/p>\n

M.T. Hajiaghayi and R. Khandekar G. Kortsarz
\nSuper expoential time FPT hardness for Set Cover and Clique.
\nUnpublished Manuscript.
\nThe first paper top prove super exponential time
\nsuper constant hardness for Set Cover and Clique.<\/p>\n","protected":false},"excerpt":{"rendered":"

Remark: Most of the papers here are published. The copyrights\u00a0have been transferred to the respective publishers. Please respect this. Papers are divided into topics. In every topic the publications are … Read More<\/a><\/p>\n","protected":false},"author":21,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"footnotes":""},"class_list":["post-363","page","type-page","status-publish","hentry"],"acf":[],"yoast_head":"\nPublications - Guy Kortsarz<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Publications - Guy Kortsarz\" \/>\n<meta property=\"og:description\" content=\"Remark: Most of the papers here are published. The copyrights\u00a0have been transferred to the respective publishers. Please respect this. Papers are divided into topics. In every topic the publications are … Read More\" \/>\n<meta property=\"og:url\" content=\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/\" \/>\n<meta property=\"og:site_name\" content=\"Guy Kortsarz\" \/>\n<meta property=\"article:modified_time\" content=\"2024-07-01T18:46:37+00:00\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data1\" content=\"18 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"WebPage\",\"@id\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/\",\"url\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/\",\"name\":\"Publications - Guy Kortsarz\",\"isPartOf\":{\"@id\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/#website\"},\"datePublished\":\"2020-07-09T16:51:59+00:00\",\"dateModified\":\"2024-07-01T18:46:37+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Publications\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/#website\",\"url\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/\",\"name\":\"Guy Kortsarz\",\"description\":\"\",\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/sites.rutgers.edu\/guy-kortsarz\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Publications - Guy Kortsarz","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/","og_locale":"en_US","og_type":"article","og_title":"Publications - Guy Kortsarz","og_description":"Remark: Most of the papers here are published. The copyrights\u00a0have been transferred to the respective publishers. Please respect this. Papers are divided into topics. In every topic the publications are … Read More","og_url":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/","og_site_name":"Guy Kortsarz","article_modified_time":"2024-07-01T18:46:37+00:00","twitter_card":"summary_large_image","twitter_misc":{"Est. reading time":"18 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"WebPage","@id":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/","url":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/","name":"Publications - Guy Kortsarz","isPartOf":{"@id":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/#website"},"datePublished":"2020-07-09T16:51:59+00:00","dateModified":"2024-07-01T18:46:37+00:00","breadcrumb":{"@id":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/publications\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/"},{"@type":"ListItem","position":2,"name":"Publications"}]},{"@type":"WebSite","@id":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/#website","url":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/","name":"Guy Kortsarz","description":"","potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"}]}},"_links":{"self":[{"href":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/wp-json\/wp\/v2\/pages\/363"}],"collection":[{"href":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/wp-json\/wp\/v2\/comments?post=363"}],"version-history":[{"count":58,"href":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/wp-json\/wp\/v2\/pages\/363\/revisions"}],"predecessor-version":[{"id":817,"href":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/wp-json\/wp\/v2\/pages\/363\/revisions\/817"}],"wp:attachment":[{"href":"https:\/\/sites.rutgers.edu\/guy-kortsarz\/wp-json\/wp\/v2\/media?parent=363"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}