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.