Susanne Albers
Eric Angel
Giorgio Ausiello
Ricardo Baeza-Yates
Jon Bentley
Adam Buchsbaum
Ioannis Chatzigiannakis
Camil Demetrescu (chair)
Cid de Souza
Rolf Fagerberg
Rudolf Fleischer
Monika Henzinger
Dorit S. Hochbaum
Michel Gendreau
Giuseppe F. Italiano
Riko Jacob
Richard Ladner
Kurt Mehlhorn
Bernard Moret
S. Muthukrishnan
Petra Mutzel
Giri Narasimhan
Robert Sedgewick
Thomas Stuetzle
Jan Vahrenhold
Renato Werneck
Norbert Zeh

Steering Committee

Edoardo Amaldi
David A. Bader
Josep Diaz
Giuseppe F. Italiano
David Johnson
Klaus Jansen
Kurt Mehlhorn
Ian Munro
Sotiris Nikoletseas
Jose Rolim (chair)
Pavlos Spirakis

Organizing Committee

Vincenzo Bonifaci
Saverio Caminiti
Fabio Dellutri
Camil Demetrescu
Irene Finocchi
Luigi Laura
Andrea Vitaletti

WEA 2007

6th Workshop on Experimental Algorithms

June 6-8, 2007 — Rome Italy

Speakers

Plenary Speakers

Corinna Cortes (Google)

Peter Sanders (Universität Karlsruhe)

Maria Serna (Universitat Politècnica de Catalunya)

Corinna Cortes (Google Research)

An Alternative Ranking Problem for Search Engines

Joint work with Mehryar Mohri and Ashish Rastogi

Abstract:
This paper examines in detail an alternative ranking problem for
search engines, movie recommendation, and other similar ranking
systems motivated by the requirement to not just accurately predict
pairwise ordering but also preserve the magnitude of the preferences
or the difference between ratings. We describe and analyze several
cost functions for this learning problem and give stability bounds for
their generalization error, extending previously known stability
results to non-bipartite ranking and magnitude of
preference-preserving algorithms. We present algorithms optimizing
these cost functions, and, in one instance, detail both a batch and an
on-line version. For this algorithm, we also show how the
leave-one-out error can be computed and approximated efficiently,
which can be used to determine the optimal values of the trade-off
parameter in the cost function. We report the results of experiments
comparing these algorithms on several datasets and contrast them with
those obtained using an AUC-maximization algorithm. We also compare
training times and performance results for the on-line and batch
versions, demonstrating that our on-line algorithm scales to
relatively large datasets with no significant loss in accuracy.

Peter Sanders (Universität Karlsruhe)

Engineering Fast Route Planning Algorithms

Joint work with Dominik Schultes

Abstract:
Algorithms for route planning in transportation networks have
recently undergone a rapid development, leading to methods that are
up to one million times faster than Dijkstra's algorithm. We
outline ideas, algorithms, implementations, and experimental methods behind
this development. We also explain why the story is not
over yet because dynamically changing networks, flexible objective
functions, and new applications pose a lot of interesting
challenges.

Maria Serna (Universitat Politècnica de Catalunya)

Random models for geometric graphs

Abstract:
In the last decade there has been an increasing interest in graphs
whose nodes are placed in the plane. In particular when modeling
the communication pattern in wireless ad-hoc networks. The
different communication ways or protocol implementation have
directed the interest of the community to study and use different
intersection graph families as basic models of communication. In
this talk we review those models when the graph nodes are placed
at random in the plane. In general we assume that the set of
vertices is a random set of points generated by placing n points
uniformly at random in the unit square. The basic distance model,
the random geometric graph connects two points if they are
at distance at most r where r is a parameter of the model
[M.D. Penrose. Random Geometric Graphs. Oxford Studies in Probability, Oxford U.P., 2003]. A second model is the k-neighbor graph in
which each node selects as neighbors the k-nearest neighbors in
P [F. Xue and P.R. Kumar. The number of neighbors needed for connectivity of wireless networks. Wireless Networks, 10(2):169-181, 2004]. Another variation, inspired by the communication
pattern of directional radio frequency and optical networks, is
the random sector graph, a generalization of the random
geometric graph introduced in [J. Díaz, J. Petit, and M. Serna. A random graph model for optical networks of sensors. IEEE Transactions on Mobile Computing, 2:143–154, 2003]. In the setting under
consideration, each node has a fixed angle alpha (0 < alpha <=
2pi) definning a sector S_{i} of transmission determined by a
random angle between the sector and the horizontal axis. Every
node which falls inside of S_{i} can potentially receive the
signal emitted by i. In this talk we survey the main properties
and parameters of such random graph families, and their use in the
modelling and experimental evaluation of algorithms and protocols
for several network problems.