Bertinoro, Italy

**Organizers:****Camil Demetrescu**, University of Rome "La Sapienza", demetres@dis.uniroma1.it**Andrew Goldberg**, Microsoft Research, goldberg@microsoft.com**Robert Tarjan**, Princeton University, ret@cs.princeton.edu

The workshop is co-sponsored by BICI, the Bertinoro Center for Informatics, and DIMACS, the Center for Discrete Mathematics and Theoretical Computer Science.

**Ittai Abraham**, Jerusalem U., Israel

Title: Partitions, Metric Space Embeddings, and Distance Oracles

I will talk about several recent results in the theory of metric space embedding and their applications to distance oracles. In particular, I will focus on new probabilistic partition results and on new notions of distortion: scaling distortion (that preserves good average distortion) and local distortion (that preserves the local distortion of the metric).

(joint work with Yair Bartal and Ofer Neiman)

Title: Online Topological Ordering

I will talk about some recent results for maintaining the topological ordering of a directed acyclic graph under an online edge insertion sequence. I will present some simple algorithms for this problem and show their analysis in the worst case scenario where an adversary chooses the order of the inserted edges as well as in the average case scenario where the edges of a complete DAG are inserted in a random order.

Title: The Power of Prefix Search (with a nice open problem)

The talk will consist of two parts. In the first part I will present our CompleteSearch engine. This engine supports a variety of powerful search features, which at first glance have little in common, yet are all realized via the same core mechanism, which solves instances of a certain kind of prefix search problem. In the second part, I will explain our currently best data structures and algorithms for this core mechanism and why they are not perfect yet. I will then formulate an open problem and hope that this stimulates some of you to think about it, so that by the end of the workshop we have something better :-)

Title: Knowledge States: A Tool in Randomized Online Algorithms

We introduce the novel concept of knowledge states; many well-known algorithms can be viewed as knowledge state algorithms. The knowledge state approach can be used to to construct competitive randomized online algorithms and study the tradeoff between competitiveness and memory.

Title: Dictionaries: Fault Tolerance versus I/O Efficiency

When dealing with massive data sets, algorithms are usually designed for I/O-efficiency, often captured by the I/O model by Aggarwal and Vitter. Another aspect of dealing with massive data is how to deal with memory faults. A model for dealing with memory faults is the faulty-memory RAM by Finocchi and Italiano. However, current fault-tolerant algorithms do not scale beyond main memory. In this paper we investigate the connection between I/O-efficiency in the I/O model and fault-tolerance in the faulty-memory RAM, for the case of dictionaries. We design the first I/O efficient resilient dictionary. We show optimality of our data structure by proving a non-trivial lower bound on the number of I/Os required for any deterministic resilient searching algorithm against an adaptive adversary. For the case of randomized algorithms, we design an optimal algorithm analyzed against a non-adaptive adversary. Noticeably the expected I/O performance of the randomized algorithm significantly improves over the worst case I/O performance of the optimal deterministic algorithm. The data structures can be made dynamic using standard techniques.

(joint work with Allan Grønlund Jørgensen and Thomas Mølhave)

Title: Rectangular Layouts and Contact Graphs

Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding rectangular layouts is a key problem. We study the area-optimization problem and show that it is NP-hard to find a minimum-area rectangular layout of a given contact graph. We present O(n)-time algorithms that construct O(n2)-area rectangular layouts for general contact graphs and O(n log n)-area rectangular layouts for trees.

We derive these results by presenting new characterizations of graphs that admit rectangular layouts and the related concept of rectangular duals, linking together works done over the past 50 years. A corollary to our results relates the class of graphs that admit rectangular layouts to rectangle of influence drawings, which have been studied in the graph drawing literature.

(joint work with Emden Gansner, Magda Procopiuc, and Suresh Venkatasubramanian)

Title: SHARC: Fast and Robust Unidirectional Routing

During the last years, impressive speed-up techniques for Dijkstra's algoritm have been developed. Unfortunately, the most advanced techniques use bidirectional search which makes it hard to use them in scenarios where a backward search is prohibited. Even worse, such scenarios are widely spread, e.g., timetable-information systems or time-dependent networks.

