#### Termes les plus recherchés

# [PDF](+115👁️) Télécharger Algorithms--ESA 2004 : 12th annual European symposium, Bergen, Norway, September 14-17, 2004 : proceedings pdf

#### Invited lectures -- Design and analysis track -- Engineering and applications track -- Author indexTélécharger gratuit Algorithms--ESA 2004 : 12th annual European symposium, Bergen, Norway, September 14-17, 2004 : proceedings pdf

LNCS 3221

Susanne Albers

Tomasz Radzik (Eds.)

Algorithms -

ESA 2004

12th Annual European Symposium

Bergen, Norway, September 2004

Proceedings

3221

Lecture Notes in Computer Science

Commenced Publication in 1973

Founding and Former Series Editors:

Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen

Editorial Board

David Hutchison

Lancaster University, UK

Takeo Kanade

Carnegie Mellon University, Pittsburgh, PA, USA

Josef Kittler

University of Surrey, Guildford, UK

Jon M. Kleinberg

Cornell University, Ithaca, NY, USA

Friedemann Mattern

ETH Zurich, Switzerland

John C. Mitchell

Stanford University, CA, USA

Moni Naor

Weizmann Institute of Science, Rehovot, Israel

Oscar Nierstrasz

University of Bern, Switzerland

C. Pandu Rangan

Indian Institute of Technology, Madras, India

Bernhard Steffen

University of Dortmund, Germany

Madhu Sudan

Massachusetts Institute of Technology, MA, USA

Demetri Terzopoulos

New York University, NY, USA

Doug Tygar

University of California, Berkeley, CA, USA

Moshe Y. Vardi

Rice University, Houston, TX, USA

Gerhard Weikum

Max-Planck Institute of Computer Science, Saarbruecken, Germany

Susanne Albers Tomasz Radzik (Eds.)

Algorithms -

ESA 2004

12th Annual European Symposium

Bergen, Norway, September 14-17, 2004

Proceedings

^ Springer

Volume Editors

Susanne Albers

Albert-Ludwigs-Universitat Freiburg

Institut fiir Informatik

Georges-Kbhler-Allee 79, 79110 Freiburg, Germany

E-mail: salbers@informatik.uni-freiburg.de

Tomasz Radzik

King’s College London

Department of Computer Science

London WC2R 2LS, UK

E-mail: radzik@dcs.kcl.ac.uk

Library of Congress Control Number: 200411 1289

CR Subject Classification (1998): F.2, G.1-2, E.l, F.1.3, 1.3.5, C.2.4, E.5

ISSN 0302-9743

ISBN 3-540-23025-4 Springer Berlin Heidelberg New York

This work is subject to copyright. All rights are reserved, whether the whole or part of the material is

concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,

reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication

or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,

in its current version, and permission for use must always be obtained from Springer. Violations are liable

to prosecution under the German Copyright Law.

Springer is a part of Springer Science-t-Business Media

springeronline.com

© Springer-Verlag Berlin Heidelberg 2004

Printed in Germany

Typesetting: Camera-ready by author, data conversion by PTP-Berlin, Protago-TeX-Production GmbH

Printed on acid-free paper SPIN: 11319627 06/3 142 5 4 3 2 1 0

Preface

This volume contains the 70 contributed papers and abstracts of two invited lec-

tures presented at the 12th Annual European Symposium on Algorithms (ESA

2004), held in Bergen, Norway, September 14-17, 2004. The papers in each sec-

tion of the proceedings are arranged alphabetically. The three distinguished in-

vited speakers were David Eppstein, Michael Fellows and Monika Henzinger.

As in the last two years, ESA had two tracks, with separate program com-

mittees, which dealt respectively with:

— the design and mathematical analysis of algorithms (the “Design and Ana-

lysis” track);

— real-world applications, engineering and experimental analysis of algorithms

(the “Engineering and Applications” track).

Previous ESAs were held at Bad Honnef, Germany (1993); Utrecht, The

Netherlands (1994); Corfu, Greece (1995); Barcelona, Spain (1996); Graz, Aus-

tria (1997); Venice, Italy (1998); Prague, Czech Republic (1999); Saarbriicken,

Germany (2000); Arhus, Denmark (2001); Rome, Italy (2002); and Budapest,

Hungary (2003). The predecessor to the Engineering and Applications track

of ESA was the annual Workshop on Algorithm Engineering (WAE) . Previous

WAEs were held in Venice, Italy (1997); Saarbriicken, Germany (1998); London,

UK (1999); Saarbriicken, Germany (2000); and Arhus, Denmark (2001).

The proceedings of the previous ESAs were published as Springer- Verlag’s

LNCS volumes 726, 855, 979, 1284, 1461, 1643, 1879, 2161, 2461, and 2832. The

proceedings of the WAEs from 1999 onwards were published as Springer- Verlag’s

LNCS volumes 1668, 1982, and 2141.

Papers were solicited in all areas of algorithmic research, including but not

limited to: computational biology, computational finance, computational geo-

metry, databases and information retrieval, external-memory algorithms, graph

and network algorithms, graph drawing, machine learning, network design, on-

line algorithms, parallel and distributed computing, pattern matching and data

compression, quantum computing, randomized algorithms, and symbolic compu-

tation. The algorithms could be sequential, distributed, or parallel. Submissions

were strongly encouraged in the areas of mathematical programming and opera-

