Magnus M. Halldorsson: Online papers


For work on wireless algorithms, see here.

Most of my recent papers are on arXiv.

Recent Manuscripts

Journal Publications

The following works are the last versions leaving my hands. They may not incorporate corrections made in galley proofs or copyediting. Copyright rests with the respective publisher.
  • Distributed Large Independent Sets in a Single Round
    Distributed Computing (with Christian Konrad), published online March 2017. (Local copy)
  • Max Point-Tolerance Graphs. (with Daniele Catanzaro, Steven Chaplick, Stefan Felsner, Bjarni V. Halld\'orsson, Thomas Hixon, Juraj Stacho) Discrete Applied Mathematics 216(1):84--97, January 2017.
    1. Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems (with Pierre Fraigniaud, Boaz Patt-Shamir, Dror Rawitz, Adi Rosen)
      Algorithmica 74(4): 1205-1223, 2016.
    2. On the complexity of the shortest-path broadcast problem (with Pierluigi Crescenzi, Pierre Fraigniaud, Hovhannes A. Harutyunyan, Chiara Pierucci, Andrea Pietracaprina, Geppino Pucci).
      Discrete Applied Mathematics 199: 101-109, 2016.
    3. Semi-Transitive Orientations and Word-Representable Graphs (with Sergey Kitaev, Artem Pyatkin).
      Discrete Applied Math 201:164-171, 2016. (This version: arXiv:1501.07108 [math.CO], January 2015.)
      (Full (and corrected) version of WG'10 paper)
    4. Streaming Algorithms for Independent Sets
      Algorithmica, 2016 (with Bjarni V. Halldorsson, Elena Losievskja and Mario Szegedy).
    5. ACM DL Author-ize serviceSpace-Constrained Interval Selection
      ACM Transactions on Algorithms (TALG), 2016 (with Yuval Emek, Adi Rosén)
    6. A Note on Vertex Coloring Edge-Weighted Digraphs (with Joergen Bang-Jensen)
      Mittag-Leffler Report No. 29, 2013/2014, spring.
      Information Processing Letters, 115(10):791-796, October 2015.
    7. Online selection of intervals and t-intervals.
      Information and Computation 233:1-11, December 2013 (with Unnar Th. Bachmann and Hadas Shachnai)
    8. Scheduling with interval conflicts
      Theory of Computing Systems 53(2):300-317, August 2013; earlier version appeared in STACS '11 (with Boaz Patt-Shamir, Dror Rawitz).
    9. Approximation and Special Cases of Common Subtrees and Editing Distance.
      Theoretical Computer Science, Jan 2013 (with Tatsyua Akutsu, Daiji Fukagawa, Atsuhiro Takasu, and Keisuke Tanaka).
    10. SDP-based Algorithms for Maximum Independent Set Problems on Hypergraphs.
      Theoretical Computer Science, Jan 2013 (with Geir Agnarsson and Elena Losievskaja).
    11. Online set packing and competitive scheduling of multi-part tasks.
      SICOMP, 41(4):728-746, 2012. (Earlier version appeared in PODC'10). (With Yuval Emek, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan and Dror Rawitz).
    12. ACM DL Author-ize serviceWireless scheduling with power control
      ACM Transactions on Algorithms (TALG), 2012
    13. ACM DL Author-ize serviceSum edge coloring of multigraphs via configuration LP
      ACM Transactions on Algorithms (TALG), 2011 (with Guy Kortsarz, Maxim Sviridenko)
    14. Vertex coloring the square of outerplanar graphs of low degree.
      Discussiones Mathematicae Graph Theory 30(4):619--636, 2010. (with Geir Agnarsson).
    15. Online coloring of hypergraphs.
      Information Processing Letters 110:370--372, 2010.
    16. Approximating Independent Sets in Bounded-Degree Hypergraphs.
      Discrete Applied Mathematics 157 (2009) 1773--1786, 2009 (with Elena Losievskaja).
    17. Approximation algorithms for the weighted independent set problem in sparse graphs.
      Discrete Applied Mathematics, April 2009 (with Akihisa Kako, Takao Ono, and Tomio Hirata)
    18. Scheduling with conflicts: Online and offline algorithms.
      Journal of Scheduling, April 2009 (with Guy Even, Lotem Kaplan, and Dana Ron)
    19. Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
      Algorithmica, Dec 2009 (with Leah Epstein, Asaf Levin, Hadas Shachnai)
    20. Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
      Theoretical Computer Science, 2008 (with Takeshi Tokuyama)
    21. Complete Partitions of Graphs.
      Combinatorica 2007 (with Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian.)
    22. Vertex coloring acyclic digraphs and their corresponding hypergraphs.
      Discrete Applied Mathematics, 2007. (with Geir Agnarsson and Agust Egilsson.)
    23. Strongly Simplicial Vertices of Powers of Trees
      Discrete Mathematics, 2007 (with Geir Agnarsson.)
    24. Scheduling Split Interval Graphs.
      SIAM Journal of Computing, Vol. 36, No. 1, 1--15, 2006 (with Reuven Bar-Yehuda, Seffi Naor, Hadas Shachnai, and Irina Shapira.)
    25. Approximating the $(h,k)$-labelling problem.
      Int. J. Mobile Mobile Network Design and Innovation 1(2):113--117, 2006.
    26. Approximation algorithms for optimization problems in graphs with superlogarithmic treewidth.
      Information Processing Letters 94(2):49-53, 2005 (with Artur Czumaj, Andrzej Lingas, and Johan Nilsson.)
    27. Randomized approximation of the stable marriage problem.
      Theoretical Computer Science 325(3):439-465, 2004 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa.)
    28. Powers of Geometric Intersection Graphs and Dispersion Algorithms
      Discrete Applied Mathematics, 2003 (with Geir Agnarsson, Peter Damaschke.)
    29. Coloring Squares of Graphs.
      SIAM J. Discrete Math, 2003 (with Geir Agnarsson.)
    30. Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.
      Algorithmica, 2003 (with Guy Kortsarz and Hadas Shachnai.)
    31. Approximation algorithms for the minimum test set problem.
      Mathematical Programming-B, 2003 (with Koen M.J. De Bontridder, Bjarni V. Halldórsson, Cor A.J. Hurkens, Jan K. Lenstra, R. Ravi, and Leen Stougie.)
    32. Approximability results for the stable marriage problem with ties.
      Theoretical Computer Science, 2003 (with Robert W. Irving, Kazuo Iwama, David F. Manlove, Shuichi Miyazaki, Yasufumi Morita, and Sandy Scott.)
    33. Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees.
      Journal of Algorithms, 42(2), 334-366, February 2002 (with Guy Kortsarz.)
    34. Online Independent Sets.
      Theoretical Computer Science, 289(2), 953--962, October 2002 (with Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi.)
    35. Approximating the domatic number.
      SIAM Journal of Computing 32(1), 172--195, December 2002 (with Uriel Feige, Guy Kortsarz, and Arvind Srinivasan.)
    36. Multicoloring Trees.
      Information and Computation, Available online 12 December 2002 (with Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, and Jan Arne Telle)
    37. Approximations for the Generalized Block Distribution of a Matrix.
      Theoretical Computer Science 262(1-2), 145--160, July 2001 (with Bengt Aspvall and Fredrik Manne.), PDF
    38. Online coloring known graphs.
      In Electronic J. of Combinatorics Feb 2000.
    39. Mod-2 Independence and Domination in Graphs.
      Discrete Applied Math. Earlier version appears in WG '99, LNCS. (with Jan Kratochvil, Jan Arne Telle.)
    40. Sum Multicoloring of Graphs.
      Journal of Algorithms, Mar 2000.
      Extended abstract appears in ESA '99. (with Amotz Bar-Noy, Guy Kortsarz, Hadas Shachnai, Ravit Salman), PDF
    41. Approximations of Weighted Independent Set and Hereditary Subset Problems.
      Journal of Graphs Algorithms and Applications, Vol.4, No.1, pp.1-16.
    42. Approximation Algorithms for Dispersion Problems.
      Journal of Algorithms, April 2000 (with Barun Chandra.)
    43. Powers of chordal graphs and their coloring.
      Congressus Numerantium, (since Sept 2000) (with Geir Agnarsson, Ray Greenlaw)
    44. Greedy local improvement and weighted set packing approximation.
      Journal of Algorithms, 39(2), 223-240, May 2000. (Abstract , (PDF) (with Barun Chandra)
    45. A matched approximation bound for the sum of a greedy coloring.
      Information Processing Letters 71, 135-140, 1999. (with Amotz Bar-Noy and Guy Kortsarz)
    46. Finding Subsets Maximizing Minimum Structures.
      SIAM Journal of Discrete Math 12(3), 342-359, 1999. (with Kazuo Iwano, Naoki Katoh, and Takeshi Tokuyama.), PDF
    47. On the approximation of largest common point sets and largest common subtrees.
      Theoretical Computer Science 233(1-2), 33-50, 17 Dec 1999. (with Tatsuya Akutsu), PDF
    48. Independent sets with domination constraints.
      Discrete Applied Mathematics, 99(1-3), 39-54, 17 Dec 1999. (with Jan Kratochvíl, Jan Arne Telle.), PDF
    49. On Chromatic Sums and Distributed Resource Allocation.
      Information and Computation 140(2), February 1998 (with Amotz Bar-Noy, Mihir Bellare, Hadas Shachnai, and Tami Tamir) PDF
    50. Approximating Steiner trees in graphs with restricted weights.
      Networks 31(4):283-292, 1998. (with Shuichi Ueno, Hiroshi Nakao, and Yoji Kajitani.), PDF
    51. Greed is good: Approximating independent sets in sparse and bounded-degree graphs.
      Algorithmica 18:143-163 (1997), special issue on on approximation algorithms. (with Jaikumar Radhakrishnan.) PDF
    52. Parallel and online graph coloring.
      Journal of Algorithms, 23:265-280 (1997), PDF
    53. Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring.
      Journal of Graph Algorithms and Applications 1(3):1--13, Nov. 1997 (with Hoong-Chuin Lau.) (See also here)
    54. Lower bounds for on-line graph coloring.
      Theoretical Computer Science 130:163--174, August 1994. (with Mario Szegedy), PDF
    55. Improved approximations of bounded-degree independent sets via subgraph removal.
      In a special issue of Nordic J. Computing, 1(4):475--492, Winter 1994. (with Jaikumar Radhakrishnan.), PDF
      Received the Carl-Erik Fröberg Prize for a young Nordic author of a distinguished paper published in the Nordic Journal of Computing in 1994-1996.
    56. A still better performance guarantee for approximate graph coloring.
      Information Processing Letters, 45:19--23, 25 January 1993, PDF
    57. Approximating the minimum maximal independence number.
      Information Processing Letters, 46:169--172, 25 June 1993. PDF
    58. Approximating the tree and tour covers of a graph.
      Information Processing Letters, 47:275--282, 18 October 1993 (with Estie Arkin and Rafi Hassin), PDF
    59. Approximating maximum independent sets by excluding subgraphs.
      BIT, 32(2):180--196, June 1992 (with Ravi B. Boppana), PDF

    Refereed Conference Publications

    The following are primarily papers that have not been superseded by later versions. For superseded papers, see here.
    1. Distributed Approximation of k-Service Assignment
      OPODIS'15. LIPcs vol. 46, 2016. (with Sven Köhler, Dror Rawitz)
    2. Distributed Large Independent Sets in One Round On Bounded-independence Graphs
      DISC'15 (with Christian Konrad)
    3. Progress (and Lack Thereof) for Graph Coloring Approximation Problems
      SOFSEM'15 (invited paper), Jan 2015
    4. The Minimum Vulnerability Problem on Graphs
      COCOA'14 (with Yusuke Aoki, Bjarni V. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou)
    5. Distributed Algorithms for Coloring Interval Graphs,
      DISC '14 (with Christian Konrad)
    6. Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems.
      APPROX'13 (with Pierre Fraigniaud, Boaz Patt-Shamir, Dror Rawitz, Adi Rosen)
    7. On the Impact of Identifiers on Local Decision.
      OPODIS'12, Dec 2012. (with Pierre Fraigniaud, and Amos Korman)
    8. Space-Constrained Interval Selection
      ICALP '12, arXiv:1202.4326v1 (with Yuval Emek and Adi Rosen).
    9. Streaming Algorithms for Independent Sets
      ICALP, July 2010 (with Bjarni V. Halldorsson, Elena Losievskja and Mario Szegedy).
    10. Return of the Boss Problem: Competing Online Against a Non-Adaptive Adversary
      FUN, June 2010 (with Hadas Shachnai).
    11. Batch Coloring Tree-like Graphs
      SWAT 2008 (with Hadas Shachnai).
    12. Robust Cost Coloring
      SODA 2008 (with Takuro Fukunaga and Hiroshi Nagamochi).
    13. Rent-or-Buy scheduling and cost coloring problems
      FSTTCS 2007 (with Takuro Fukunaga and Hiroshi Nagamochi).
    14. Parameterized algorithms and complexity of non-crossing spanning trees.
      WADS '07 (with Christian Knauer, Andreas Spillner, Takeshi Tokuyama).
    15. Strip graphs: Recognition and Scheduling.
      WG '06 (with Ragnar K. Karlsson).
    16. Strong colorings of hypergraphs.
      WAOA 2004 (with Geir Agnarsson).
    17. Logical form equivalence: The case of referring expressions generation.
      8th European Workshop on Natural Language Generation, 2001 (with Kees van Deemter).
    18. On computing Prufer codes in parallel.
      Journées de l'Informatique Messine -- Algorithmes de graphes, May 2000 (with Ray Greenlaw, and Rossella Petreschi).
    19. Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.
      ISAAC '00 (with Takao Asano, Kazuo Iwama, Takeshi Matsuda).
    20. Approximating k-Set Cover and Complementary Graph Coloring.
      IPCO '96.
    21. Greedy Approximations of Independent Sets in Low Degree Graphs.
      ISAAC '95 (with Kiyohito Yoshihara) PDf .
    22. Approximating Discrete Collections via Local Improvements
      SODA '95 Note
    23. On some communication complexity problems related to threshold functions
      FSTTCS '93 (with K. V. Subrahmanyam, and Jaikumar Radhakrishnan).
    24. Directed vs. undirected monotone contact networks for threshold functions.
      FOCS '93(with K. V. Subrahmanyam, and Jaikumar Radhakrishnan).

    Book Chapters

    1. Multicoloring: Problems and Techniques. Invited paper to MFCS '04.
    2. Approximations of independent sets in graphs. Invited survey paper, from APPROX '98.

    Unrefereed Manuscripts

    Papers in Icelandic

    Thesis

    Student Publications


    Last revised February 2015, Magnus M Halldorsson