Magnus M. Halldorsson: Online papers

Many of my recent papers are on arXiv.

Work on wireless algorithms

Recent Manuscripts

• Superfast Coloring in CONGEST via Efficient Color Sampling. Theoretical Computer Science (with Alexandre Nolin), 2023

1. Distributed approximation of k-service assignment
   Distributed Computing (with Sven Köhler, Dror Rawitz), published online Jan 2018.
2. Distributed Backup Placement in Networks
   Distributed Computing (with Sven Köhler, Boaz Patt-Shamir,Dror Rawitz), published online June 2017.
3. Distributed Large Independent Sets in a Single Round
   Distributed Computing (with Christian Konrad), published online March 2017.
4. 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.
5. 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.
6. 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.
7. 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)
8. Streaming Algorithms for Independent Sets
   Algorithmica, 2016 (with Bjarni V. Halldorsson, Elena Losievskja and Mario Szegedy).
9. Space-Constrained Interval Selection
   ACM Transactions on Algorithms (TALG), 2016 (with Yuval Emek, Adi Rosén)
10. 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.
11. Making wireless algorithm theory more useful: five ideas from the 2013 workshop on realistic models for algorithms in wireless networks
    ACM SIGACT News, 2014 (with Calvin Newport)
12. Online selection of intervals and t-intervals.
    Information and Computation 233:1-11, December 2013 (with Unnar Th. Bachmann and Hadas Shachnai)
13. Corrigendum: Improved results for data migration and open shop scheduling
    ACM Transactions on Algorithms (TALG), 2013 (with Rajiv Gandhi, Guy Kortsarz, Hadas Shachnai)
14. 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).
15. 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).
16. SDP-based Algorithms for Maximum Independent Set Problems on Hypergraphs.
    Theoretical Computer Science, Jan 2013 (with Geir Agnarsson and Elena Losievskaja).
17. 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).
18. Wireless scheduling with power control
    ACM Transactions on Algorithms (TALG), 2012
19. Sum edge coloring of multigraphs via configuration LP
    ACM Transactions on Algorithms (TALG), 2011 (with Guy Kortsarz, Maxim Sviridenko)
20. Vertex coloring the square of outerplanar graphs of low degree.
    Discussiones Mathematicae Graph Theory 30(4):619--636, 2010. (with Geir Agnarsson).
21. Online coloring of hypergraphs.
    Information Processing Letters 110:370--372, 2010.
22. Approximating Independent Sets in Bounded-Degree Hypergraphs.
    Discrete Applied Mathematics 157 (2009) 1773--1786, 2009 (with Elena Losievskaja).
23. Approximation algorithms for the weighted independent set problem in sparse graphs.
    Discrete Applied Mathematics, April 2009 (with Akihisa Kako, Takao Ono, and Tomio Hirata)
24. Scheduling with conflicts: Online and offline algorithms.
    Journal of Scheduling, April 2009 (with Guy Even, Lotem Kaplan, and Dana Ron)
25. Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
    Algorithmica, Dec 2009 (with Leah Epstein, Asaf Levin, Hadas Shachnai)
26. Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
    Theoretical Computer Science, 2008 (with Takeshi Tokuyama)
27. Improved bounds for scheduling conflicting jobs with minsum criteria
    ACM Transactions on Algorithms (TALG), 2008 (Rajiv Gandhi, Guy Kortsarz, Hadas Shachnai)
28. Complete Partitions of Graphs.
    Combinatorica 2007 (with Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian.)
29. Vertex coloring acyclic digraphs and their corresponding hypergraphs.
    Discrete Applied Mathematics, 2007. (with Geir Agnarsson and Agust Egilsson.)
30. Improved approximation results for the stable marriage problem
    ACM Transactions on Algorithms (TALG), 2007 (with Kazuo Iwama, Shuichi Miyazaki, Hiroki Yanagisawa)
31. Strongly Simplicial Vertices of Powers of Trees
    Discrete Mathematics, 2007 (with Geir Agnarsson.)
32. 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.)
33. Approximating the $(h,k)$-labelling problem.
    Int. J. Mobile Mobile Network Design and Innovation 1(2):113--117, 2006.
34. Improved results for data migration and open shop scheduling
    ACM Transactions on Algorithms (TALG), 2006 (with Rajiv Gandhi, Guy Kortsarz, Hadas Shachnai)
35. 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.)
36. Randomized approximation of the stable marriage problem.
    Theoretical Computer Science 325(3):439-465, 2004 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa.)
37. Powers of Geometric Intersection Graphs and Dispersion Algorithms
    Discrete Applied Mathematics, 2003 (with Geir Agnarsson, Peter Damaschke.)
    
38. Coloring Squares of Graphs.
    SIAM J. Discrete Math, 2003 (with Geir Agnarsson.)