tions research, including: approximation algorithms, branch-and-cut algorithms,

combinatorial optimization, integer programming, network optimization, poly-

hedral combinatorics, and semidefinite programming.

Each extended abstract was submitted to exactly one of the two tracks, and

a few abstracts were switched from one track to the other at the discretion of

the program chairs during the reviewing process. The extended abstracts were

read by at least four referees each, and evaluated on their quality, originality,

and relevance to the symposium. The program committees of both tracks met

at King’s Gollege London at the end of May. The Design and Analysis track se-

lected for presentation 52 out of 158 submitted abstracts. The Engineering and

VI

Preface

Applications track selected for presentation 18 out of 50 submitted abstracts.

The program committees of the two tracks consisted of:

Karen Aardal

Susanne Albers (Chair)

Timothy Chan

Camil Demetrescu

Rolf Fagerberg

Paolo Ferragina

Fedor Fomin

Claire Kenyon

Elias Koutsoupias

Klaus Jansen

Ulrich Meyer

Michael Mitzenmacher

Joseph (Sefh) Naor

Micha Sharir

Peter Widmayer

Gerhard Woeginger

Design and Analysis Track

(CWI, Amsterdam)

(University of Freiburg)

(University of Waterloo)

(University of Rome “La Sapienza”)

(BRICS Arhus and University of Southern Denmark)

(University of Pisa)

(University of Bergen)

(Ecole Poly technique, Palaiseau)

(University of Athens and UCLA)

(University of Kiel)

(MPI Saarbriicken)

(Harvard University)

(Technion, Haifa)

(Tel Aviv University)

(ETH Ziirich)

(University of Twente and TU Eindhoven)

Engineering and Applications Track

Bo Chen

Ulrich Derigs

Andrew V. Goldberg

Roberto Gross!

Giuseppe F. Italiano

Giuseppe Liotta

Tomasz Radzik (Chair)

Marie-France Sagot

Christian Scheideler

Jop F. Sibeyn

Michiel Smid

(University of Warwick)

(University of Cologne)

(Microsoft Research, Mountain View)

(University of Pisa)

(University of Rome “Tor Vergata”)

(University of Perugia)

(King’s College London)

(INRIA Rhone- Alpes)

(Johns Hopkins University)

(University of Halle)

(Carleton University)

ESA 2004 was held along with the 4th Workshop on Algorithms in Bioinfor-

matics (WABI 2004), the 4th Workshop on Algorithmic Methods and Models

for Optimization of Railways (ATMOS 2004), the 2nd Workshop on Approxi-

mation and Online Algorithms (WAOA 2004), and an International Workshop

on Parametrized and Exact Computation (IWPEC 2004) in the context of the

combined conference ALGO 2004. The organizing committee of ALGO 2004 con-

sisted of Pinar Heggernes (chair), Fedor Fomin (co-chair), Eivind Coward, Inge

Jonassen, Fredrik Manne, and Jan Arne Telle, all from the University of Bergen.

ESA 2004 was sponsored by EATCS (the European Association for Theo-

retical Computer Science), the University of Bergen, the Research Council of

Preface

VII

Norway, IBM, HP and SGI. The EATCS sponsorship included an award of EUR

500 for the authors of the best student paper at ESA 2004. The winners of the

prize were Marcin Muca and Piotr Sandowski for their paper Maximum Matching

in Planar Graphs via Gaussian Elimination.

Finally, we would like to thank the members of the program committees for

their time and work devoted to the paper selection process.

July 2004

Susanne Albers and Tomasz Radzik

Program Chairs, ESA 2004

Referees

Mohamed I. Abouelhoda

Pankaj Kumar Agarwal

Noga Alon

Steven Alpern

Ernst Althaus

Christoph Ambiihl

Luzi Anderegg

Lars Arge

Vera Asodi

Franz Aurenhammer

Yossi Azar

Holger Bast

Surender Baswana

Luca Becchetti

Rene Beier

Michael Bender

Marc Benkert

Mark de Berg

Randeep Bhatia

Ulrik Brandes

Gerth Stplting Brodal

Hajo Broersma

Adam Buchsbaum

Stefan Burkhardt

Gruia Calinescu

Saverio Caminiti

Frederic Cazals

Bernard Chazelle

Chandra Chekuri

Johnny Chen

Joseph Cheriyan

Steve Chien

Jana Chlebikova

Marek Chrobak

Julia Chuzhoy

Mark Cieliebak

Valentina Ciriani

Andrea dementi

Richard Cole

Colin Cooper

Andreas Crauser

Janos Csirik

Victor Dalmau

Siavash Vahdati Daneshmand

Gianna Del Corso

Erik Demaine

Roman Dementiev

Jorg Derungs

Tamal Dey

Emilio Di Giacomo

Walter Didimo

Martin Dietzfelbinger

Krzysztof Diks

Yefim Dinitz

Florian Dittrich

Debora Donato

Eleni Drinea

Vida Dujmovic

Christian Duncan

Stefan Edelkamp

Herbert Edelsbrunner

Alon Efrat

Stephan Eidenbenz

Lars Engebretsen

Roee Engelberg

David Eppstein

Leah Epstein

Jeff Erickson

Thomas Erlebach

Lene Monrad Favrholdt

Sandor Fekete

Mike Fellows

Amos Fiat

Irene Finocchi

Aleksei Fishkin

Lisa Fleischer

