21-23 June 2010
Bergen, Norway
The 12th Scandinavian Symposium on Algorithm Theory
will take place in Bergen, Norway during 21-23 of June, just before
midnight of Midsummer's Eve on June 23.
Invited speakers are
Sanjeev Arora,
Prabhakar Raghavan, and
Dana Randall.
The full program is below. For more details see
http://org.uib.no/swat2010/pro.html
Haim Kaplan
SWAT 2010, chair
-------------------------------------------------------------------
SUNDAY - June 20
-------------------------------------------------------------------
17:30 -- 19:30 Reception at Christies gate 18.
Light refreshments served.
Registration available.
-------------------------------------------------------------------
MONDAY - June 21
-------------------------------------------------------------------
08:45 -- 08:50 Opening announcements.
University of Bergen Student Center (Parkveien 1).
Contributed Papers Session 1. University of Bergen Student Center.
08:50 -- 09:15 Optimal exploration of terrains with obstacles.
Jurek Czyzowicz, David Ilcinkas, Arnaud Labourel
and Andrzej Pelc.
09:15 -- 09:40 Reconstructing a simple polygon from its angles.
Yann Disser, Matus Mihalak and Peter Widmayer.
Invited Talk. University of Bergen Student Center.
09:45 -- 10:45 Sanjeev Arora, Princeton University.
Coffee Break. University of Bergen Student Center.
Contributed Papers Session 2. University of Bergen Student Center.
11:15 -- 11:40 Strictly-regular number system and data structures.
Amr Elmasry, Claus Jensen and Jyrki Katajainen.
11:40 -- 12:05 An $O(\log \log n)$-competitive binary search tree
with optimal worst-case access times.
Karim Dou\"{i}eb, Prosenjit Bose, Vida Dujmovic
and Rolf Fagerberg.
12:05 -- 12:30 The emergence of sparse spanners and greedy
well-separated pair decomposition.
Jie Gao and Dengpan Zhou.
Lunch. Fosswinckelsgate 18.
Contributed Papers Session 3. University of Bergen Student Center.
14:00 -- 14:25 A bottom-up method and fast algorithms for
max independent set.
Bourgeois Nicolas, Bruno Escoffier,
Vangelis Paschos and Johan M. M. van Rooij.
14:25 -- 14:50 Capacitated domination faster than $O(2^n)$.
Marek Cygan, Marcin Pilipczuk and Jakub Wojtaszczyk.
14:50 -- 15:15 Isomorphism for graphs of bounded feedback
vertex set number.
Stefan Kratsch and Pascal Schweitzer.
15:15 -- 15:40 On feedback vertex set: New measure and new structures.
Yixin Cao, Jianer Chen and Yang Liu.
Coffee Break. University of Bergen Student Center.
Contributed Papers Session 4. University of Bergen Student Center.
16:10 -- 16:35 Conflict-free coloring made stronger.
Elad Horev, Roi Krakovski and Shakhar Smorodinsky.
16:35 -- 17:00 Polychromatic coloring for half-planes.
Shakhar Smorodinsky and Yelena Yuditsky.
17:00 -- 17:25 A 3/2-approximation algorithm for multiple depot
multiple traveling salesman problem.
Zhou Xu and Brian Rodrigues.
Bussiness Meeting. University of Bergen Student Center.
17:30 -- 18:00
-------------------------------------------------------------------
TUESDAY - June 22
-------------------------------------------------------------------
08:45 -- 08:50 Opening announcements.
University of Bergen Student Center (Parkveien 1).
Contributed Papers Session 5. University of Bergen Student Center.
08:50 -- 09:15 Minimum and maximum against $k$ lies.
Michael Hoffmann, Jiri Matousek, Yoshio Okamoto
and Philipp Zumstein.
09:15 -- 09:40 Feasible and accurate algorithms for covering
semidefinite programs.
Garud Iyengar, David Phillips and Cliff Stein.
Invited Talk. University of Bergen Student Center.
09:45 -- 10:45 Prabhakar Raghavan, Yahoo! Research Labs.
Coffee Break. University of Bergen Student Center.
Contributed Papers Session 6. University of Bergen Student Center.
11:15 -- 11:40 Systems of linear equations over $F_2$ and problems
parameterized above average.
Robert Crowston, Gregory Gutin, Mark Jones,
Eun Jung Kim and Imre Ruzsa.
11:40 -- 12:05 Capacitated max-batching with interval graph
compatibilities.
Tim Nonner.
12:05 -- 12:30 A weakly robust PTAS for minimum clique partition
in unit disk graphs.
Imran Pirwani and Mohammad Salavatipour.
Lunch. Fosswinckelsgate 18.
Contributed Papers Session 7. University of Bergen Student Center.
14:00 -- 14:25 Representing a functional curve by curves with
fewer peaks.
Danny Z. Chen, Chao Wang and Haitao Wang.
14:25 -- 14:50 Bregman clustering for separable instances.
Marcel R. Ackermann and Johannes Bl\"{o}mer.
14:50 -- 15:15 Improved methods for generating quasi-gray codes.
Prosenjit Bose, Paz Carmi, Dana Jansens,
Anil Maheshwari, Pat Morin and Michiel Smid.
15:15 -- 15:40 The MST of symmetric disk graphs is light.
A. Karim Abu-Affash, Rom Aschner, Paz Carmi
and Matthew J. Katz.
Coffee Break. University of Bergen Student Center.
Contributed Papers Session 8. University of Bergen Student Center.
16:00 -- 16:25 Vector bin packing with multiple-choice.
Boaz Patt-Shamir and Dror Rawitz.
16:25 -- 16:50 Bin packing with fixed number of bins revisited.
Klaus Jansen, Stefan Kratsch, Daniel Marx
and Ildiko Schlotter.
16:50 -- 17:15 Cops and robber game without recharging.
Fedor Fomin, Petr Golovach and Daniel Lokshtanov.
Conference Dinner. Meet at Torget (the harbour).
18:00 -- Boat departs for conference dinner
-------------------------------------------------------------------
WEDNESDAY - June 23
-------------------------------------------------------------------
08:45 -- 08:50 Opening announcements.
University of Bergen Student Center (Parkveien 1).
Contributed Papers Session 9. University of Bergen Student Center.
08:50 -- 09:15 Path schematization for route sketches.
Daniel Delling, Andreas Gemsa, Thomas Pajor
and Martin Noellenburg.
09:15 -- 09:40 Approximation algorithms for free-label maximization.
Mark de Berg and Dirk H.P. Gerrits.
Invited Talk. University of Bergen Student Center.
09:45 -- 10:45 Dana Randall, Georgia Institute of Technology.
Coffee Break. University of Bergen Student Center.
Contributed Papers Session 10. University of Bergen Student Center.
11:15 -- 11:40 Polynomial kernels for hard problems on disk graphs.
Bart Jansen.
11:40 -- 12:05 Faster parameterized algorithms for minor containment.
Isolde Adler, Frederic Dorn, Fedor V. Fomin,
Ignasi Sau and Dimtrios M. Thilikos.
12:05 -- 12:30 Fixed-parameter algorithms for cochromatic number and
disjoint rectangle stabbing.
Pinar Heggernes, Dieter Kratsch, Daniel Lokshtanov,
Venkatesh Raman and Saket Saurabh.
Lunch. Fosswinckelsgate 18.
Contributed Papers Session 11. University of Bergen Student Center.
14:00 -- 14:25 Dispatching equal-length jobs to parallel machines
to maximize throughput.
David P. Bunde and Michael H. Goldwasser.
14:25 -- 14:50 Online function tracking with generalized penalties.
Marcin Bienkowski and Stefan Schmid.
14:50 -- 15:15 Better bounds on online unit clustering.
Martin R. Ehmsen and Kim S. Larsen.
15:15 -- 15:40 Online scheduling intervals and t-intervals.
Unnar Bachmann, Magnus M. Halldorsson and
Hadas Shachnai.
Coffee Break. University of Bergen Student Center.
Contributed Papers Session 12. University of Bergen Student Center.
16:10 -- 16:35 Approximating the maximum 3- and 4-edge-colorable
subgraph.
Marcin Kaminski and Lukasz Kowalik.
16:35 -- 17:00 Improved algorithm for degree bounded survivable
network design problem.
Anand Louis and Nisheeth Vishnoi.
17:00 -- 17:25 Fast rumor spreading using shortcut edges.
Erik Demaine and Morteza Zadimoghaddam.
Midsummer's Eve Bonfire.
19:00 -- Location TBD.