Magnús M. Halldórsson: Online papers

My papers on arxiv.

Recent manuscripts

  1. Corrigendum:Improved results for data migration and open-shop scheduling.
    To appear in TALG (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai). Correction and slight improvement of the 2006 TALG paper.
  2. Wireless Connectivity and Capacity
    SODA '12 (with Pradipta Mitra).
  3. Nearly Optimal Bounds for Distributed Wireless Scheduling in the SINR Model.
    ICALP '11 (with Pradipta Mitra).
  4. Scheduling with interval conflicts
    STACS '11. Full version. (With Boaz Patt-Shamir, Dror Rawitz).
  5. Wireless Capacity with Oblivious Power in General Metrics.
    In SODA '11 (with Pradipta Mitra).
  6. Online set packing and competitive scheduling of multi-part tasks.
    PODC '10. Full version. (With Yuval Emek, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan and Dror Rawitz).
  7. Wireless scheduling with power control
    arXiv:1010.3427v1. To appear in ACM TALG. Earlier version appears ESA, Sept 2009.
  8. Computing wireless capacity.
    Manuscript. Correction of a draft appear in ICALP, July 2009 (with Roger Wattenhofer).

Refereed Conference Publications

  1. Streaming Algorithms for Independent Sets
    ICALP, July 2010 (with Bjarni V. Halldorsson, Elena Losievskja and Mario Szegedy).
  2. Online Selection of Intervals and t-Intervals
    SWAT, June 2010 (with Hadas Shachnai).
  3. Return of the Boss Problem: Competing Online Against a Non-Adaptive Adversary
    FUN, June 2010 (with Hadas Shachnai).
  4. Wireless scheduling with power control
    ESA, Sept 2009. (Full version, February 2011)
  5. SDP-based Algorithms for Maximum Independent Set Problems on Hypergraphs.
    ICALP, July 2009 (with Geir Agnarsson and Elena Losievskaja).
  6. Wireless Communication is in APX.
    ICALP, July 2009 (with Roger Wattenhofer). Retraction
  7. Capacity of Arbitrary Wireless Networks.
    INFOCOM, April 2009 (with Olga Goussevskaia, Roger Wattenhofer, and Emo Welzl). Note.
  8. Batch Coloring Tree-like Graphs
    SWAT 2008 (with Hadas Shachnai).
  9. Min Sum Edge Coloring in Multigraphs via Configuration LP.
    IPCO 2008 (with Guy Kortsarz and Maxim Sviridenko). (Full version).
  10. Robust Cost Coloring
    SODA 2008 (with Takuro Fukunaga and Hiroshi Nagamochi).
  11. Rent-or-Buy scheduling and cost coloring problems
    FSTTCS 2007 (with Takuro Fukunaga and Hiroshi Nagamochi).
  12. Approximating Independent Sets in Bounded-Degree Hypergraphs.
    WADS '07 (with Elena Losievskaja). (See journal version below)
  13. Parameterized algorithms and complexity of non-crossing spanning trees.
    WADS '07 (with Christian Knauer, Andreas Spillner, Takeshi Tokuyama).
  14. Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
    ALGOSENSORS '06 (with Takeshi Tokuyama).
  15. Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
    APPROX '06 (with Leah Epstein, Asaf Levin, Hadas Shachnai). (See journal version below.)
  16. Strip graphs: Recognition and Scheduling.
    WG '06 (with Ragnar K. Karlsson).
  17. Approximation Algorithms for the Weighted Independent Set Problem.
    WG ’05(with Akihisa Kako, Takao Ono, Tomio Hirata).
  18. Strong colorings of hypergraphs.
    WAOA 2004 (with Geir Agnarsson).
  19. Improved Bounds for Sum Multicoloring and Weighted Completion Time of Dependent Jobs
    WAOA 2004 (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai).
  20. On Spectrum Sharing Games
    PODC 2004 (with Joseph Y. Halpern, Li (Erran) Li, Vahab S. Mirrokni).
  21. Improved results for data migration and open-shop scheduling.
    ICALP 2004 (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai).
  22. On Coloring Squares of Outerplanar graphs.
    SODA 2004 (with Geir Agnarsson).
  23. Proper down-coloring of simple acyclic digraphs.
    2nd Int'l Workshop, AGTIVE 2003, LNCS #3062, May 2004 (with Geir Agnarsson, Ágúst Egilsson).
  24. Improved approximation of the stable marriage problem.
    ESA 2003 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa).
  25. Randomized approximation of the stable marriage problem.
    COCOON 2003 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa).
  26. Powers of Geometric Intersection Graphs and Dispersion Algorithms.
    SWAT 2002 (with Geir Agnarsson, Peter Damaschke)
  27. Inapproximability Results on Stable Marriage Problems
    LATIN 2002 (with Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita).
  28. Scheduling Split Interval Graphs.
    SODA 2002 (with Reuven Bar-Yehuda, Seffi Naor, Hadas Shachnai, and Irina Shapira)
  29. Logical form equivalence: The case of referring expressions generation.
    8th European Workshop on Natural Language Generation, 2001 (with Kees van Deemter).
  30. On the approximability of the minimum test collection problem.
    ESA 2001(with Bjarni V. Halldórsson and R. Ravi).
  31. Minimizing Average Completion of Dedicated Tasks and Interval Graphs.
    APPROX 2001 (with Guy Kortsarz and Hadas Shachnai).
  32. Approximating the domatic number.
    STOC 2000 [© 2000 ACM Inc., included here by permission] (with Uriel Feige, Guy Kortsarz).
  33. On computing Prufer codes in parallel.
    Journées de l'Informatique Messine -- Algorithmes de graphes, May 2000 (with Ray Greenlaw, and Rossella Petreschi).
  34. Online Independent Sets.
    COCOON '00 (with Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi).
  35. Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.
    ISAAC '00 (with Takao Asano, Kazuo Iwama, Takeshi Matsuda).
  36. Sum Multicoloring of Graphs.
    ESA '99 (with Amotz Bar-Noy, Guy Kortsarz, Hadas Shachnai, Ravit Salman).
  37. Approximations of Weighted Independent Set and Hereditary Subset Problems.
    COCOON '99.
  38. Multi-coloring trees.
    COCOON '99. (with Guy Kortsarz, Andrzej Proskurowski, Hadas Shachnai, Ravit Salman, Jan Arne Telle).
  39. Mod-2 Independence and Domination in Graphs.
    WG '99. Also TR, Univ. of Bergen (with Jan Kratochvil, Jan Arne Telle)
  40. Greedy local improvement and weighted set packing approximation.
    SODA '99 (with Barun Chandra).
  41. Independent sets with domination constraints.
    ICALP '98. (with Jan Kratochvíl, and Jan Arne Telle).
  42. Approximating the Generalized Block Distribution of a Matrix.
    SWAT '98 (with Bengt Aspvall and Fredrik Manne).
  43. Approximation and Special Cases of Common Subtrees and Editing Distance.
    ISAAC '96 (with Keisuke Tanaka), PDF.
  44. Facility Dispersion and Remote Subgraphs.
    SWAT '96 (with Barun Chandra).
  45. Approximating k-Set Cover and Complementary Graph Coloring.
    IPCO '96.
  46. Greedy Approximations of Independent Sets in Low Degree Graphs.
    ISAAC '95 (with Kiyohito Yoshihara) PDf .
  47. Approximating Discrete Collections via Local Improvements
    SODA '95
  48. Finding Subsets Maximizing Minimum Structures.
    SODA '95 (with Kazuo Iwano, Naoki Katoh, and Takeshi Tokuyama).
  49. On the approximation of largest common point sets and largest common subtrees.
    ISAAC '94 (with Tatsuya Akutsu).
  50. Improved approximations of independent sets in bounded-degree graphs.
    SWAT '94 (with Jaikumar Radhakrishnan).
  51. Greed is good: Approximating independent sets in sparse and bounded-degree graphs.
    STOC '94 (with Jaikumar Radhakrishnan).
  52. On some communication complexity problems related to threshold functions
    FSTTCS '93 (with K. V. Subrahmanyam, and Jaikumar Radhakrishnan).
  53. Directed vs. undirected monotone contact networks for threshold functions.
    FOCS '93(with K. V. Subrahmanyam, and Jaikumar Radhakrishnan).
  54. Parallel and on-line graph coloring.
    ISAAC '92, pages 61--70, Nagoya, Japan, Dec. 1992. Springer LNCS #650.
    Received the Best Paper Award.
  55. Approximating Steiner trees in graphs with restricted weights.
    In Proc. of 1st Asia-Pacific Conference on Circuits and Systems, pages 69--73, Sidney, Australia, December 1992 (with Shuichi Ueno, Hiroshi Nakao, and Yoji Kajitani).
  56. Lower bounds for on-line graph coloring.
    SODA '92, pages 211--216 (with Mario Szegedy).
  57. Approximating maximum independent sets by excluding subgraphs.
    SWAT '90 LNCS #447, pages 13--25 (with Ravi B. Boppana).