Rudolf Fleischer

Paola Flocchini

Pierre Fraigniaud

Gianni Franceschini

Paolo Franciosa

Gudmund Skovbjerg Frandsen

Antonio Frangioni

Ari Freund

Daniele Frigioni

Stefan Funke

Martin Fiirer

Hal Gabow

Referees

IX

Bernd Gartner

Marc van Kreveld

Naveen Garg

Michael Krivelevich

Leszek Gasieniec

Piotr Krysta

Olga Gerber

Alejandro Lopez-Ortiz

Georg Gottlob

Gad Landau

Fabrizio Grandoni

Kim Skak Larsen

Roberto Gross!

James Lee

Jens Gustedt

Gary G. Lee

Magnus Halldorsson

Moshe Lewenstein

Dan Halperin

Liane Lewin-Eytan

Sariel Har-Peled

Andrzej Lingas

David Hart

Dean Lorenz

Jason Hartline

Anna Lubiw

Refael Hassin

Fabrizio Luccio

Ryan Hayward

Flaminia Luccio

Danny Hermelin

Tamas Lukovski

Volker Heun

Anil Maheshwari

Stefan Hougardy

Thomas Mailund

Gor Hurkens

Ghristos Makris

Sandy Irani

Ion Mandoiu

Rob W. Irving

David Manlove

Riko Jacob

Fredrik Mamie

Tommy Jensen

Giovanni Manzini

Frank Kammer

Gitta Marchand

Viggo Kann

Alberto Marchetti-Spaccamela

Haim Kaplan

David Orden Martin

Juha Karkkainen

Jirka Matousek

Brad Karp

Ernst W. Mayr

Irit Katriel

Alessandro Mei

Michael Kaufmann

Peter Bro Miltersen

Hans Kellerer

Joseph Mitchell

Lutz Kettner

Anders Mpller

Valerie King

Angelo Monti

Tamas Kiraly

Pat Morin

Adam Kirsch

Aziz Moukrim

Teemu Kivioja

Haiko Muller

Ralf Klasing

S. Muthukrishnan

Bettina Klinz

Gene Myers

Daniel Kobler

Umberto Nanni

Jochen Konemann

Morten Hegner Nielsen

Alexandr Kononov

Naomi Nishimura

Michael Korn

Marc Nunkesser

Guy Kortsarz

Liadan O’Gallaghan

Dariusz Kowalski

Anna Ostlin Pagh

Daniel Krai

Rasmus Pagh

X

Referees

Linda Pagli

Aris Pagourtzis

Igor Pak

Anna Palbom

Alessandro Panconesi

Gopal Pandurangan

Maurizio Patrignani

Marcin Peczarski

Christian N.S. Pedersen

Leon Peeters

Marco Pellegrini

Rudi Pendavingh

Paolo Penna

Giuseppe Persiano

Seth Pettie

Andrea Pietracaprina

Maurizio Pizzonia

Greg Plaxton

Andrzej Proskurowski

Kirk Pruhs

Geppino Pucci

Uri Rabinovich

Mathieu Raffinot

Sven Rahmann

Rajmohan Rajaraman

Edgar Ramos

Michael Rao

Srinivasa Rao

R. Ravi

Dror Rawitz

Bruce Reed

Oded Regev

Franz Rendl

Romeo Rizzi

Liam Roditty

Hein Rohrig

Gunter Rote

Tim Roughgarden

Amin Saberi

Cenk Sahinalp

Jared Saia

Peter Sanders

Miklos Santha

Nicola Santoro

Fabiano Sarracco

Joe Sawada

Cynthia Sawchuk

Gabriel Scalosub

Guido Schafer

Baruch Schieber

Manfred Schimmler

Christian Schindelhauer

Klaus Schittkowski

Susanne Schmitt

Frank Schulz

Maria Serna

Jiri Sgall

Ron Shamir

Roded Sharan

Bruce Shepherd

David Shmoys

Riccardo Silvestri

Amitabh Sinha

Naveen Sivadasan

Martin Skutella

Roberto Solis-Oba

Bettina Speckmann

Frits Spieksma

Divesh Srivastava

Rob van Stee

Cliff Stein

Ileana Streinu

Maxim Sviridenko

Gabor Szabo

Arie Tamir

Eric Tannier

Jan Arne Telle

Moshe Tennenholtz

Thorsten Theobald

Dimitrios Thilikos

Ralf Thole

Torsten Tholey

Carsten Thomassen

Mikkel Thorup

loan Todinca

Laura Toma

Esko Ukkonen

Peter Ullrich

Takeaki Uno

Eli Upfal

Referees

XI

Berthold Vocking

Jan Vahrenhold

Kasturi Varadarajan

Elad Verbin

Stephane Vialette

Eric Vigoda

Luca Vismara

Tjark Vredeveld

Mirjam Wattenhofer

Birgitta Weber

Michael Weber

Udi Wieder

Ryan Williams

Alexander Wolff

David Wood

Deshi Ye

Anders Yeo

Neal Young

W. Zang

Christos Zaroliagis

Norbert Zeh

Alex Zelikovski

Guochuan Zhang

Hu Zhang

Uri Zwick

Table of Contents

Invited Lectures

A Survey of FPT Algorithm Design Techniques with an Emphasis

on Recent Advances and Connections to Practical Computing 1

Michael R. Fellows