In this work, we present an unidirectional speed-up technique which competes with bidirectional approaches. Moreover, we show how to exploit the advantage of unidirectional routing for fast exact queries in timetable information systems and for fast approximative queries in time-dependent scenarios. By running experiments on several other inputs than road networks, we show that our approach is very robust to the input.

Title: To share or not to share? An approximate answer

In the maximum sharing problem (MS), we want to compute a set of (non-simple) paths in an undirected bipartite graph covering as many nodes as possible of the first layer of the graph, with the constraint that all paths have both endpoints in the second layer and no node in that layer is covered more than once. MS is equivalent to the node-duplication based crossing elimination problem (NDCE) that arises in the design of molecular quantum-dot cellular automata (QCA) circuits and the physical synthesis of BDD based regular circuit structures in VLSI design.

A variant of MS is the maximum simple sharing problem (MSS), where we want to compute a set of node-disjoint simple paths covering as many nodes as possible of one layer of the graph, with the constraint that all paths have both endpoints in the other layer. MSS generalizes the maximum weight node-disjoint path cover problem.

We show that MS and MSS are NP-hard, present a polynomial-time 1.5-approximation algorithm for MS and a 5/3-approximation algorithm for MSS, and show that both problems cannot be approximated with a factor better than 740/739 unless P=NP.

Title: Improved Dynamic Planar Point Location

In this talk we present recent results on dynamic planar point location. We give the first linear-space data structures for dynamic planar point location in general subdivisions (or more specifically, for dynamic vertical ray-shooting), that achieve logarithmic query time (and o(n) update time). In the fully-dynamic case, we improve the best previous query bound of Baumgarten, Jung, and Mehlhorn by a log log n factor, while increasing the update time by a factor of logepsilon n. This structure is implementable in the pointer-machine model of computation. In the random-access machine (RAM) model, we improve the deletion bound by a log log n factor, while only increasing the insertion bound by a logepsilon log n factor. For the incremental (insertions only) version of this problem, we obtain both O(log n)-time queries and insertions in the RAM model. On a pointer machine, we obtain a structure with O(log1+epsilon n) insertions and O(log n) queries, as well as a structure with O(log n) insertions and O(log n log* n) queries.

(joint work with Lars Arge and Gerth S. Brodal)

Title: Shortest Path Feasibility Algorithms: An Experimental Evaluation

This is an experimental study of algorithms for the shortest path feasibility problem: Given a graph with (possibly negative) arc lengths, find a feasible set of potentials or a negative cycle. We study previously known and new algorithms. Our testbed is more extensive than those previously used, and includes both static and incremental problems, as well as bad-case instances for all algorithms. We show that, while no single algorithm dominates, a small subset (including a new algorithm) has very robust performance in practice. Our work advances state of the art in the area and should be useful in deciding which algorithm to use for any particular application.

(joint work with Boris Cherkassky, Loukas Georgiadis, Robert Tarjan, and Renato Werneck)

Title: Revisiting The Monge Property

We revisit the "Monge" speedup for dynamic programming and show that not only time, but in many cases also space, can be reduced by an order of magnitude. We further show that it's often possible to maintain the speedup in an online setting (the original Monge speedup assumed static input).

(joint work with Amotz Bar-Noy, Yi Feng, Larry Larmore, and Yan Zhang)

Title: Finding the Maximum Suffix of a String

The talk will show how to compute the lexicographically maximum suffix of a string of n>=2 characters using at most (4/3)n-(5/3) three-way character comparisons. The best previous bound, which has stood unchallenged for more than 23 years, is (3/2)n-O(1) comparisons.

(joint work with Gianni Franceschini)

Title: Distribution-Sensitive Point Location in Convex Subdivisions

A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a constant factor of optimal.

(joint work with Sebastien Collette, Vida Dujmovic, Stefan Langerman and Pat Morin)

Title: Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model