Journal Publications

The following works are the last versions leaving my hands. They may not incorporate corrections made in galley proofs or copyediting.
  1. Sum Edge Coloring of Multigraphs via Configuration LP.
    ACM TALG 7(2), Article 22, March 2011 (with Guy Kortsarz and Maxim Sviridenko).
  2. Vertex coloring the square of outerplanar graphs of low degree.
    Discussiones Mathematicae Graph Theory 30(4):619--636, 2010. (with Geir Agnarsson).
  3. Online coloring of hypergraphs.
    Information Processing Letters 110:370--372, 2010.
  4. Approximating Independent Sets in Bounded-Degree Hypergraphs.
    Discrete Applied Mathematics 157 (2009) 1773--1786, 2009 (with Elena Losievskaja).
  5. Approximation algorithms for the weighted independent set problem in sparse graphs.
    Discrete Applied Mathematics, April 2009 (with Akihisa Kako, Takao Ono, and Tomio Hirata)
  6. Scheduling with conflicts: Online and offline algorithms.
    Journal of Scheduling, April 2009 (with Guy Even, Lotem Kaplan, and Dana Ron)
  7. Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
    Algorithmica, Dec 2009 (with Leah Epstein, Asaf Levin, Hadas Shachnai)
  8. Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
    Theoretical Computer Science, 2008 (with Takeshi Tokuyama)
  9. Improved Bounds for Sum Multicoloring and Weighted Completion Time of Dependent Jobs.
    ACM Transactions on Algorithms, March 2008. (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai)
    Note: Corrigendum to appear in TALG, 2012 (Correction and slight improvement).
  10. Complete Partitions of Graphs.
    Combinatorica 2007 (with Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian.)
  11. Vertex coloring acyclic digraphs and their corresponding hypergraphs.
    Discrete Applied Mathematics, 2007. (with Geir Agnarsson and Agust Egilsson.)
  12. Improved approximation of the stable marriage problem.
    ACM Transactions on Algorithms 2007 (with Shuichi Miyazaki, K. Iwama, K. Yanagisawa.)
  13. Strongly Simplicial Vertices of Powers of Trees
    Discrete Mathematics, 2007 (with Geir Agnarsson.)
  14. 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.)
  15. Approximating the $(h,k)$-labelling problem.
    Int. J. Mobile Mobile Network Design and Innovation 1(2):113--117, 2006.
  16. Improved results for data migration and open-shop scheduling.
    ACM Transactions on Algorithms 2006. (with Rajiv Gandhi, Magnús M. Halldórsson, G. Kortsarz and H. Shachnai)
  17. 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.)
  18. Randomized approximation of the stable marriage problem.
    Theoretical Computer Science 325(3):439-465, 2004 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa.)
  19. Powers of Geometric Intersection Graphs and Dispersion Algorithms
    Discrete Applied Mathematics, 2003 (with Geir Agnarsson, Peter Damaschke.)
  20. Coloring Squares of Graphs.
    SIAM J. Discrete Math, 2003 (with Geir Agnarsson.)
  21. Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.
    Algorithmica, 2003 (with Guy Kortsarz and Hadas Shachnai.)
  22. 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.)
  23. 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.)
  24. Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees.
    Journal of Algorithms, 42(2), 334-366, February 2002 (with Guy Kortsarz.)
  25. Online Independent Sets.
    Theoretical Computer Science, 289(2), 953--962, October 2002 (with Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi.)
  26. Approximating the domatic number.
    SIAM Journal of Computing 32(1), 172--195, December 2002 (with Uriel Feige, Guy Kortsarz, and Arvind Srinivasan.)
  27. Multicoloring Trees.
    Information and Computation, Available online 12 December 2002 (with Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, and Jan Arne Telle)
  28. 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
  29. Online coloring known graphs.
    In Electronic J. of Combinatorics Feb 2000.
  30. Mod-2 Independence and Domination in Graphs.
    Discrete Applied Math. Earlier version appears in WG '99, LNCS. (with Jan Kratochvil, Jan Arne Telle.)
  31. 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
  32. Approximations of Weighted Independent Set and Hereditary Subset Problems.
    Journal of Graphs Algorithms and Applications, Vol.4, No.1, pp.1-16.
  33. Approximation Algorithms for Dispersion Problems.
    Journal of Algorithms, April 2000 (with Barun Chandra.)
  34. Powers of chordal graphs and their coloring.
    Congressus Numerantium, (since Sept 2000) (with Geir Agnarsson, Ray Greenlaw)
  35. Greedy local improvement and weighted set packing approximation.
    Journal of Algorithms, 39(2), 223-240, May 2000. (Abstract , (PDF) (with Barun Chandra)
  36. 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)
  37. Finding Subsets Maximizing Minimum Structures.
    SIAM Journal of Discrete Math 12(3), 342-359, 1999. (with Kazuo Iwano, Naoki Katoh, and Takeshi Tokuyama.), PDF
  38. 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
  39. Independent sets with domination constraints.
    Discrete Applied Mathematics, 99(1-3), 39-54, 17 Dec 1999. (with Jan Kratochvíl, Jan Arne Telle.), PDF
  40. 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
  41. Approximating Steiner trees in graphs with restricted weights.
    Networks 31(4):283-292, 1998. (with Shuichi Ueno, Hiroshi Nakao, and Yoji Kajitani.), PDF
  42. 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
  43. Parallel and online graph coloring.
    Journal of Algorithms, 23:265-280 (1997), PDF
  44. 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.)
  45. Lower bounds for on-line graph coloring.
    Theoretical Computer Science 130:163--174, August 1994. (with Mario Szegedy), PDF
  46. 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.
  47. A still better performance guarantee for approximate graph coloring.
    Information Processing Letters, 45:19--23, 25 January 1993, PDF
  48. Approximating the minimum maximal independence number.
    Information Processing Letters, 46:169--172, 25 June 1993. PDF
  49. 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
  50. Approximating maximum independent sets by excluding subgraphs.
    BIT, 32(2):180--196, June 1992 (with Ravi B. Boppana), PDF

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 March 2010, Magnus M Halldorsson