Algorithmic Aspects of Web Search Engines 3

Monika Henzinger

Design and Analysis Track

Efficient Tradeoff Schemes in Data Structures

for Querying Moving Objects 4

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Flai Yu

Swap and Mismatch Edit Distance 16

Amihood Amir, Estrella Eisenberg, Ely Porat

Path Decomposition Under a New Cost Measure with Applications

to Optical Network Design 28

Elliot Anshelevich, Lisa Zhang

Optimal External Memory Planar Point Enclosure 40

Lars Arge, Vasilis Samoladas, Ke Yi

Maximizing Throughput in Multi-queue Switches 53

Yossi Azar, Arik Litichevskey

An Improved Algorithm for CIOQ Switches 65

Yossi Azar, Yossi Richter

Labeling Smart Dust 77

Vikas Bansal, Eriedhelm Meyer auf der Heide, Christian Sohler

Graph Decomposition Lemmas and Their Role

in Metric Embedding Methods 89

Yair Bartal

Modeling Locality: A Probabilistic Analysis of LRU and EWE 98

Luca Becchetti

An Algorithm for Computing DNA Walks 110

Ankur Bhargava, S. Rao Kosaraju

XIV Table of Contents

Algorithms for Generating Minimal Blockers of Perfect Matchings

in Bipartite Graphs and Related Problems 122

Endre Boros, Khaled Elbassioni, Vladimir Gurvich

Direct Routing: Algorithms and Gomplexity 134

Costas Busch, Malik Mag don- Ismail, Marios Mavronicolas,

Paul Spirakis

Lower Bounds for Embedding into Distributions

over Excluded Minor Graph Families 146

Douglas E. Carroll, Ashish Goel

A Parameterized Algorithm for Upward Planarity Testing 157

Hubert Chan

Fisher Equilibrium Price with a Glass of Goncave Utility Functions 169

Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao

Hardness and Approximation Results for Packing Steiner Trees 180

Joseph Cheriyan, Mohammad R. Salavatipour

Approximation Hardness of Dominating Set Problems 192

Miroslav Chlebik, Janka Chlebikovd

Improved Online Algorithms for Buffer Management in QoS Switches .... 204

Marek Chrobak, Wojciech Jawor, Jifi Sgall, Tomas Tichy

Time Dependent Multi Scheduling of Multicast 216

Rami Cohen, Dror Rawitz, Danny Raz

Gonvergence Properties of the Gravitational Algorithm

in Asynchronous Robot Systems 228

Reuven Cohen, David Peleg

The Average Gase Analysis of Partition Sorts 240

Richard Cole, David C. Kandathil

A Fast Distributed Algorithm

for Approximating the Maximum Matching 252

Andrzej Czygrinow, Miehal Hahckowiak, Edyta Szymahska

Extreme Points Under Random Noise 264

Valentina Damerow, Christian Sohler

Fixed Parameter Algorithms for Gounting and Deciding

Bounded Restrictive List iL-Golorings 275

Josep Diaz, Maria Serna, Dimitrios M. Thilikos

On Variable-Sized Multidimensional Packing 287

Leah Epstein, Rob van Stee

Table of Contents

XV

An Inductive Construction for Plane Laman Graphs

via Vertex Splitting 299

Zsolt Fekete, Tibor Jordan, Walter Whiteley

Faster Fixed-Parameter Tractable Algorithms

for Matching and Packing Problems 311

Michael R. Fellows, C. Knauer, N. Nishimura, P. Ragde,

F. Rosamond, U. Stege, Dimitrios M. Thilikos, S. Whitesides

On the Evolution of Selfish Routing 323

Simon Fischer, Berthold Vocking

Competitive Online Approximation of the Optimal Search Ratio 335

Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe,

Gerhard Trippen

Incremental Algorithms for Facility Location and fc-Median 347

Dimitris Fotakis

Dynamic Shannon Coding 359

Travis Gagie

Fractional Covering with Upper Bounds on the Variables:

Solving LPs with Negative Entries 371

Naveen Garg, Rohit Khandekar

Negotiation-Range Mechanisms: Coalition-Resistant Markets 383

Rica Gonen

Approximation Algorithms for Quickest Spanning Tree Problems 395

Refael Flassin, Asaf Levin

An Approximation Algorithm for Maximum Triangle Packing 403

Refael Flassin, Shlomi Rubinstein

Approximate Parameterized Matching 414

Garmit Hazay, Moshe Lewenstein, Dina Sokol

Approximation of Rectangle Stabbing and Interval Stabbing Problems . . . 426

Sofia Kovaleva, Frits G.R. Spieksma

Fast 3-Coloring Triangle-Free Planar Graphs 436

Lukasz Kowalik

Approximate Unions of Lines and Minkowski Sums 448

Marc van Kreveld, A. Frank van der Stappen

Radio Network Clustering from Scratch 460

Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer

XVI Table of Contents

Seeking a Vertex of the Planar Matching Poly tope in NC 472

Raghav Kulkarni, Meena Mahajan

Equivalence of Search Capability Among Mobile Guards

with Various Visibilities 484

Jae-Ha Lee, Sang-Min Park, Kyung-Yong Chwa

Load Balancing in Hypercubic Distributed Hash Tables

with Heterogeneous Processors 496

Junning Liu, Micah Adler

On the Stability of Multiple Partner Stable Marriages with Ties 508

Varun S. Malhotra

