Conference Program

Tuesday, August 14, 2007
19:00–21:00	Reception

Wednesday, August 15, 2007
	Session 1 (Invited talk)
9:15–10:15	Finding Small Holes: A Brief Foray into Computational Topology J. Erickson
10:15–10:45	Coffee break
	Session 2A	Session 2B
10:45–11:10	Approximate range searching: the absolute model G.D. da Fonseca	A 4/3-approximation algorithm for minimum 3-edge-connectivity P. Gubbala and B. Raghavachari
11:10–11:35	Orthogonal range searching in linear and almost-linear space Y. Nekrich	Approximating the maximum sharing problem A. Chaudhary, D.Z. Chen, R. Fleischer, X.S. Hu, J. Li, M.T. Niemier, Z. Xie, and H. Zhu
11:35–12:00	Spherical LSH for approximate nearest neigbor search on unit hypersphere K. Terasawa and Y. Tanaka	The Stackelberg minimum spanning tree game J. Cardinal, E.D. Demaine, S. Fiorini, G. Joret, S. Langerman, I. Newman, and O. Weimann
12:00–13:30	Lunch break
	Session 3A	Session 3B
13:30–13:55	Edges and switches, tunnels and bridges D. Eppstein, M. van Kreveld, E. Mumford, and B. Speckmann	Discrepancy-sensitive dynamic fractional cascading, dominated maxima searching, and 2-d nearest neighbors in any Minkowski metric M.J. Atallah, M. Blanton, M.T. Goodrich, and S. Polu
13:55–14:20	How to draw a clustered tree G. Di Battista, G. Drovandi, and F. Frati	Priority queues resilient to memory faults A.G. Jørgensen, G. Moruz, and T. Mølhave
14:20–14:45	Drawing colored graphs on colored points M. Badent, E. Di Giacomo, and G. Liotta	Simple and efficient minimal perfect hash functions F. Botelho, R. Pagh, and N. Ziviani
14:45–15:15	Coffee break
	Session 4A	Session 4B
15:15–15:40	A near linear time approximation scheme for Steiner tree among obstacles in the plane M. Müller-Hannemann and S. Tazari	Constant factor approximations for the hotlink assignment problem T. Jacobs
15:40–16:05	A pseudopolynomial time O(log n)-approximation algorithm for art gallery problems A. Deshpande, T. Kim, E.D. Demaine, and S.E. Sarma	Approximation algorithms for the sex-equal stable marriage problem K. Iwama, S. Miyazaki, and H. Yanagisawa
16:05–16:30	Optimization for first order Delaunay triangulations M. van Kreveld, M. Löffler, and R. Silveira	A stab at approximating minimum subadditive join S.A. Vinterbo

Thursday, August 16, 2007
	Session 5 (Invited talk)
9:15–10:15	Algorithmic Challenges for Systems-Level Correlational Analysis: A Tale of Two Datasets M.A. Langston
10:15–10:45	Coffee break
	Session 6A	Session 6B
10:45–11:10	Flooding countries and destroying dams R.I. Silveira and R. van Oostrum	Independent sets in bounded-degree hypergraphs M.M. Halldórsson and E. Losievskaja
11:10–11:35	I/O-efficient flow modeling on fat terrains M. de Berg, O. Cheong, H. Haverkort, J.G. Lim, and L. Toma	Steiner tree in planar graphs: an O(n log n) approximation scheme with singly exponential dependence on epsilon G. Borradaile, P.N. Klein, and C. Mathieu
11:35–12:00	Computing the visibility map of fat objects M. de Berg and C. Gray	Computing a minimum-depth planar graph embedding in O(n⁴) time P. Angelini, G. Di Battista, and M. Patrignani
12:00–13:30	Lunch break
	Session 7A	Session 7B
13:30–13:55	On a family of strong geometric spanners that admit local routing strategies P. Bose, P. Carmi, M. Couture, M. Smid, and D. Xu	The k-resource problem on uniform and on uniformly decomposable metric spaces M. Bienkowski and J. Kutyłowski
13:55–14:20	Spanners for geometric intersection graphs M. Fürer and S.P. Kasiviswanathan	On robust online job shop scheduling M. Gatto and P. Widmayer
14:20–14:45	On generalized diamond spanners P. Bose, A. Lee, and M. Smid	Improved results for a memory allocation problem L. Epstein and R. van Stee
14:45–15:15	Coffee break
	Session 8A	Session 8B
15:15–15:40	Computational and structural advantages of circular boundary representation O. Aichholzer, F. Aurenhammer, T. Hackl, B. Jüttler, M. Oberneder, and Z. Šír	Parameterized algorithms and complexity of non-crossing spanning trees M.M. Halldórsson, C. Knauer, A. Spillner, and T. Tokuyama
15:40–16:05	Alpha-beta witness complexes D. Attali, H. Edelsbrunner, J. Harer, and Y. Mileyko	Improved algorithms for the feedback vertex set problems J. Chen, F.V. Fomin, Y. Liu, S. Lu, and Y. Villanger
16:05–16:30	Cauchy's theorem and edge lengths of convex polyhedra T. Biedl, A Lubiw, and M. Spriggs	Kernelization algorithms for d-hitting set problems F.N. Abu-Khzam
19:00–21:00	Conference Dinner

Friday, August 17, 2007
	Session 9A	Session 9B
9:15–9:40	Largest bounding box, smallest diameter, and related problems on imprecise points M. Löffler and M. van Kreveld	Kernelization and complexity results for connectivity augmentation problems J. Guo and J. Uhlmann
9:40–10:05	Maximizing maximal angles for plane straight-line graphs O. Aichholzer, T. Hackl, M. Hoffmann, C. Huemer, A. Pór, F. Santos, B. Speckmann, and B. Vogtenhuber	An improved parameterized algorithm for the minimum node multiway cut problem J. Chen, Y. Liu, and S. Lu
10:05–10:30	Cuttings for disks and axis-aligned rectangles in three-space E. Rafalin, D.L. Souvaine, and C. Tóth	Branch and recharge: exact algorithms for generalized domination F.V. Fomin, P.A. Golovach, J. Kratochvíl, D. Kratsch, and M. Liedloff
10:30–11:00	Coffee break
	Session 10A	Session 10B
11:00–11:25	On computing the centroid of the vertices of an arrangement and related problems D. Ajwani, S. Ray, R. Seidel, and H.R. Tiwary	Faster approximation of distances in graphs P. Berman and S.P. Kasiviswanathan
11:25–11:50	Optimal algorithms for the weighted p-center problems for points on a real line B. Bhattacharya and Q. Shi	Approximate shortest paths guided by a small index J. Derungs, R. Jacob, and P. Widmayer
11:50–13:20	Lunch break
	Session 11A	Session 11B
13:20–13:45	Initializing sensor networks of non-uniform density in the weak sensor model M. Farach-Colton and M.A. Mosteiro	Optimal lightweight construction of suffix arrays G. Nong and S. Zhang
13:45–14:10	Computing best coverage path in the presence of obstacles in a sensor field S. Basu Roy, G. Das, and S. Das	Range non-overlapping indexing and successive list indexing O. Keller, T. Kopelowitz, and M. Lewenstein
14:10–14:35	35/44-Approximation for asymmetric maxTSP with triangle inequality L. Kowalik and M. Mucha	Space-efficient straggler identification in round-trip data streams via Newton's identities and invertible bloom filters D. Eppstein and M.T. Goodrich
14:35–15:00	On Euclidean vehicle routing with allocation J. Remy, R. Spöhel, and A. Weißl	Dynamic TCP acknowledgment with sliding window H. Koga