39. Sum Coloring Interval and k-Claw Free Graphs with Application to Scheduling Dependent Jobs.
    Algorithmica, 2003 (with Guy Kortsarz and Hadas Shachnai.)
40. 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.)
41. 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.)
42. Tools for Multicoloring with Applications to Planar Graphs and Partial k-Trees.
    Journal of Algorithms, 42(2), 334-366, February 2002 (with Guy Kortsarz.)
43. Online Independent Sets.
    Theoretical Computer Science, 289(2), 953--962, October 2002 (with Kazuo Iwama, Shuichi Miyazaki and Shiro Taketomi.)
44. Approximating the domatic number.
    SIAM Journal of Computing 32(1), 172--195, December 2002 (with Uriel Feige, Guy Kortsarz, and Arvind Srinivasan.)
45. Multicoloring Trees.
    Information and Computation, Available online 12 December 2002 (with Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, and Jan Arne Telle)
46. 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
47. Online coloring known graphs.
    In Electronic J. of Combinatorics Feb 2000.
48. Mod-2 Independence and Domination in Graphs.
    Discrete Applied Math. Earlier version appears in WG '99, LNCS. (with Jan Kratochvil, Jan Arne Telle.)
49. 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
50. Approximations of Weighted Independent Set and Hereditary Subset Problems.
    Journal of Graphs Algorithms and Applications, Vol.4, No.1, pp.1-16.
51. Approximation Algorithms for Dispersion Problems.
    Journal of Algorithms, April 2000 (with Barun Chandra.)
52. Powers of chordal graphs and their coloring.
    Congressus Numerantium, (since Sept 2000) (with Geir Agnarsson, Ray Greenlaw)
53. Greedy local improvement and weighted set packing approximation.
    Journal of Algorithms, 39(2), 223-240, May 2000. (Abstract , (PDF) (with Barun Chandra)
54. 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)
55. Finding Subsets Maximizing Minimum Structures.
    SIAM Journal of Discrete Math 12(3), 342-359, 1999. (with Kazuo Iwano, Naoki Katoh, and Takeshi Tokuyama.), PDF
56. 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
57. Independent sets with domination constraints.
    Discrete Applied Mathematics, 99(1-3), 39-54, 17 Dec 1999. (with Jan Kratochvíl, Jan Arne Telle.), PDF
58. 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
59. Approximating Steiner trees in graphs with restricted weights.
    Networks 31(4):283-292, 1998. (with Shuichi Ueno, Hiroshi Nakao, and Yoji Kajitani.), PDF
60. 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
61. Parallel and online graph coloring.
    Journal of Algorithms, 23:265-280 (1997), PDF
62. 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)
63. Lower bounds for on-line graph coloring.
    Theoretical Computer Science 130:163--174, August 1994. (with Mario Szegedy), PDF
64. 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.
65. A still better performance guarantee for approximate graph coloring.
    Information Processing Letters, 45:19--23, 25 January 1993, PDF
66. Approximating the minimum maximal independence number.
    Information Processing Letters, 46:169--172, 25 June 1993. PDF
67. 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
68. Approximating maximum independent sets by excluding subgraphs.
    BIT, 32(2):180--196, June 1992 (with Ravi B. Boppana), PDF

Refereed Conference Publications

1. Brief Announcement: Local Independent Set Approximation
   PODC '16 (with Marijke H.L. Bodlaender, Christian Konrad, Fabian Kuhn)
2. Distributed Approximation of k-Service Assignment
   OPODIS'15. LIPcs vol. 46, 2016. (with Sven Köhler, Dror Rawitz)
3. Distributed Large Independent Sets in One Round On Bounded-independence Graphs
   DISC'15 (with Christian Konrad)
4. Distributed Backup Placement in Networks
   SPAA '15 (Sven Köhler, Boaz Patt-Shamir, Dror Rawitz)
5. Progress (and Lack Thereof) for Graph Coloring Approximation Problems
   SOFSEM'15 (invited paper), Jan 2015
6. The Minimum Vulnerability Problem on Graphs
   COCOA'14 (with Yusuke Aoki, Bjarni V. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou)
7. Extending wireless algorithm design to arbitrary environments via metricity
   MSWiM '14 (with Helga Gudmundsdottir, Eyjólfur I. Ásgeirsson, Marijke H.L. Bodlaender, Joseph T. Foley, Ymir Vigfusson)
8. Distributed Algorithms for Coloring Interval Graphs,
   DISC '14 (with Christian Konrad)
9. Beyond geometry: towards fully realistic wireless models
   PODC '14 (with Marijke H.L. Bodlaender)
10. Brief announcement: locality in wireless scheduling
    SPAA '13
11. Connectivity and aggregation in multihop wireless networks
    PODC '13 (Marijke H.L. Bodlaender, Pradipta Mitra)
12. Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems.
    APPROX'13 (with Pierre Fraigniaud, Boaz Patt-Shamir, Dror Rawitz, Adi Rosen)
13. On the Impact of Identifiers on Local Decision.
    OPODIS'12, Dec 2012. (with Pierre Fraigniaud, and Amos Korman)
14. Towards tight bounds for local broadcasting
    FOMC '12 (Pradipta Mitra)
15. Brief announcement: distributed algorithms for throughput performance in wireless networks
    PODC '12 (Eyjólfur I. Ásgeirsson, Pradipta Mitra)
16. Distributed connectivity of wireless networks
    PODC '12 (with Pradipta Mitra)
17. Space-Constrained Interval Selection
    ICALP '12, arXiv:1202.4326v1 (with Yuval Emek and Adi Rosen).
18. Streaming Algorithms for Independent Sets
    ICALP, July 2010 (with Bjarni V. Halldorsson, Elena Losievskja and Mario Szegedy).
19. Online set packing and competitive scheduling of multi-part tasks
    PODC '10 (with Yuval Emek, Yishay Mansour, Boaz Patt-Shamir, Jaikumar Radhakrishnan, Dror Rawitz)
20. Return of the Boss Problem: Competing Online Against a Non-Adaptive Adversary
    FUN, June 2010 (with Hadas Shachnai).
21. Batch Coloring Tree-like Graphs
    SWAT 2008 (with Hadas Shachnai).
22. Robust Cost Coloring
    SODA 2008 (with Takuro Fukunaga and Hiroshi Nagamochi).
23. Rent-or-Buy scheduling and cost coloring problems
    FSTTCS 2007 (with Takuro Fukunaga and Hiroshi Nagamochi).
24. Parameterized algorithms and complexity of non-crossing spanning trees.
    WADS '07 (with Christian Knauer, Andreas Spillner, Takeshi Tokuyama).
25. Strip graphs: Recognition and Scheduling.
    WG '06 (with Ragnar K. Karlsson).
26. On spectrum sharing games
    PODC '04 (Joseph Y. Halpern, Li (Erran) Li, Vahab S. Mirrokni)
27. Strong colorings of hypergraphs.
    WAOA 2004 (with Geir Agnarsson).
28. Logical form equivalence: The case of referring expressions generation.
    8th European Workshop on Natural Language Generation, 2001 (with Kees van Deemter).
29. Approximating the domatic number
    STOC '00 (with Uriel Feige, Guy Kortsarz)
30. On computing Prufer codes in parallel.
    Journées de l'Informatique Messine -- Algorithmes de graphes, May 2000 (with Ray Greenlaw, and Rossella Petreschi).
31. Approximation Algorithms for the Maximum Power Consumption Problem on Combinatorial Circuits.
    ISAAC '00 (with Takao Asano, Kazuo Iwama, Takeshi Matsuda).
32. Approximating k-Set Cover and Complementary Graph Coloring.
    IPCO '96.
33. Greedy Approximations of Independent Sets in Low Degree Graphs.
    ISAAC '95 (with Kiyohito Yoshihara) PDF
    Errata, April 2019.
34. Approximating Discrete Collections via Local Improvements
    SODA '95 Note
35. Greed is good: approximating independent sets in sparse and bounded-degree graphs
    STOC '94 (with Jaikumar Radhakrishnan)
36. On some communication complexity problems related to threshold functions
    FSTTCS '93 (with K. V. Subrahmanyam, and Jaikumar Radhakrishnan).
37. 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

• A superlinear lower bound for undirected monotone contact networks computing ...
  (with K. V. Subrahmanyam, and Jaikumar Radhakrishnan) Manuscript, September 1994.
• Approximations via partitioning.
  JAIST Research Report IS-RR-95-0003F, March 1995. (Most, but not all, of the results in the manuscript appeared later in JGAA.)

Papers in Icelandic

• Punktar, línur, slembitölur og reiknirit Tímarit um raunvísindi og stærðfræði, 25 Nov 2003.

Thesis

• Frugal Methods for the Independent Set and Graph Coloring Problems.
  Ph. D. Thesis. Rutgers University, October 1991.

Student Publications

• Elena Losievskaja. Approximation Algorithms for Independent Set Problems on Hypergraphs , Ph.D. thesis. Reykjavik University, January 2010.
• Unnar Þór Bachmann. Online t-Interval Scheduling, M. Sc. thesis. Reykjavik University, January 2010.
• Yayoi Shimomura Halldorsson. Multimodal User Interface Design: Increasing Accessibility to Mathematics For Blind students M. Sc. thesis. University of Iceland, October 2005. (Ok, not my student, but related...)
• Haukur Thorgeirsson. Microarray Probe Design Using Large-Scale Genomic Search for Primer Specificity. M. Sc. thesis. University of Iceland, June 2005.