Flows on Few Paths: Algorithms and Lower Bounds 520

Maren Martens, Martin Skutella

Maximum Matchings in Planar Graphs via Gaussian Elimination 532

Marcin Mueha, Piotr Sankowski

Fast Multipoint Evaluation of Bivariate Polynomials 544

Michael Niisken, Martin Ziegler

On Adaptive Integer Sorting 556

Anna Pagh, Rasmus Pagh, Mikkel Thorup

Tiling a Polygon with Two Kinds of Rectangles 568

Eric Remila

On Dynamic Shortest Paths Problems 580

Liam Roditty, Uri Zwick

Uniform Algorithms for Deterministic Construction

of Efficient Dictionaries 592

Milan Ruzic

Fast Sparse Matrix Multiplication 604

Raphael Yuster, Uri Zwick

Engineering and Applications Track

An Experimental Study of Random Knapsack Problems 616

Rene Beier, Berthold Vocking

Contraction and Treewidth Lower Bounds 628

Hans L. Bodlaender, Arie M.C.A. Koster, Thomas Wolle

Load Balancing of Indivisible Unit Size Tokens

in Dynamic and Heterogeneous Networks 640

Robert Elsdsser, Burkhard Monien, Stefan Schamberger

Table of Contents XVII

Comparing Real Algebraic Numbers of Small Degree 652

loannis Z. Emiris, Elias P. Tsigaridas

Code Flexibility and Program Efficiency by Genericity:

Improving Cgal’s Arrangements 664

Efi Fogel, Ron Wein, Dan Halperin

Finding Dominators in Practice 677

Loukas Georgiadis, Renato F. Werneck, Robert E. Tarjan,

Spyridon Triantafyllis, David I. August

Data Migration on Parallel Disks 689

Leana Golubchik, Samir Khuller, Yoo-Ah Kim,

Svetlana Shargorodskaya, Yung-Ghun (Justin) Wan

Classroom Examples of Robustness Problems

in Geometric Computations 702

Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra,

Ghee Yap

Stable Minimum Storage Merging by Symmetric Comparisons 714

Pok-Son Kim, Arne Kutzner

On Rectangular Cartograms 724

Marc van Kreveld, Bettina Speckmann

Multi-word Atomic Read/ Write Registers on Multiprocessor Systems .... 736

Andreas Larsson, Anders Gidenstam, Phuong H. Ela,

Marina Papatriantafilou, Philippas Tsigas

Beyond Optimal Play in Two-Person-Zerosum Games 749

Ulf Lorenz

Solving Geometric Covering Problems by Data Reduction 760

Steffen Mecke, Dorothea Wagner

Efficient IP Table Lookup via Adaptive Stratified Trees

with Selective Reconstructions 772

Marco Pellegrini, Giordano Fusco

Super Scalar Sample Sort 784

Peter Sanders, Sebastian Winkel

Construction of Minimum- Weight Spanners 797

Mikkel Sigurd, Martin Zachariasen

XVIII Table of Contents

A Straight Skeleton Approximating the Medial Axis 809

Mirela Tanase, Remco C. Veltkamp

Non-additive Shortest Paths 822

George Tsaggouris, Christos Zaroliagis

Author Index 835

A Survey of FPT Algorithm Design Techniques

with an Emphasis on Recent Advances and

Connections to Practical Computing

Michael R. Fellows

School of Electrical Engineering and Computer Science

University of Newcastle, University Drive, Callaghan NSW 2308, Australia

mf ellowsScs .newcastle . edu.au

Abstract. The talk will survey the rich toolkit of FPT algorithm de-

sign methodologies that has developed over the last 20 years, includ-

ing “older” techniques such as well-quasi-ordering, bounded treewidth,

color-coding, reduction to a problem kernel, and bounded search trees —

which have continued to deepen and advance — as well as some recently

developed approaches such as win/win’s, greedy localization, iterative

compression, and crown decompositions.

Only in the last few years has it become clear that there are two distinct theoreti-

cal “games” being played in the effort to devise better and better FPT algorithms

for various problems, that is, algorithms with a running time of 0(/(fc)n°), where

c is a fixed constant, k is the parameter, and n is the total input size. The first

of these games is the obvious one of improving the parameter cost function /(fc).

For example, the first FPT algorithm for Vertex Cover had a running time of

2^n. After a series of efforts, the best currently known algorithm (due to Chan-

dran and Grandoni, in a paper to be presented at IWPEC 2004), has a parameter

cost function of f{k) = (1.2745)^fc^. The second theoretical game being played

in FPT algorithm design has to do with efficient kernelization. The naturality

and universality of this game comes from the observation that a parameterized

problem is FPT if and only if there is a polynomial time preprocessing (also called

data reduction or kernelization) algorithm that transforms the input (x, k) into

(x',fc'), where k' < k and \x'\ < g{k) for some kernel-bounding function g{k),

and where of course (x, k) is a yes-instance if and only if (x', k') is a yes-instance.

In other words, modulo polynomial-time pre-processing, all of the difficulty, and

even the size of the input that needs to be considered, is bounded by a function of

the parameter. The natural theoretical game from this point of view about FPT

is to improve the kernel-bounding function g(k). For example, after strenous ef-

forts, a kernel-bounding function of g{k) = 335fc has recently been achieved (by

Alber et al.) for the Planar Dominating Set problem.

