Magnus M. Halldorsson: Superseded papers

This page contains preliminary versions of papers that have been superseded by newer (usually journal) versions.

Online Selection of Intervals and t-Intervals
SWAT, June 2010 (with Unnar Bachmann and Hadas Shachnai).
SDP-based Algorithms for Maximum Independent Set Problems on Hypergraphs.
ICALP, July 2009 (with Geir Agnarsson and Elena Losievskaja).
Min Sum Edge Coloring in Multigraphs via Configuration LP.
IPCO 2008 (with Guy Kortsarz and Maxim Sviridenko). (Full version).
Approximating Independent Sets in Bounded-Degree Hypergraphs.
WADS '07 (with Elena Losievskaja).
Minimizing Interference of a Wireless Ad-Hoc Network in a Plane
ALGOSENSORS '06 (with Takeshi Tokuyama).
Weighted Sum Coloring in Batch Scheduling of Conflicting Jobs.
APPROX '06 (with Leah Epstein, Asaf Levin, Hadas Shachnai). (See journal version below.)
Approximation Algorithms for the Weighted Independent Set Problem.
WG ’05(with Akihisa Kako, Takao Ono, Tomio Hirata).
Improved Bounds for Sum Multicoloring and Weighted Completion Time of Dependent Jobs
WAOA 2004 (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai).
On Spectrum Sharing Games
PODC 2004 (with Joseph Y. Halpern, Li (Erran) Li, Vahab S. Mirrokni).
Improved results for data migration and open-shop scheduling.
ICALP 2004 (with Rajiv Gandhi, Guy Kortsarz and Hadas Shachnai).
On Coloring Squares of Outerplanar graphs.
SODA 2004 (with Geir Agnarsson).
Proper down-coloring of simple acyclic digraphs.
2nd Int'l Workshop, AGTIVE 2003, LNCS #3062, May 2004 (with Geir Agnarsson, Ágúst Egilsson).
Improved approximation of the stable marriage problem.
ESA 2003 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa).
Randomized approximation of the stable marriage problem.
COCOON 2003 (with Kazuo Iwama, Shuichi Miyazaki and Hiroki Yanagisawa).
Inapproximability Results on Stable Marriage Problems
LATIN 2002 (with Kazuo Iwama, Shuichi Miyazaki and Yasufumi Morita).
Powers of Geometric Intersection Graphs and Dispersion Algorithms.
SWAT 2002 (with Geir Agnarsson, Peter Damaschke)
Scheduling Split Interval Graphs.
SODA 2002 (with Reuven Bar-Yehuda, Seffi Naor, Hadas Shachnai, and Irina Shapira)
Minimizing Average Completion of Dedicated Tasks and Interval Graphs.
APPROX 2001 (with Guy Kortsarz and Hadas Shachnai).
On the approximability of the minimum test collection problem.
ESA 2001(with Bjarni V. Halldórsson and R. Ravi).
Approximating the domatic number.
STOC 2000 [© 2000 ACM Inc., included here by permission] (with Uriel Feige, Guy Kortsarz).
Multi-coloring trees.
COCOON '99. (with Guy Kortsarz, Andrzej Proskurowski, Hadas Shachnai, Ravit Salman, Jan Arne Telle).
Mod-2 Independence and Domination in Graphs.
WG '99. Also TR, Univ. of Bergen (with Jan Kratochvil, Jan Arne Telle)
Greedy local improvement and weighted set packing approximation.
SODA '99 (with Barun Chandra).
Independent sets with domination constraints.
ICALP '98. (with Jan Kratochvíl, and Jan Arne Telle).
Approximating the Generalized Block Distribution of a Matrix.
SWAT '98 (with Bengt Aspvall and Fredrik Manne).
Approximation and Special Cases of Common Subtrees and Editing Distance.
ISAAC '96 (with Keisuke Tanaka), PDF.
Facility Dispersion and Remote Subgraphs.
SWAT '96 (with Barun Chandra).
Finding Subsets Maximizing Minimum Structures.
SODA '95 (with Kazuo Iwano, Naoki Katoh, and Takeshi Tokuyama).
Improved approximations of independent sets in bounded-degree graphs.
SWAT '94 (with Jaikumar Radhakrishnan).
Greed is good: Approximating independent sets in sparse and bounded-degree graphs.
STOC '94 (with Jaikumar Radhakrishnan).
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).
Parallel and on-line graph coloring.
ISAAC '92, pages 61--70, Nagoya, Japan, Dec. 1992. Springer LNCS #650.
Received the Best Paper Award.
Lower bounds for on-line graph coloring.
SODA '92, pages 211--216 (with Mario Szegedy).
Approximating maximum independent sets by excluding subgraphs.
SWAT '90 LNCS #447, pages 13--25 (with Ravi B. Boppana).

Unrefereed Manuscripts

On representable graphs, semi-transitive orientations, and the representation numbers (with Sergey Kitaev, Artem Pyatkin).
arXiv:0810.0310v1 [math.CO], October 2008.
On coloring squares of outerplanar graphs.
Technical report VHI-03-2005, Dec 2005. (with Geir Agnarsson). (Extensions of the SODA 2004 paper)
Approximation algorithms for complete partitions of regular graphs, Manuscript, May 2005.(Subsumed by the journal paper "Complete partitions of graphs").

Last revised February 2015, Magnus M Halldorsson