We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in the I/O-model. The task of SpMV is to compute y:=Ax, where A is a sparse N by N matrix and x and y are vectors. Here, sparsity is expressed by the parameter k that states that A has a total of at most kN nonzeros, i.e., an average number of k nonzeros per column. The extreme choices for parameter k are well studied special cases, namely for k=1 permuting and for k=N dense matrix-vector multiplication.

We study the worst-case complexity of this computational task, i.e., what is the best possible upper bound on the number of I/Os depending on k and N only. We determine this complexity up to a constant factor for large ranges of the parameters. By our arguments, we find that most matrices with kN nonzeros require this number of I/Os, even if the program may depend on the structure of the matrix. The model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung.

We study two variants of the problem, depending on the memory layout of A:

If A is stored in column major layout, SpMV has I/O complexity: Theta( min { kN/B (1+ logM/B N/max{M,k} } ), kN } ) for k < N1-e and any constant 1>e>0. If the algorithm can choose the memory layout, the I/O complexity of SpMV is: Theta( min { kN/B (1+ logM/B N / kM } ), kN } ) for k < N1/3.

In the cache oblivious setting with tall cache assumption M > B1+e, the I/O complexity is O( kN/B (1+ logM/B N/k ) ) for A in column major layout.

(joint work with Gerth Brodal, Michael Bender, Rolf Fagerberg, and Elias Vicari)

Title: Computing the Volume of the Union of Cubes

Let C be a set of n axis-aligned cubes in R3, and let U(C) denote the union of C. We present an algorithm that can compute the volume of U(C) in time O(n4/3 log n). The previously best known algorithm, by Overmars and Yap, computes the volume of the union of any n axis-aligned boxes in R3 in O(n3/2 log n) time.

(joint work with P. Agarwal and M. Sharir)

Title: A Simple Streaming Problem with Applications to Power Consumption in Sensor Nets (short talk)

We define a simple yet new? Bad Santa problem as follows: a stream of n packages go by, half of which contain presents, half of which are empty, as distributed by a worst case adversary. A child must choose which packages to open as they go by. What is the expected number of packages the child must open to find a present with probability 1? This problem arose naturally in determining an energy efficient method for broadcasting in a radio grid network, where nodes transmit on a fixed schedule, up to half of the transmitting nodes in the listening range may be deleted by an adversary, and the listening nodes pay to stay awake for any given time slot.

(joint work with Cynthia Phillips, Jared Saia, and Max Young)

Title: Minimum Cycle Bases in Graphs: Algorithms and Applications [abstract in pdf format, 42.1 KB]

Title: FPF-SB: a Scalable Algorithm for Microarray Gene Expression Data Clustering

Efficient and effective analysis of large datasets from microarray gene expression data is one of the keys to time-critical personalized medicine. The issue we address here is the scalability of the data processing software for clustering gene expression data into groups with homogeneous expression profile. In this paper we propose FPF-SB, a novel clustering algorithm based on a combination of the Furthest-Point-First (FPF) heuristic for solving the k-center problem and a stability-based method for determining the number of clusters k. Our algorithm improves the state of the art: it is scalable to large datasets without sacrificing output quality.

(joint work with F. Geraci, M. Leoncini, M. Montangero, and M. Elena Renda)

Title: A Survey of Algorithmic Speed Scaling

Current processors produced by Intel and AMD allow the speed of the processor to be changed dynamically. Intel's SpeedStep and AMD's PowerNOW technologies allow the Windows XP operating system to dynamically change the speed of such a processor to conserve energy or reduce temperature. In this setting, the operating system must not only have a job selection policy to determine which job to run, but also a speed scaling policy to determine the speed at which the job will be run. The operating system is faced with a dual objective optimization problem as it both wants to conserve energy (or reduce temperature), and optimize some Quality of Service (QoS) measure of the resulting schedule. I will survey the current state of speed scaling research, and highlight some of the more interesting open questions.

Title: Tree Exploration with Logarithmic Memory

We consider the task of network exploration by a mobile agent (robot) with small memory. The agent has to traverse all nodes and edges of a network (represented as an undirected connected graph), and return to the starting node. Nodes of the network are unlabeled and edge ports are locally labeled at each node. The agent has no a priori knowledge of the topology of the network or of its size, and cannot mark nodes in any way.