Some of the new techniques to be surveyed pertain to the /(fc) game, some

address the kernelization game, and some are relevant to both of these goals

in improving FPT algorithms. One of the striking things about the “positive”

toolkit of FPT algorithm design is how unsettled the area seems to be, with

S. Albers and T. Radzik (Eds.): ESA 2004, LNCS 3221, pp. 1—2, 2004.

(c) Springer- Verlag Berlin Heidelberg 2004

2

M.R. Fellows

seemingly rather basic methodological insights still emerging in recent years

with surprising frequency. In other words, despite 20 years of research on FPT

algorithm design, the area still seems to be in its infancy.

Most of the work on FPT algorithm design to date has been theoretical,

sometimes highly theoretical and seemingly completely impractical (such as in

FPT results obtained by well-quasiordering methods). The last few years have

seen two developments concerning the practical relevance of FPT algorithmics.

First of all, there has been a surge of implementation efforts that have helped

to clarify the somewhat complex relationship between the theoretical games and

practical algorithms. In many cases, adaptations of the structural and algorith-

mic insights of the theoretical FPT results are yielding the best available practi-

cal algorithms for problems such as Vertex Cover, regardless of whether the

parameter is small or not! For example, polynomial-time pre-processing rules

uncovered by the kernelization game will always be useful, and are sometimes of

substantial commercial interest. Similarly, clever branching strategies that are

often a key part of advances in the f{k) game are of universal significance with

respect to backtracking heuristics for hard problems. Some striking examples of

this interplay of FPT theory and practical implementations will be described by

Langston in his IWPEC 2004 invited address.

Secondly, a broad realization has developed that many implemented practi-

cal algorithms for hard problems, that people are quite happy with, are actually

FPT algorithms, unanalyzed and not described as such, sometimes even with

quite terrible /(A:)’s (if viewed theoretically) and employing relatively unsophis-

ticated pre-processing. So it does seem that there is plenty of scope for theoretical

research on improved FPT algorithms to have considerable impact on practical

computing.

Algorithmic Aspects of Web Search Engines

Monika Henzinger

Google Inc.

Mountain View, CA 94043, USA

monikaSgoogle . com

Abstract. Web search engines have emerged as one of the central ap-

plications on the internet. In fact, search has become one of the most

important activities that people engage in on the Internet. Even beyond

becoming the number one source of information, a growing number of

businesses are depending on web search engines for customer acquisition.

In this talk I will brief review the history of web search engines: The

first generation of web search engines used text-only retrieval techniques.

Google revolutionized the held by deploying the PageRank technology -

an eigenvector-based analysis of the hyperlink structure- to analyze the

web in order to produce relevant results. Moving forward, our goal is to

achieve a better understanding of a page with a view towards producing

even more relevant results.

Google is powered by a large number of PGs. Using this infrastructure

and striving to be as efficient as possible poses challenging systems prob-

lems but also various algorithmic challenges. I will discuss some of them

in my talk.

S. Albers and T. Radzik (Eds.): ESA 2004, LNCS 3221, p. 3, 2004.

© Springer- Verlag Berlin Heidelberg 2004

Efficient Tradeoff Schemes in Data Structures

for Querying Moving Objects*

Pankaj K. Agarwal^, Lars Arge^, JefF Erickson^, and Hai Yu^

^ Department of Computer Science, Duke University,

Durham, NC 27708-0129

{pankaj , large , f ishhai}@cs . duke . edu

^ Department of Computer Science, University of Illinois,

Urbana, IL 61801-2302

jeff e@cs .uiuc . edu

Abstract. The ability to represent and query continuously moving ob-

jects is important in many applications of spatio-temporal database sys-

tems. In this paper we develop data structures for answering various

queries on moving objects, including range and proximity queries, and

study tradeoffs between various performance measures — query time, data

structure size, and accuracy of results.

1 Introduction

With the rapid advances in geographical positioning technologies, it has become

feasible to track continuously moving objects accurately. In many applications,

one would like to store these moving objects so that various queries on them can

be answered quickly. For example, a mobile phone service provider may wish to

know how many users are currently present in a specified area. Unfortunately,

most traditional data structure techniques assume that data do not change over

time. Therefore the problem of efficiently representing and querying moving

objects has been extensively researched in both the database and computational

geometry communities. Recently, several new techniques have been developed;

see [1,7,9,15,17,22] and references therein.

The kinetic data structure framework (KDS) proposed by Basch et al. [9] has

been successfully applied to a variety of geometric problems to efficiently main-

tain data structures for moving objects. The key observation of KDS is that

though the actual structure defined by a set of moving objects may change con-

tinuously over time, its combinatorical description changes only at discrete time

instances. Although this framework has proven to be very useful for maintaining

* Research by the first and fourth authors is supported by NSF under grants CCR-

0086013, EIA-9870724, EIA-0131905, and CCR-0204118, and by a grant from the

U.S. -Israel Binational Science Foundation. Research by the second author is sup-

ported by NSF under grants EIA-9972879, CCR-9984099, EIA-0112849, and INT-

0129182. Research by the third author is supported by NSF under grants CCR-

0093348, DMR-0121695 and CCR-0219594.

S. Albers and T. Radzik (Eds.): ESA 2004, LNCS 3221, pp. 4—15, 2004.

(c) Springer- Verlag Berlin Heidelberg 2004

Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects

5

geometric structures, it is not clear whether it is the right framework if one sim-

ply wants to query moving objects: on the one hand, there is no need to maintain

the underlying structure explicitly, and on the other hand the KDS maintains

a geometric structure on the current configuration of objects, while one may

actually wish to answer queries on the past as well as the future configurations

of objects.

For example, one can use the KDS to maintain the convex hull of a set of lin-

early moving points [9]. While the points move, O(n^) events are processed when

the combinatorial description of the convex hull changes, each requiring 0(log^ n)

time. Using the maintained structure, one can easily determine whether a query

point lies in the convex hull of the current configuration of points. But suppose

one is interested in queries of the following form: “Does a point p lie in the

convex hull of the point set at a future time tq?” In order to answer this query,

there is no need to maintain the convex hull explicitly. The focus of this paper is

to develop data structures for answering this and similar types of queries and to

study tradeoffs between various performance measures such as query time, data

structure size, and accuracy of results.

Problem statement. Let S = {pi,p 2 ,-'' iPn} be a set of moving points in

or K^. For any time t, let Pi{t) be the position of Pi at time t, and let

S{t) = {pi{t) , p 2 {t) , ■ ■ ■ ,Pn{t)} be the configuration of S at time t. We assume

that each pi moves along a straight line at some fixed speed. We are interested

in answering the following queries.

— Interval query: Given an interval / = [yi,y 2 ] C and a time stamp tg,

report S{tg) fl /, that is, all k points of S that lie inside I at time tg.

— Rectangle query: Given an axis-aligned rectangle i? C and a time

stamp tg, report S{tg) fl R, that is, all k points of S that lie inside R at

time tg.

— Approximate nearest- neighbor query: Given a query point p € a

time stamp tg and a parameter i5 > 0, report a point p' G S such that

d{p,p'{tg)) < (1 + 5 ) ■mmg(zsd{p,q{tg)).

— Approximate farthest-neighbor query: Given a query point p G R^, a

time stamp tg, and a parameter 0 < 5 < 1, report a point p' G S such that

d{p,p'{tg)) > (1 - 5 ) • maxg(z sd{p,q{tg)).

— Convex- hull query: Given a query point p € R^ and a time stamp tg,

determine whether p lies inside the convex hull of S{tg).

Previous results. Range trees and fcd-trees are two widely used data structures

for orthogonal range queries; both of these structures have been generalized to

the kinetic setting. Agarwal et al. [1] developed a two-dimensional kinetic range

tree that requires 0(nlogn/loglogn) space and answers queries in 0{\ogn + k)

time.^ Agarwal et al. [4] developed kinetic data structures for two variants of the

^ Some of the previous work described in this section was actually done in the standard

two-level I/O model aiming to minimize the number of I/Os. Here we interpret and

state their results in the standard internal-memory setting.

6

P.K. Agarwal et al.

standard kd-tree that can answer queries in + k) time. These kinetic

data structures can only answer queries about the current configuration of points,

that is, where tq is the current time.

Kollios et al. [17] proposed a linear-size data structure based on partition

trees [18] for answering interval queries with arbitrary time stamps tq, in time

-I- k). This result was later extended to by Agarwal et al. [1] with

the same space and query time bounds.

Agarwal et al. [1] were the first to propose time-responsive data structures,

which answer queries about the current configuration of points more quickly

than queries about the distant past or future. Agarwal et al. [1] developed a

time-responsive data structure for interval and rectangle queries where the cost

of any query is a monotonically increasing function of the difference between

the query’s time stamp tq and the current time; the worst-case query cost is

-|- k). However, no exact bounds on the query time were known except

for a few special cases.

Fairly complicated time-responsive data structures with provable query time

bounds were developed later in [2] . The query times for these structures are ex-

pressed in terms of kinetic events', a kinetic event occurs whenever two moving

points in S momentarily share the same x-coordinate or the same y-coordinate.

For a query with time stamp tq, let <p(tq) denote the number kinetic events

between tq and the current time. The data structure uses O(nlogn) space, an-

swers interval queries in 0{ip{tq) /n -|- log n k) time, and answers rectangle