Under such weak assumptions, cycles in the network prevent feasibility of exploration, hence we restrict attention to trees. We present an algorithm to accomplish tree exploration (with return) using O(log n)-bit memory for all n-node trees. An algorithm using O(log2 n)-bit memory and an Omega(log n) lower bound were shown previously.

(joint work with Leszek Gasieniec, Andrzej Pelc and Xiaohui Zhang)

Title: On the size of succinct indices

A succinct data structure occupies an amount of space that is close to the information-theoretic minimum plus an additional term. The latter is not necessarily a lower-order term and, in several cases, completely dominates the space occupancy both in theory and in practice. We present several solutions to partially overcome this problem, introducing new techniques of independent interest that allow us to improve over previously known upper and lower bounds.

(joint work with Alex Golynski, Ankur Gupta, Roberto Grossi and Srinivasa Rao)

Title: Geometric spanners: New Results

In my talk I will describe new results on geometric spanners. In particular, I will focus on a new construction of spanners for disk graphs. A disk graph is a directed graph and thus this result implies the first 'good' spanner construction for an important class of directed graph.

Title: Algorithm Engineering - An Attempt at a Definition

Algorithm engineering can be viewed as an approach to algorithm development where design, analysis, implementation, and experimentation work together. This talk gives a more detailed definition and motivates it with examples for very basic algorithms and data structures like sorting and full text indices.

Title: Route Planning in Road Networks

An up-to-date overview on our research regarding route planning in road networks.

(joint work with Peter Sanders)

Title: Clustering Dynamic Data Streams

A dynamic geometric data stream is a very long sequence of Insert/Delete operations of points from a discrete space {1,...,Delta}d. A data streaming algorithm computes a statistic of the current point set using small space, i.e. space polylogarithmic in \Delta. In this talk we develop a data streaming algorithm for the k-median problem for dynamic geometric data streams. We maintain a set of k centers that approximate the optimal set of centers within a factor of (1+epsilon). Our algorithm is based on coresets, which are small point sets that approximate a given point set with respect to an optimization problem. Finally, we show how coresets can be used to enhance the performance of the k-means clustering algorithm.

Title: Mergeable trees

Title: Interval Graph Completion and Polynomial-Time Preprocessing

This talk will start by arguing that the complexity class FPT can be used to capture the notion of polynomial-time preprocessing to reduce input size. This is followed by an FPT algorithm with runtime O(k2kn3m for the following NP-complete problem [GT35 in Garey&Johnson]: Given an arbitrary graph G on n vertices and m edges, can we obtain an interval graph by adding at most k edges to G? The given algorithm answers a question first posed by Kaplan, Shamir and Tarjan in 1994.

Title: Reach for A*: Efficient Point-to-Point Shortest Path Computation

We show how to accelerate the exact computation point-to-point shortest paths with a combination of A* search (which directs the search) and reach-based routing (which makes the search sparser). Although our main application is computing driving directions on road networks, we show that the algorithm can be applied to other graph classes as well.

(joint work with Andrew Goldberg and Haim Kaplan)

Title: Multiobjective Optimization: New Results and Applications

Until quite recently, the vast majority of research in multiobjective optimization had focussed either on exact methods (that compute the entire Pareto set), or approximation methods through heuristic and metaheuristic approaches that did not usually provide guarantees on the quality of the returned solution. Most importantly, there had been a lack of a systematic study of the complexity issues regarding approximate versions of the Pareto set (in a way analogous to the well-established approximation theory for single objective optimization problems). We have recently witnessed the initiation of such a systematic study regarding the complexity issues of approximate Pareto sets. In particular, a generic method (FPTAS) for computing an approximate Pareto set (under certain conditions) has been developed. In this talk, I will review this method along with some new results concerning: (i) a new generic method for obtaining FPTAS to any multiobjective optimization problem with non-linear objectives; (ii) a new FPTAS for multiobjective shortest paths; and (iii) application of these results to three related problems that are of a key interest in QoS routing and traffic optimization.

Previous: Program

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on September 28, 2007.