queries in O ( \/ (f{tq) ( ^/n/ yj\ip{tq) In'] ) log n-\-k) time . In the worst case , when

^p{tq) = 0{n^), these query times are no better than brute force.

Kollios et al. [16] described a data structure for one-dimensional nearest-

neighbor queries, but did not give any bound on the query time. Later, an

efficient structure was given by Agarwal et al. [1] to answer h-approximate

nearest-neighbor queries in /VS) time using 0{n/VS) space. Their data

structure can also be used to answer ^-approximate farthest-neighbor queries;

however, in both cases, the approximation parameter <5 must be fixed at prepro-

cessing time. More practical data structures to compute exact and approximate

fc-nearest-neighbors were proposed by Procopiuc et al. [20].

Basch et al. [9] described how to maintain the convex hull of a set of moving

points in under the KDS framework. They showed that each kinetic event

can be handled in logarithmic time, and the total number of kinetic events is

if the trajectories are polynomials of fixed degree; the number of events

is only O(n^) if points move linearly [5]. With a kinetic convex hull at hand,

one can easily answer a convex-hull query in O(logn) time. However, as noted

earlier, the kinetic convex hull can only answer queries on current configurations.

Our results. In this paper we present data structures for answering the five

types of queries listed above. A main theme of our results is the existence of var-

ious tradeoffs: time-responsive data structures for which the query time depends

on the value of tq' tradeoffs between query time and the accuracy of results; and

tradeoffs between query time and the size of the data structure.

Efficient Tradeoff Schemes in Data Structures for Querying Moving Objects

7

In Section 2, we describe a new time-responsive data structure for interval

queries in and rectangle queries in It uses 0(n^+^) space and can an-

swer queries in -I- polylogn -I- /c) time, where is the number

of events between tq and the current time. To appreciate how this new query

time improves over those of previously known data structures, let us examine two

extreme cases. For near-future or recent-past queries, where <f{tq) = 0{n), previ-

ous structures answer interval and rectangle queries in O(logn) and 0{y/nlogn)

time respectively, while our structures answer both queries in O(polylogn) time.

In the worst case, where (fiitq) = f7(n^), previous structures answer queries in

0(n) time, which is no better than brute force, while our structures provide a

query time of roughly 0{y/n), which is the best known for any structure of near-

linear size. Using this result, we also obtain the first time-responsive structures

for approximate nearest- and farthest-neighbor queries.

In Section 3, we present a data structure for answering ^-approximate

farthest-neighbor queries, which provides a tradeoff between the query time and

the accuracy of the result. In particular, for any fixed parameter m > 1, we

build a data structure of size 0{m) in 0{n + mJ^^) time so that a (5-approximate

farthest-neighbor query can be answered in time, given a parameter

S > 1/rn^/^ as a part of the query. Note that these bounds are all independent

of the number of points in S.

In Section 4, we present data structures for answering convex-hull queries. We

first describe data structures that produce a continuous tradeoff between space

and query time, by interpolating between one data structure of linear size and

another structure with logarithmic query time. We then present a data structure

that provides a tradeoff between efficiency and accuracy for approximate convex-

hull queries.

2 Time-Responsive Data Structures

2.1 One-Dimensional Interval Queries

Preliminaries. Let L be a set of n lines in let Z\ be a triangle, and let r be

a parameter between 1 and n. A (1/r) -cutting of L within Z\ is a triangulation Ei

of A such that each triangle of S intersects at most n/r lines in L. Chazelle [13]

described an efficient hierarchical method to construct 1/r-cuttings. In this ap-

proach, one chooses a sufficiently large constant p and sets h = [logp r] . One

then constructs a sequence of cuttings A = Eq, Ei, ■ ■ ■ , Eh = E, where Ei is a

(l/p*)-cutting of L. Ei is obtained from Ei_i by computing, for each triangle

T G Ei-i, a (l/p)-cutting Ef of Lt within r, where L,- C L is the set of lines

intersecting r. Chazelle [13] proved that |S'i| < {cipf cip(?^ fr? for each i,

where c \ , C 2 are constants and p is the number of vertices of the arrangement

of L inside A. Hence [S'] = -|- /n^) for any e > 0, provided that p

is sufficiently large. This hierarchy of cuttings can be represented as a cutting

tree T, where each node v is associated with a triangle Ay and the subset Ly C L

of lines that intersect Ay. The final cutting E is the set of triangles associated

with the leaves of T. E and T can be constructed in time 0{nr‘^ -|- prjn).

P.K. Agarwal et al.

High-level structure. Let S = {pi,--- ,Pn} be a set of n points in

each moving linearly. We regard time t as an additional dimension; each mov-

ing point Pi traces a linear trajectory in the tj/-plane, which we denote ^i. Let

L = ,£n} be the set of all n trajectories, and let A{L) denote the ar-

rangement of lines in L. Answering an interval query for interval [j/ 1 , 2 / 2 ] and

time stamp tq is equivalent to reporting all lines in L that intersect the vertical

line segment {tq} x [yi,y2\- We refer to this query as a stabbing query.

Each vertex in the arrangement A{L) corresponds to a change of y-ordering

for a pair of points in S, or in other words, a kinetic event. As in [2], we divide

the ty-plane into O(logn) vertical slabs as follows. Without loss of generality,

suppose t = 0 is the current time. Consider the partial arrangement of A{L)

that lies in the halfplane t > 0; the other side of the arrangement is handled

symmetrically. For each 1 < * < [log 2 n] , let denote the t-coordinate of the

(2®n)th vertex to the right of the line t = 0, and set tq = 0. Using an algorithm

of Bronnimann and Chazelle [10], each can be computed in O(nlogn) time.

For each i, let Wi denote the half-open vertical slab [ri_i,Ti) x R. By construc-

tion, there are at most 2*n kinetic events inside Uj<i bVj. For each slab Wi, we

construct a separate window data structure Wi for answering stabbing queries

within yVi. Our overall one-dimensional data structure consists of these O(logn)

window data structures.

Window data structure for one-sided queries. Before we describe the

window data structure Wi for answering general stabbing queries in Wi, We

first describe a simpler structure W“ to handle half-infinite query segments of

the form {tq} x (— oo,y]. Equivalently, we want to report the lines of L that lie

below the query point {tq, y).

Set r = n/2L We construct a hierarchical (l/r)-cutting S inside Wi, as

described at the beginning of this section. The cutting tree 7s of S' forms the

top part of our data structure W“; see Figure 1. Recall that any node u in 7s is

associated with a triangle Z\„ an

Lire la suite

- 7.71 MB
- 15

##### Vous recherchez le terme ""

115

186