Technical Reports

This paper provides a suite of optimization techniques for

the verification of safety properties of linear hybrid

automata with large discrete state spaces, such as

naturally arising when incorporating health state

monitoring and degradation levels into the controller

design. Such models can -- in contrast to purely functional

controller models -- not analyzed with hybrid verification

engines relying on explicit representations of modes, but

require fully symbolic representations for both the

continuous and discrete part of the state space. The

optimization techniques shown yield consistently a speedup

of about 20 against previously published results for a

similar benchmark suite, and complement these with new

results on counterexample guided abstraction refinement. In

combination with the methods guaranteeing preciseness of

abstractions, this allows to significantly extend the class

of models for which safety can be established, covering in

particular models with 23 continuous variables and 2 to the

71 discrete states, 20 continuous variables and 2 to the

199 discrete states, and 9 continuous variables and 2 to

the 271 discrete states.

We consider the speed scaling problem introduced in the seminal paper of Yao et al.. In this problem, a number of jobs, each with its own processing volume, release time, and deadline needs to be executed on a speed-scalable processor. The power consumption of this processor is $P(s) = s^\alpha$, where $s$ is the processing speed, and $\alpha > 1$ is a constant. The total energy consumption is power integrated over time, and the goal is to process all jobs while minimizing the energy consumption.

The preemptive version of the problem, along with its many variants, has been extensively studied over the years. However, little is known about the non-preemptive version of the problem, except that it is strongly NP-hard and allows a constant factor approximation. Up until now, the (general) complexity of this problem is unknown. In the present paper, we study an important special case of the problem, where the job intervals form a laminar family, and present a quasipolynomial-time approximation scheme for it, thereby showing that (at least) this special case is not APX-hard, unless $NP \subseteq DTIME(2^{poly(\log n)})$.

The second contribution of this work is a polynomial-time algorithm for the special case of equal-volume jobs, where previously only a $2^\alpha$ approximation was known. In addition, we show that two other special cases of this problem allow fully polynomial-time approximation schemes (FPTASs).

Generalized matching problems arise in a number of applications, including

computational advertising, recommender systems, and trade markets. Consider,

for example, the problem of recommending multimedia items (e.g., DVDs) to

users such that (1) users are recommended items that they are likely to be

interested in, (2) every user gets neither too few nor too many

recommendations, and (3) only items available in stock are recommended to

users. State-of-the-art matching algorithms fail at coping with large

real-world instances, which may involve millions of users and items. We

propose the first distributed algorithm for computing near-optimal solutions

to large-scale generalized matching problems like the one above. Our algorithm

is designed to run on a small cluster of commodity nodes (or in a MapReduce

environment), has strong approximation guarantees, and requires only a

poly-logarithmic number of passes over the input. In particular, we propose a

novel distributed algorithm to approximately solve mixed packing-covering

linear programs, which include but are not limited to generalized matching

problems. Experiments on real-world and synthetic data suggest that our

algorithm scales to very large problem sizes and can be orders of magnitude

faster than alternative approaches.

Hard real-time systems require tasks to finish in time. To guarantee the

timeliness of such a system, static timing analyses derive upper bounds on the

\emph{worst-case execution time} of tasks. There are two types of timing

analyses: numeric and parametric ones. A numeric analysis derives a numeric

timing bound and, to this end, assumes all information such as loop bounds to

be given a priori.

If these bounds are unknown during analysis time, a parametric analysis can

compute a timing formula parametric in these variables.

A performance bottleneck of timing analyses, numeric and especially parametric,

can be the so-called path analysis, which determines the path in the analyzed

task with the longest execution time bound.

In this paper, we present a new approach to the path analysis.

This approach exploits the rather regular structure of software for hard

real-time and safety-critical systems.

As we show in the evaluation of this paper, we strongly improve upon former

techniques in terms of precision and runtime in the parametric case. Even in

the numeric case, our approach matches up to state-of-the-art techniques and

may be an alternative to commercial tools employed for path analysis.

We consider the problem of computing a maximum cardinality {\em popular}

matching in a bipartite

graph $G = (\A\cup\B, E)$ where each vertex $u \in \A\cup\B$ ranks its

neighbors in a

strict order of preference. This is the same as an instance of the {\em

stable marriage}

problem with incomplete lists.

A matching $M^*$ is said to be popular if there is no matching $M$ such

that more vertices are better off in $M$ than in $M^*$.

\smallskip

Popular matchings have been extensively studied in the case of one-sided

preference lists, i.e.,

only vertices of $\A$ have preferences over their neighbors while

vertices in $\B$ have no

preferences; polynomial time algorithms

have been shown here to determine if a given instance admits a popular

matching

or not and if so, to compute one with maximum cardinality. It has very

recently

been shown that for two-sided preference lists, the problem of

determining if a given instance

admits a popular matching or not is NP-complete. However this hardness

result

assumes that preference lists have {\em ties}.

When preference lists are {\em strict}, it is easy to

show that popular matchings always exist since stable matchings always

exist and they are popular.

But the

complexity of computing a maximum cardinality popular matching was

unknown. In this paper

we show an $O(mn)$ algorithm for this problem, where $n = |\A| + |\B|$ and

$m = |E|$.

Graphs are increasingly used to model a variety of loosely structured data such

as biological or social networks and entity-relationships. Given this profusion

of large-scale graph data, efficiently discovering interesting substructures

buried

within is essential. These substructures are typically used in determining

subsequent actions, such as conducting visual analytics by humans or designing

expensive biomedical experiments. In such settings, it is often desirable to

constrain the size of the discovered results in order to directly control the

associated costs. In this report, we address the problem of finding

cardinality-constrained connected

subtrees from large node-weighted graphs that maximize the sum of weights of

selected nodes. We provide an efficient constant-factor approximation algorithm

for this strongly NP-hard problem. Our techniques can be applied in a wide

variety

of application settings, for example in differential analysis of graphs, a

problem that frequently arises in bioinformatics but also has applications on

the web.

Initially used in digital audio players, digital cameras, mobile

phones, and USB memory sticks, flash memory may become the dominant

form of end-user storage in mobile computing, either completely

replacing the magnetic hard disks or being an additional secondary

storage. We study the design of algorithms and data structures that

can exploit the flash memory devices better. For this, we characterize

the performance of NAND flash based storage devices, including many

solid state disks. We show that these devices have better random read

performance than hard disks, but much worse random write performance.

We also analyze the effect of misalignments, aging and past I/O

patterns etc. on the performance obtained on these devices. We show

that despite the similarities between flash memory and RAM (fast

random reads) and between flash disk and hard disk (both are block

based devices), the algorithms designed in the RAM model or the

external memory model do not realize the full potential of the flash

memory devices. We later give some broad guidelines for designing

algorithms which can exploit the comparative advantages of both a

flash memory device and a hard disk, when used together.

In this report we describe the current progress with respect to prototype

implementations of algebraic kernels within the ACS project. More specifically,

we report on: (1) the Cgal package Algebraic_kernel_for_circles_2_2 aimed at

providing the necessary algebraic functionality required for treating circular

arcs; (2) an interface between Cgal and SYNAPS for accessing the algebraic

functionality in the SYNAPS library; (3) the NumeriX library (part of the

EXACUS project) which is a prototype implementation of a set of algebraic tools

on univariate polynomials, needed to built an algebraic kernel and (4) a rough

CGAL-like prototype implementation of a set of algebraic tools on univariate

polynomials.

We present a branch-and-bound (bb) algorithm for the multiple sequence

alignment

problem (MSA), one of the most important problems in computational

biology. The

upper bound at each bb node is based on a Lagrangian relaxation of an

integer linear programming formulation for MSA. Dualizing certain

inequalities, the Lagrangian subproblem becomes a pairwise alignment

problem, which

can be solved efficiently by a dynamic programming approach. Due to a

reformulation

w.r.t. additionally introduced variables prior to relaxation we improve

the convergence

rate dramatically while at the same time being able to solve the

Lagrangian problem efficiently.

Our experiments show that our implementation, although preliminary,

outperforms all exact

algorithms for the multiple sequence alignment problem.

This paper presents the synchronization in LFthreads, a thread library

entirely based on lock-free methods, i.e. no

spin-locks or similar synchronization mechanisms are employed in the

implementation of the multithreading.

Since lock-freedom is highly desirable in multiprocessors/multicores

due to its advantages in parallelism, fault-tolerance,

convoy-avoidance and more, there is an increased demand in lock-free

methods in parallel applications, hence also in multiprocessor/multicore

system services. This is why a lock-free

multithreading library is important. To the best of our knowledge

LFthreads is the first thread library that provides a lock-free

implementation

of blocking synchronization primitives for application threads.

Lock-free implementation of objects with blocking semantics may sound like

a contradicting goal. However, such objects have benefits:

e.g. library operations that block and unblock threads on the same

synchronization object can make progress in parallel while maintaining

the desired thread-level semantics

and without having to wait for any ``slow'' operations among them.

Besides, as no spin-locks or similar synchronization mechanisms are employed,

processors are always able to do useful work. As a consequence,

applications, too, can enjoy enhanced parallelism and fault-tolerance.

The synchronization in LFthreads is achieved by a new method, which

we call responsibility hand-off (RHO), that does not need any

special kernel support.

We consider the following autocompletion search scenario: imagine a user

of a search engine typing a query; then with every keystroke display those

completions of the last query word that would lead to the best hits, and

also display the best such hits. The following problem is at the core of

this feature: for a fixed document collection, given a set $D$ of

documents, and an alphabetical range $W$ of words, compute the set of all

word-in-document pairs $(w,d)$ from the collection such that $w \in W$

and $d\in D$.

We present a new data structure with the help of which such

autocompletion queries can be processed, on the average, in time linear

in the input plus output size, independent of the size of the underlying

document collection. At the same time, our data structure uses no more

space than an inverted index. Actual query processing times on a large test collection

correlate almost perfectly with our theoretical bound.

Top-k query processing is an important building block for ranked retrieval,

with applications ranging from text and data integration to distributed

aggregation of network logs and sensor data.

Top-k queries operate on index lists for a query's elementary conditions

and aggregate scores for result candidates. One of the best implementation

methods in this setting is the family of threshold algorithms, which aim

to terminate the index scans as early as possible based on lower and upper

bounds for the final scores of result candidates. This procedure

performs sequential disk accesses for sorted index scans, but also has the option

of performing random accesses to resolve score uncertainty. This entails

scheduling for the two kinds of accesses: 1) the prioritization of different

index lists in the sequential accesses, and 2) the decision on when to perform

random accesses and for which candidates.

The prior literature has studied some of these scheduling issues, but only for each of the two access types in isolation.

The current paper takes an integrated view of the scheduling issues and develops

novel strategies that outperform prior proposals by a large margin.

Our main contributions are new, principled, scheduling methods based on a Knapsack-related

optimization for sequential accesses and a cost model for random accesses.

The methods can be further boosted by harnessing probabilistic estimators for scores,

selectivities, and index list correlations.

We also discuss efficient implementation techniques for the

underlying data structures.

In performance experiments with three different datasets (TREC Terabyte, HTTP server logs, and IMDB),

our methods achieved significant performance gains compared to the best previously known methods:

a factor of up to 3 in terms of execution costs, and a factor of 5

in terms of absolute run-times of our implementation.

Our best techniques are close to a lower bound for the execution cost of the considered class

of threshold algorithms.

We provide a deterministic algorithm that constructs small point sets

exhibiting a low star discrepancy. The algorithm is based on bracketing and on

recent results on randomized roundings respecting hard constraints. It is

structurally much simpler than the previous algorithm presented for this

problem in [B. Doerr, M. Gnewuch, A. Srivastav. Bounds and constructions for

the star discrepancy via -covers. J. Complexity, 21: 691-709, 2005]. Besides

leading to better theoretical run time bounds, our approach can be implemented

with reasonable effort.

We show that the duality of a pair of monotone Boolean functions in disjunctive

normal forms can be tested in polylogarithmic time using a quasi-polynomial

number of processors. Our decomposition technique yields stronger bounds on the

complexity of the problem than those currently known and also allows for

generating all minimal transversals of a given hypergraph using only polynomial

space.

A fundamental class of problems in wireless communication is concerned

with the assignment of suitable transmission powers to wireless

devices/stations such that the

resulting communication graph satisfies certain desired properties and

the overall energy consumed is minimized. Many concrete communication

tasks in a

wireless network like broadcast, multicast, point-to-point routing,

creation of a communication backbone, etc. can be regarded as such a

power assignment problem.

This paper considers several problems of that kind; for example one

problem studied before in (Vittorio Bil{\`o} et al: Geometric Clustering

to Minimize the Sum

of Cluster Sizes, ESA 2005) and (Helmut Alt et al.: Minimum-cost

coverage of point sets by disks, SCG 2006) aims to select and assign

powers to $k$ of the

stations such that all other stations are within reach of at least one

of the selected stations. We improve the running time for obtaining a

$(1+\epsilon)$-approximate

solution for this problem from $n^{((\alpha/\epsilon)^{O(d)})}$ as

reported by Bil{\`o} et al. (see Vittorio Bil{\`o} et al: Geometric

Clustering to Minimize the Sum

of Cluster Sizes, ESA 2005) to

$O\left( n+ {\left(\frac{k^{2d+1}}{\epsilon^d}\right)}^{ \min{\{\;

2k,\;\; (\alpha/\epsilon)^{O(d)} \;\}} } \right)$ that is, we obtain a

running time that is \emph{linear}

in the network size. Further results include a constant approximation

algorithm for the TSP problem under squared (non-metric!) edge costs,

which can be employed to

implement a novel data aggregation protocol, as well as efficient

schemes to perform $k$-hop multicasts.

We present an algorithm to compute the subresultant sequence of two polynomials that completely avoids division in the ground domain, generalizing an algorithm from Abdeljaoued et al.\ (see Abdeljaoed et al.: Minors of Bezout Matrices\ldots, Int.\ J.\ of Comp.\ Math.\ 81, 2004). This is done by evaluating determinants of slightly manipulated Bezout matrices using an algorithm of Berkowitz. Experiments show that our algorithm is superior compared to pseudo-division approaches for moderate degrees if the domain contains indeterminates.

The all-pairs approximate shortest-paths problem is an interesting

variant of the classical all-pairs shortest-paths problem in graphs.

The problem aims at building a data-structure for a given graph

with the following two features. Firstly, for any two vertices,

it should report an {\emph{approximate}} shortest path between them,

that is, a path which is longer than the shortest path

by some {\emph{small}} factor. Secondly, the data-structure should require

less preprocessing time (strictly sub-cubic) and occupy optimal space

(sub-quadratic), at the cost of this approximation.

In this paper, we present algorithms for computing all-pairs approximate

shortest paths in a weighted undirected graph. These algorithms significantly

improve the existing results for this problem.

Point samples of a surface in $\R^3$ are the dominant output of a

multitude of 3D scanning devices. The usefulness of these devices rests on

being able to extract properties of the surface from the sample. We show that, under

certain sampling conditions, the minimum cycle basis of a nearest neighbor graph of

the sample encodes topological information about the surface and yields bases for the

trivial and non-trivial loops of the surface. We validate our results by experiments.

Given a digraph $G = (V,E)$ with a set $U$ of vertices marked

``interesting,'' we want to find a smaller digraph $\RS{} = (V',E')$

with $V' \supseteq U$ in such a way that the reachabilities amongst

those interesting vertices in $G$ and \RS{} are the same. So with

respect to the reachability relations within $U$, the digraph \RS{}

is a substitute for $G$.

We show that while almost all graphs do not have reachability

substitutes smaller than $\Ohmega(|U|^2/\log |U|)$, every planar

graph has a reachability substitute of size $\Oh(|U| \log^2 |U|)$.

Our result rests on two new structural results for planar

dags, a separation procedure and a reachability theorem, which

might be of independent interest.

Let $A=\langle a_1,\dots,a_n\rangle$ and

$B=\langle b_1,\dots,b_m \rangle$ be two sequences with $m \ge n$,

whose elements are drawn from a totally ordered set.

We present an algorithm that finds a longest

common increasing subsequence of $A$ and $B$ in $O(m\log m+n\ell\log n)$

time and $O(m + n\ell)$ space, where $\ell$ is the length of the output.

A previous algorithm by Yang et al. needs $\Theta(mn)$ time and space,

so ours is faster for a wide range of values of $m,n$ and $\ell$.

Given a bipartite graph $G( V, E)$, $ V = A \disjointcup B$

where $|V|=n, |E|=m$ and a partition of the edge set into

$r \le m$ disjoint subsets $E = E_1 \disjointcup E_2

\disjointcup \dots \disjointcup E_r$, which are called ranks,

the {\em rank-maximal matching} problem is to find a matching $M$

of $G$ such that $|M \cap E_1|$ is maximized and given that

$|M \cap E_2|$, and so on. Such a problem arises as an optimization

criteria over a possible assignment of a set of applicants to a

set of posts. The matching represents the assignment and the

ranks on the edges correspond to a ranking on the posts submitted

by the applicants.

The rank-maximal matching problem has been previously

studied where a $O( r \sqrt n m )$ time and linear

space algorithm~\cite{IKMMP} was

presented. In this paper we present a new simpler algorithm which

matches the running time and space complexity of the above

algorithm.

The new algorithm is based on a different approach,

by exploiting that the rank-maximal matching problem can

be reduced to a maximum weight matching problem where the

weight of an edge of rank $i$ is $2^{ \ceil{\log n} (r-i)}$.

By exploiting that these edge weights are steeply distributed

we design a scaling algorithm which scales by a factor of

$n$ in each phase. We also show that in each phase one

maximum cardinality computation is sufficient to get a new

optimal solution.

This algorithm answers an open question raised on the same

paper on whether the reduction to the maximum-weight matching

problem can help us derive an efficient algorithm.

We present two $\twothirds - \epsilon$ approximation algorithms for the

maximum weight matching problem that run in time

$O(m\log\frac{1}{\epsilon})$. We give a simple and practical

randomized algorithm and a somewhat more complicated deterministic

algorithm. Both algorithms are exponentially faster in

terms of $\epsilon$ than a recent algorithm by Drake and Hougardy.

We also show that our algorithms can be generalized to find a

$1-\epsilon$ approximatation to the maximum weight matching, for any

$\epsilon>0$.

We present two theoretically interesting and empirically successful

techniques for improving the linear programming approaches, namely

graph transformation and local cuts, in the context of the

Steiner problem. We show the impact of these techniques on the

solution of the largest benchmark instances ever solved.

In this paper, we present the first average-case analysis proving an expected

polynomial running time for an exact algorithm for the 0/1 knapsack problem.

In particular, we prove, for various input distributions, that the number of

{\em dominating solutions\/} (i.e., Pareto-optimal knapsack fillings)

to this problem is polynomially bounded in the number of available items.

An algorithm by Nemhauser and Ullmann can enumerate these solutions very

efficiently so that a polynomial upper bound on the number of dominating

solutions implies an algorithm with expected polynomial running time.

The random input model underlying our analysis is very general

and not restricted to a particular input distribution. We assume adversarial

weights and randomly drawn profits (or vice versa). Our analysis covers

general probability

distributions with finite mean, and, in its most general form, can even

handle different probability distributions for the profits of different items.

This feature enables us to study the effects of correlations between profits

and weights. Our analysis confirms and explains practical studies showing

that so-called strongly correlated instances are harder to solve than

weakly correlated ones.

Let $G$ be a simple graph on $n$ vertices. A conjecture of

Bollob\'as and Eldridge~\cite{be78} asserts that if $\delta (G)\ge {kn-1 \over

k+1}$

then $G$ contains any $n$ vertex graph $H$ with $\Delta(H) = k$.

We strengthen this conjecture: we prove that if $H$ is bipartite,

$3 \le \Delta(H)$ is bounded and $n$ is sufficiently large , then there exists

$\beta >0$ such that if $\delta (G)\ge {\Delta \over {\Delta +1}}(1-\beta)n$,

then

$H \subset G$.

In a simple graph $G$ without isolated nodes the

following random experiment is carried out:

each node chooses one

of its neighbors uniformly at random.

We say a rendezvous occurs

if there are adjacent nodes $u$ and $v$

such that $u$ chooses $v$

and $v$ chooses $u$;

the probability that this happens is denoted by $s(G)$.

M{\'e}tivier \emph{et al.} (2000) asked

whether it is true

that $s(G)\ge s(K_n)$

for all $n$-node graphs $G$,

where $K_n$ is the complete graph on $n$ nodes.

We show that this is the case.

Moreover, we show that evaluating $s(G)$

for a given graph $G$ is a \numberP-complete problem,

even if only $d$-regular graphs are considered,

for any $d\ge5$.

We describe a simple randomized construction for generating pairs of

hash functions h_1,h_2 from a universe U to ranges V=[m]={0,1,...,m-1}

and W=[m] so that for every key set S\subseteq U with

n=|S| <= m/(1+epsilon) the (random) bipartite (multi)graph with node

set V + W and edge set {(h_1(x),h_2(x)) | x in S} exhibits a structure

that is essentially random. The construction combines d-wise

independent classes for d a relatively small constant with the

well-known technique of random offsets. While keeping the space

needed to store the description of h_1 and h_2 at O(n^zeta), for

zeta<1 fixed arbitrarily, we obtain a much smaller (constant)

evaluation time than previous constructions of this kind, which

involved Siegel's high-performance hash classes. The main new

technique is the combined analysis of the graph structure and the

inner structure of the hash functions, as well as a new way of looking

at the cycle structure of random (multi)graphs. The construction may

be applied to improve on Pagh and Rodler's ``cuckoo hashing'' (2001),

to obtain a simpler and faster alternative to a recent construction of

"Ostlin and Pagh (2002/03) for simulating uniform hashing on a key set

S, and to the simulation of shared memory on distributed memory

machines. We also describe a novel way of implementing (approximate)

d-wise independent hashing without using polynomials.

We show an algorithm for bound consistency of {\em global cardinality

constraints}, which runs in time $O(n+n')$ plus the time required to sort

the

assignment variables by range endpoints, where $n$ is the number of

assignment

variables and $n'$ is the number of values in the union of their ranges.

We

thus offer a fast alternative to R\'egin's

arc consistency algorithm~\cite{Regin} which runs

in time $O(n^{3/2}n')$ and space $O(n\cdot n')$. Our algorithm

also achieves bound consistency for the number of occurrences

of each value, which has not been done before.

The question, whether the preemptive Sum Multicoloring (pSMC)

problem is hard on paths was raised by Halldorsson

et al. ["Multi-coloring trees", Information and Computation,

180(2):113-129,2002]. The pSMC problem is a scheduling problem where the

pairwise conflicting jobs are represented by a conflict graph, and the

time lengths of jobs by integer weights on the nodes. The goal is to

schedule the jobs so that the sum of their finishing times is

minimized. In the paper we give an O(n^3p) time algorithm

for the pSMC problem on paths, where n is the number of nodes and p is

the largest time length. The result easily carries over to cycles.

We study the price of selfish routing in non-cooperative

networks like the Internet. In particular, we investigate the

price of selfish routing using the coordination ratio and

other (e.g., bicriteria) measures in the recently introduced game

theoretic network model of Koutsoupias and Papadimitriou. We generalize

this model towards general, monotone families of cost functions and

cost functions from queueing theory. A summary of our main results

for general, monotone cost functions is as follows.

We investigate variants of the well studied problem of scheduling

tasks on uniformly related machines to minimize the makespan.

In the $k$-splittable scheduling problem each task can be broken into

at most $k \ge 2$ pieces each of which has to be assigned to a different

machine. In the slightly more general SAC problem each task $j$ comes with

its own splittability parameter $k_j$, where we assume $k_j \ge 2$.

These problems are known to be $\npc$-hard and, hence, previous

research mainly focuses on approximation algorithms.

Our motivation to study these scheduling problems is traffic allocation

for server farms based on a variant of the Internet Domain Name Service

(DNS) that uses a stochastic splitting of request streams. Optimal

solutions for the $k$-splittable scheduling problem yield optimal

solutions for this traffic allocation problem. Approximation ratios,

however, do not translate from one problem to the other because of

non-linear latency functions. In fact, we can prove that the traffic

allocation problem with standard latency functions from Queueing Theory

cannot be approximated in polynomial time within any finite factor

because of the extreme behavior of these functions.

Because of the inapproximability, we turn our attention to fixed-parameter

tractable algorithms. Our main result is a polynomial time algorithm

computing an exact solution for the $k$-splittable scheduling problem as

well as the SAC problem for any fixed number of machines.

The running time of our algorithm increases exponentially with the

number of machines but is only linear in the number of tasks.

This result is the first proof that bounded splittability reduces

the complexity of scheduling as the unsplittable scheduling is known

to be $\npc$-hard already for two machines. Furthermore, since our

algorithm solves the scheduling problem exactly, it also solves the

traffic allocation problem that motivated our study.

We develop an algorithm for parallel disk sorting, whose I/O cost

approaches the lower bound and that guarantees almost perfect

overlap between I/O and computation. Previous algorithms have

either suboptimal I/O volume or cannot guarantee that I/O and

computations can always be overlapped. We give an efficient

implementation that can (at least) compete with the best practical

implementations but gives additional performance guarantees.

For the experiments we have configured a state of the art machine

that can sustain full bandwidth I/O with eight disks and is very cost

effective.

The famous max-flow min-cut theorem states that a source node $s$ can

send information through a network (V,E) to a sink node t at a

rate determined by the min-cut separating s and t. Recently it

has been shown that this rate can also be achieved for multicasting to

several sinks provided that the intermediate nodes are allowed to

reencode the information they receive. We give

polynomial time algorithms for solving this problem. We additionally

underline the potential benefit of coding by showing that multicasting

without coding sometimes only allows a rate that is a factor

Omega(log |V|) smaller.

We present cost sharing methods for connected facility location

games that are cross-monotonic, competitive, and recover a constant

fraction of the cost of the constructed solution.

The novelty of this paper is that we use randomized algorithms, and

that we share the expected cost among the participating users.

As a consequence, our cost sharing methods are simple, and achieve

attractive approximation ratios for various NP-hard problems.

We also provide a primal-dual cost sharing method for the connected

facility location game with opening costs.

We consider online problems that can be modeled as \emph{metrical

task systems}:

An online algorithm resides in a graph $G$ of $n$ nodes and may move

in this graph at a cost equal to the distance.

The algorithm has to service a sequence of \emph{tasks} that arrive

online; each task specifies for each node a \emph{request cost} that

is incurred if the algorithm services the task in this particular node.

The objective is to minimize the total request cost plus the total

travel cost.

Several important online problems can be modeled as metrical task

systems.

Borodin, Linial and Saks \cite{BLS92} presented a deterministic

\emph{work function algorithm} (WFA) for metrical task systems

having a tight competitive ratio of $2n-1$.

However, the competitive ratio often is an over-pessimistic

estimation of the true performance of an online algorithm.

In this paper, we present a \emph{smoothed competitive analysis}

of WFA.

Given an adversarial task sequence, we smoothen the request costs

by means of a symmetric additive smoothing model and analyze the

competitive ratio of WFA on the smoothed task sequence.

Our analysis reveals that the smoothed competitive ratio of WFA

is much better than $O(n)$ and that it depends on several

topological parameters of the underlying graph $G$, such as

the minimum edge length $U_{\min}$, the maximum degree $D$,

and the edge diameter $diam$.

Assuming that the ratio between the maximum and the minimum edge length

of $G$ is bounded by a constant, the smoothed competitive ratio of WFA

becomes $O(diam (U_{\min}/\sigma + \log(D)))$ and

$O(\sqrt{n \cdot (U_{\min}/\sigma + \log(D))})$, where

$\sigma$ denotes the standard deviation of the smoothing distribution.

For example, already for perturbations with $\sigma = \Theta(U_{\min})$

the competitive ratio reduces to $O(\log n)$ on a clique and to

$O(\sqrt{n})$ on a line.

We also prove that for a large class of graphs these bounds are

asymptotically tight.

Furthermore, we provide two lower bounds for any arbitrary graph.

We obtain a better bound of

$O(\beta \cdot (U_{\min}/\psigma + \log(D)))$ on

the smoothed competitive ratio of WFA if each adversarial

task contains at most $\beta$ non-zero entries.

Our analysis holds for various probability distributions,

including the uniform and the normal distribution.

We also provide the first average case analysis of WFA.

We prove that WFA has $O(\log(D))$ expected competitive

ratio if the request costs are chosen randomly from an arbitrary

non-increasing distribution with standard deviation.

Banderier, Beier and Mehlhorn showed that the single-source shortest

path problem has smoothed complexity $O(m+n(K-k))$ if the edge costs are

$K$-bit integers and the last $k$ least significant bits are perturbed

randomly. Their analysis holds if each bit is set to $0$ or $1$ with

probability $\frac{1}{2}$.

We extend their result and show that the same analysis goes through for

a large class of probability distributions:

We prove a smoothed complexity of $O(m+n(K-k))$ if the last $k$ bits of

each edge cost are replaced by some random number chosen from $[0,

\dots, 2^k-1]$ according to some \emph{arbitrary} probability

distribution $\pdist$ whose expectation is not too close to zero.

We do not require that the edge costs are perturbed independently.

The same time bound holds even if the random perturbations are

heterogeneous.

If $k=K$ our analysis implies a linear average case running time for

various probability distributions.

We also show that the running time is $O(m+n(K-k))$ with high

probability if the random replacements are chosen independently.

In this paper we introduce the notion of smoothed competitive analysis

of online algorithms. Smoothed analysis has been proposed by Spielman

and Teng [\emph{Smoothed analysis of algorithms: Why the simplex

algorithm usually takes polynomial time}, STOC, 2001] to explain the behaviour

of algorithms that work well in practice while performing very poorly

from a worst case analysis point of view.

We apply this notion to analyze the Multi-Level Feedback (MLF)

algorithm to minimize the total flow time on a sequence of jobs

released over time when the processing time of a job is only known at time of

completion.

The initial processing times are integers in the range $[1,2^K]$.

We use a partial bit randomization model, where the initial processing

times are smoothened by changing the $k$ least significant bits under

a quite general class of probability distributions.

We show that MLF admits a smoothed competitive ratio of

$O((2^k/\sigma)^3 + (2^k/\sigma)^2 2^{K-k})$, where $\sigma$ denotes

the standard deviation of the distribution.

In particular, we obtain a competitive ratio of $O(2^{K-k})$ if

$\sigma = \Theta(2^k)$.

We also prove an $\Omega(2^{K-k})$ lower bound for any deterministic

algorithm that is run on processing times smoothened according to the

partial bit randomization model.

For various other smoothening models, including the additive symmetric

smoothening model used by Spielman and Teng, we give a higher lower

bound of $\Omega(2^K)$.

A direct consequence of our result is also the first average case

analysis of MLF. We show a constant expected ratio of the total flow time of

MLF to the optimum under several distributions including the uniform

distribution.

Real algebraic numbers are real roots of polynomials with integral

coefficients. They can be represented as expressions whose

leaves are integers and whose internal nodes are additions, subtractions,

multiplications, divisions, k-th root operations for integral k,

or taking roots of polynomials whose coefficients are given by the value

of subexpressions. This last operator is called the diamond operator.

I explain the implementation of the diamond operator in a LEDA extension

package.

Let $G$ be a biconnected planar graph given together with its planar drawing.

A {\em face-vertex walk} in $G$ of length $k$

is an alternating sequence $x_0, \ldots x_k$ of

vertices and faces (i.e., if $x_{i - 1}$ is a face then $x_i$ is

a vertex and vice versa) such that $x_{i - 1}$ and $x_i$ are incident

with each other for $1 \leq i \leq k$.

For each vertex or face $x$ of $G$, let $\alpha_x$ denote

the length of the shortest face-vertex walk from the outer face of $G$ to $x$.

Let $\alpha_G$ denote the maximum of $\alpha_x$ over all vertices/faces $x$.

We show that there always exits a branch-decomposition of $G$ with width

$\alpha_G$ and that such a decomposition

can be constructed in linear time. We also give experimental results,

in which we compare the width of our decomposition with the optimal

width and with the width obtained by some heuristics for general

graphs proposed by previous researchers, on test instances used

by those researchers.

On 56 out of the total 59 test instances, our

method gives a decomposition within additive 2 of the optimum width and

on 33 instances it achieves the optimum width.

A strategy of merging several traveling salesman tours

into a better tour, called ACC (Alternating Cycles Contribution)

is introduced. Two algorithms embodying this strategy for

geometric instances is

implemented and used to enhance Helsgaun's implementaton

of his variant of the Lin-Kernighan heuristic. Experiments

on the large instances in TSPLIB show that a significant

improvement of performance is obtained.

These algorithms were used in September 2002 to find a

new best tour for the largest instance pla85900

in TSPLIB.

This article introduces the sum of weights of distinct values

constraint, which can be seen as a generalization of the number of

distinct values as well as of the alldifferent, and the relaxed

alldifferent constraints. This constraint holds if a cost variable is

equal to the sum of the weights associated to the distinct values taken

by a given set of variables. For the first aspect, which is related to

domination, we present four filtering algorithms. Two of them lead to

perfect pruning when each domain variable consists of one set of

consecutive values, while the two others take advantage of holes in the

domains. For the second aspect, which is connected to maximum matching

in a bipartite graph, we provide a complete filtering algorithm for the

general case. Finally we introduce several generic deduction rules,

which link both aspects of the constraint. These rules can be applied to

other optimization constraints such as the minimum weight alldifferent

constraint or the global cardinality constraint with costs. They also

allow taking into account external constraints for getting enhanced

bounds for the cost variable. In practice, the sum of weights of

distinct values constraint occurs in assignment problems where using a

resource once or several times costs the same. It also captures

domination problems where one has to select a set of vertices in order

to control every vertex of a graph.

A method is presented to compute the planar arrangement

induced by segments of algebraic curves of degree three

(or less), using an improved Bentley-Ottmann sweep-line

algorithm. Our method is exact (it provides the

mathematically correct result), complete (it handles

all possible geometric degeneracies), and efficient

(the implementation can handle hundreds of segments).

The range of possible input segments comprises conic

arcs and cubic splines as special cases of particular

practical importance.

We describe a set of tools that support the running, documentation,

and evaluation of computational experiments. The tool set is designed

not only to make computational experimentation easier but also to support

good scientific practice by making results reproducable and more easily

comparable to others' results by automatically documenting the experimental

environment. The tools can be used separately or in concert and support

all manner of experiments (\textit{i.e.}, any executable can be an experiment).

The tools capitalize on the rich functionality available in Python

to provide extreme flexibility and ease of use, but one need know nothing

of Python to use the tools.

The uncapacitated facility location problem (UFLP) is a problem that has been studied intensively in operational

research. Recently a variety of new deterministic and heuristic approximation algorithms have evolved. In this paper,

we compare five new approaches to this problem - the JMS- and the MYZ-approximation algorithms, a version of local

search, a Tabu Search algorithm as well as a version of the Volume algorithm with randomized rounding. We compare

solution quality and running times on different standard benchmark instances. With these instances and additional

material a web page was set up, where the material used in this study is accessible.

We present a simple new algorithm for computing minimum spanning trees

that is more than two times faster than the best previously known

algorithms (for dense, ``difficult'' inputs). It is of conceptual interest

that the algorithm uses the property that the heaviest edge in a cycle can

be discarded. Previously this has only been exploited in asymptotically

optimal algorithms that are considered to be impractical. An additional

advantage is that the algorithm can greatly profit from pipelined memory

access. Hence, an implementation on a vector machine is up to 13 times

faster than previous algorithms. We outline additional refinements for

MSTs of implicitly defined graphs and the use of the central data

structure for querying the heaviest edge between two nodes in the MST.

The latter result is also interesting for sparse graphs.

For the Steiner tree problem in networks, we present a practical algorithm

that uses the fixed-parameter tractability of

the problem with respect to a certain width parameter closely

related to pathwidth. The running time of the algorithm is linear in

the number of vertices when the pathwidth is constant. Combining this

algorithm with our previous techniques, we can already profit from

small width in subgraphs of an instance. Integrating this

algorithm into our program package for the Steiner problem

accelerates the solution process on some groups of instances and

leads to a fast solution of

some previously unsolved benchmark instances.

We present an algorithm for all-to-all personalized

communication, in which every processor has an individual message to

deliver to every other processor. The machine model we consider is a

cluster of processing nodes where each node, possibly consisting of

several processors, can participate in only one communication

operation with another node at a time. The nodes may have different

numbers of processors. This general model is important for the

implementation of all-to-all communication in libraries such as MPI

where collective communication may take place over arbitrary subsets

of processors. The algorithm is simple and optimal up to an additive

term that is small if the total number of processors is large compared

to the maximal number of processors in a node.

We give a O(n^2 \over 3}\log{n})-competitive randomized k--server

algorithm when the underlying metric space is given by n equally spaced

points on a line. For n = k + o(k^{3 \over 2}/\log{k), this algorithm is

o(k)--competitive.

Geometric algorithms are based on geometric objects such as points,

lines and circles. The term \textit{kernel\/} refers to a collection

of representations for constant-size geometric objects and

operations on these representations. This paper describes how such a

geometry kernel can be designed and implemented in C++, having

special emphasis on adaptability, extensibility and efficiency. We

achieve these goals following the generic programming paradigm and

using templates as our tools. These ideas are realized and tested in

\cgal~\cite{svy-cgal}, the Computational Geometry Algorithms

Library.

The problem of finding the minimum size 2-connected subgraph is

a classical problem in network design. It is known to be NP-hard even on

cubic planar graphs and Max-SNP hard.

We study the generalization of this problem, where requirements of 1 or 2

edge or vertex disjoint paths are specified between every pair of vertices,

and the aim is to find a minimum subgraph satisfying these requirements.

For both problems we give $3/2$-approximation algorithms. This improves on

the straightforward $2$-approximation algorithms for these problems, and

generalizes earlier results for 2-connectivity.

We also give analyses of the classical local optimization heuristics for

these two network design problems.

The quest for a linear-time single-source shortest-path (SSSP) algorithm

on

directed graphs with positive edge weights is an ongoing hot research

topic. While Thorup recently found an ${\cal O}(n+m)$ time RAM algorithm

for undirected graphs with $n$ nodes, $m$ edges and integer edge weights

in

$\{0,\ldots, 2^w-1\}$ where $w$ denotes the word length, the currently

best time bound for directed sparse graphs on a RAM is

${\cal O}(n+m \cdot \log\log n)$.

In the present paper we study the average-case complexity of SSSP.

We give simple label-setting and label-correcting algorithms for

arbitrary directed graphs with random real edge weights

uniformly distributed in $\left[0,1\right]$ and show that they

need linear time ${\cal O}(n+m)$ with high probability.

A variant of the label-correcting approach also supports

parallelization.

Furthermore, we propose a general method to construct graphs with

random edge weights which incur large non-linear expected running times on

many traditional shortest-path algorithms.

A key ingredient of the most successful algorithms for the Steiner problem are reduction methods, i.e. methods to reduce the size of a given instance while preserving at least one optimal solution (or the

ability to efficiently reconstruct one). While classical reduction tests just inspected simple patterns (vertices or edges), recent and more sophisticated tests extend the scope of inspection to more general patterns (like

trees). In this paper, we present such an extended reduction test, which generalizes different tests in the literature. We use the new approach of combining alternative- and bound-based methods, which

substantially improves the impact of the tests. We also present several algorithmic improvements, especially for the computation of the needed information. The experimental results show a substantial improvement over previous methods using the idea of extension.

Partitioning is one of the basic ideas for designing efficient

algorithms, but on \NP-hard problems like the Steiner problem

straightforward application of the classical paradigms

for exploiting this idea rarely leads to empirically successful

algorithms. In this paper, we present a new approach which is based on

vertex separators. We show several contexts in which this

approach can be used profitably. Our approach is new in the sense that it

uses partitioning to design reduction methods. We introduce two such

methods; and show their impact empirically.

The state-of-the-art algorithms for geometric Steiner

problems use a two-phase approach based on full Steiner trees

(FSTs). The bottleneck of this approach is the second phase (FST

concatenation phase), in which an optimum Steiner tree is constructed

out of the FSTs generated in the first phase. The hitherto most

successful algorithm for this phase considers the FSTs as edges

of a hypergraph and is based on an LP-relaxation of the minimum spanning

tree in hypergraph (MSTH) problem. In this paper, we compare this

original and some new relaxations of this problem and show their

equivalence, and thereby refute a conjecture in the literature.

Since the second phase can also be formulated as a Steiner

problem in graphs, we clarify the relation of this MSTH-relaxation to

all classical relaxations of the Steiner problem.

Finally, we perform some experiments, both on the quality of the

relaxations and on FST-concatenation methods based on them,

leading to the surprising result that an algorithm of ours

which is designed for general

graphs is superior to the MSTH-approach.

A planar Nef polyhedron is any set that can be obtained from the open half-space by a finite number of set complement and set intersection operations. The set of Nef polyhedra is closed under the Boolean set operations. We describe a date structure that realizes two-dimensional Nef polyhedra and offers a large set of binary and unary set operations. The underlying set operations are realized by an efficient and complete algorithm for the overlay of two Nef polyhedra. The algorithm is efficient in the sense that its running time is bounded by the size of the inputs plus the size of the output times a logarithmic factor. The algorithm is complete in the sense that it can handle all inputs and requires no general position assumption. The seecond part of the algorithmic interface considers point location and ray shooting in planar subdivisions.

The implementation follows the generic programming paradigm in C++ and CGAL. Several concept interfaces are defined that allow the adaptation of the software by the means of traits classes. The described project is part of the CGAL libarary version 2.3.

Rigid--body docking approaches are not sufficient to predict the structure of a

protein complex from the unbound (native) structures of the two proteins.

Accounting for side chain flexibility is an important step towards fully

flexible protein docking. This work describes an approach that allows

conformational flexibility for the side chains while keeping the protein

backbone rigid. Starting from candidates created by a rigid--docking

algorithm, we demangle the side chains of the docking site, thus creating

reasonable approximations of the true complex structure. These structures are

ranked with respect to the binding free energy. We present two new techniques

for side chain demangling. Both approaches are based on a discrete

representation of the side chain conformational space by the use of a rotamer

library. This leads to a combinatorial optimization problem. For the solution

of this problem we propose a fast heuristic approach and an exact, albeit

slower, method that uses branch--\&--cut techniques. As a test set we use the

unbound structures of three proteases and the corresponding protein

inhibitors. For each of the examples, the highest--ranking conformation

produced was a good approximation of the true complex structure.

A refined heuristic for computing schedules for gossiping in the

telephone model is presented. The heuristic is fast: for a network

with n nodes and m edges, requiring R rounds for gossiping, the

running time is O(R n log(n) m) for all tested

classes of graphs. This moderate time consumption allows to compute

gossiping schedules for networks with more than 10,000 PUs and

100,000 connections. The heuristic is good: in practice the computed

schedules never exceed the optimum by more than a few rounds. The

heuristic is versatile: it can also be used for broadcasting and

more general information dispersion patterns. It can handle both the

unit-cost and the linear-cost model.

Actually, the heuristic is so good, that for CCC, shuffle-exchange,

butterfly de Bruijn, star and pancake networks the constructed

gossiping schedules are better than the best theoretically derived

ones. For example, for gossiping on a shuffle-exchange network with

2^{13} PUs, the former upper bound was 49 rounds, while our

heuristic finds a schedule requiring 31 rounds. Also for broadcasting

the heuristic improves on many formerly known results.

A second heuristic, works even better for CCC, butterfly, star and

pancake networks. For example, with this heuristic we found that

gossiping on a pancake network with 7! PUs can be performed in 15

rounds, 2 fewer than achieved by the best theoretical construction.

This second heuristic is less versatile than the first, but by

refined search techniques it can tackle even larger problems, the

main limitation being the storage capacity. Another advantage is that

the constructed schedules can be represented concisely.

In this paper, we present a randomized, online, space-efficient

algorithm for the general class of programs with synchronization

variables (such programs are produced by parallel programming

languages, like, e.g., Cool, ID, Sisal, Mul-T, OLDEN and Jade).

The algorithm achieves good locality and low scheduling overheads

for this general class of computations, by combining work-stealing

and depth-first scheduling.

More specifically, given a computation with work $T_1$,

depth $T_\infty$ and $\sigma$ synchronizations that its

execution requires space $S_1$ on a single-processor

computer, our algorithm achieves expected space

complexity at most $S_1 + O(PT_\infty \log (PT_\infty))$

and runs in an expected number of

$O(T_1/P + \sigma \log (PT_\infty)/P + T_\infty \log (PT_\infty))$

timesteps on a shared-memory, parallel machine with $P$ processors.

Moreover, for any $\varepsilon > 0$, the space complexity of our

algorithm is at most $S_1 + O(P(T_\infty + \ln (1/\varepsilon))

\log (P(T_\infty + \ln(P(T_\infty + \ln (1/\varepsilon))/\varepsilon))))$

with probability at least $1-\varepsilon$. Thus, even for values

of $\varepsilon$ as small as $e^{-T_\infty}$, the space complexity

of our algorithm is at most $S_1 + O(PT_\infty \log(PT_\infty))$,

with probability at least $1-e^{-T_\infty}$. The algorithm achieves

good locality and low scheduling overheads by automatically

increasing the granularity of the work scheduled on each

processor.

Our results combine and extend previous algorithms and

analysis techniques (published by Blelloch et. al [6]

and by Narlikar [26]). Our algorithm not only exhibits the

same good space complexity for the general class of programs

with synchronization variables as its deterministic analog

presented in [6], but it also achieves good locality and

low scheduling overhead as the algorithm presented in [26],

which however performs well only for the more restricted class

of nested parallel computations.

We prove a separation bound for a large class of algebraic expressions

specified by expression dags.

The bound applies to expressions whose leaves are integers

and whose internal nodes are additions, subtractions, multiplications,

divisions, $k$-th root operations for integral $k$, and taking roots of

polynomials whose coefficients are given by the values of subexpressions.

The (logarithm of the)

new bound depends linearly on the algebraic degree of the expression.

Previous bounds applied to a smaller class of expressions and did not

guarantee linear dependency.

\ignore{In~\cite{BFMS} the dependency was quadratic.

and in the Li-Yap bound~\cite{LY} the dependency is usually linear, but may be

even worse than quadratic.}

Many geometric algorithms that are usually formulated for points and

segments generalize easily to inputs also containing rays and lines.

The sweep algorithm for segment intersection is a prototypical

example. Implementations of such algorithms do, in general, not

extend easily. For example, segment endpoints cause events in sweep

line algorithms, but lines have no endpoints. We describe a general

technique, which we call infimaximal frames, for extending

implementations to inputs also containing rays and lines. The

technique can also be used to extend implementations of planar

subdivisions to subdivisions with many unbounded faces. We have used

the technique successfully in generalizing a sweep algorithm designed

for segments to rays and lines and also in an implementation of planar

Nef polyhedra.

Our implementation is based on concepts of generic programming in C++

and the geometric data types provided by the C++ Computational

Geometry Algorithms Library (CGAL).

In the next century, virtual laboratories will play a key role in

biotechnology. Computer experiments will not only replace

time-consuming and expensive real-world experiments, but they will also

provide insights that cannot be obtained using ``wet'' experiments.

The field that deals with the modeling of atoms, molecules, and their

reactions is called Molecular Modeling. The advent of

Life Sciences gave rise to numerous new developments in this

area. However, the implementation of new simulation tools is extremely

time-consuming. This is mainly due to the large amount of

supporting code ({\eg} for data import/export, visualization, and so on)

that is required in addition to the code necessary to implement the new idea. The

only way to reduce the development time is to reuse reliable code,

preferably using object-oriented approaches. We have designed and

implemented {\Ball}, the first object-oriented application framework for rapid

prototyping in Molecular Modeling. By the use

of the composite design pattern and polymorphism we were able to model

the multitude of complex biochemical concepts in a well-structured and

comprehensible class hierarchy, the {\Ball} kernel classes. The

isomorphism between the biochemical structures and the kernel classes

leads to an intuitive interface. Since {\Ball} was designed for rapid software

prototyping, ease of use and flexibility were our principal design

goals. Besides the kernel classes, {\Ball} provides fundamental

components for import/export of data in various file formats,

Molecular Mechanics simulations, three-dimensional visualization, and

more complex ones like a numerical solver for the Poisson-Boltzmann

equation. The usefulness of {\Ball} was shown by the

implementation of an algorithm that checks proteins for

similarity. Instead of the five months that an earlier implementation

took, we were able to implement it within a day using {\Ball}.

Writing a program for computing the Voronoi diagram of line segments

is a complex task. Not only there is an abundance of geometric cases

that have to be considered, but the problem is also numerically

difficult. Therefore it is very easy to make subtle programming errors.

In this paper we present a procedure that for a given set of sites $S$

and a candidate graph $G$ rigorously checks that $G$ is the correct

Voronoi diagram of line segments for $S$. Our procedure is particularly

efficient and simple to implement.

The construction of full-text indexes on very large text collections

is nowadays a hot problem. The suffix array [Manber-Myers,~1993] is

one of the most attractive full-text indexing data structures due to

its simplicity, space efficiency and powerful/fast search operations

supported. In this paper we analyze, both theoretically and

experimentally, the I/O-complexity and the working space of six

algorithms for constructing large suffix arrays. Three of them are

the state-of-the-art, the other three algorithms are our new

proposals. We perform a set of experiments based on three different

data sets (English texts, Amino-acid sequences and random texts) and

give a precise hierarchy of these algorithms according to their

working-space vs. construction-time tradeoff. Given the current

trends in model design~\cite{Farach-et-al,Vitter} and disk

technology~\cite{dahlin,Ruemmler-Wilkes}, we will pose particular

attention to differentiate between ``random'' and ``contiguous''

disk accesses, in order to reasonably explain some practical

I/O-phenomena which are related to the experimental behavior of

these algorithms and that would be otherwise meaningless in the

light of other simpler external-memory models.

At the best of our knowledge, this is the first study which provides

a wide spectrum of possible approaches to the construction of suffix

arrays in external memory, and thus it should be helpful to anyone

who is interested in building full-text indexes on very large text

collections.

Finally, we conclude our paper by addressing two other issues. The

former concerns with the problem of building word-indexes; we show

that our results can be successfully applied to this case too,

without any loss in efficiency and without compromising the

simplicity of programming so to achieve a uniform, simple and

efficient approach to both the two indexing models. The latter issue

is related to the intriguing and apparently counterintuitive

``contradiction'' between the effective practical performance of the

well-known BaezaYates-Gonnet-Snider's algorithm~\cite{book-info},

verified in our experiments, and its unappealing (i.e., cubic)

worst-case behavior. We devise a new external-memory algorithm that

follows the basic philosophy underlying that algorithm but in a

significantly different manner, thus resulting in a novel approach

which combines good worst-case bounds with efficient practical

performance.

This paper explains some implementation details of graph iterators and

data accessors in LEDA.

It shows how to create new iterators for new graph implementations such

that old algorithms can be re--used with new graph implementations as long

as they are based on graph iterators and data accessors.

By \emph{open--world design} we mean that collaborating classes are so

loosely coupled that changes in one class

do not propagate to the other classes, and single classes can be isolated

and integrated in other contexts. Of course, this is what maintainability

and reusability is all about.

In the paper, we will demonstrate that in Java even an open--world design of mere

attribute access can only be achieved if static

safety is sacrificed, and that this conflict is unresolvable \emph{even if the attribute

type is fixed}. With generic language extensions such as GJ, which is a generic extension

of Java, it is possible to combine static type safety and open--world design.

As a consequence, genericity should be viewed as a

first--class design feature, because generic language features are preferably applied

in many situations in which object--orientedness seems appropriate.

We chose Java as the base of the discussion because Java is commonly known and several

advanced features of Java aim at a loose coupling of classes.

In particular, the paper is intended to make a strong point

in favor of generic extensions of Java.

High performance applications involving large data sets require the

efficient and flexible use of multiple disks. In an external memory

machine with D parallel, independent disks, only one block can be

accessed on each disk in one I/O step. This restriction leads to a

load balancing problem that is perhaps the main inhibitor for the

efficient adaptation of single-disk external memory algorithms to

multiple disks. We show how this problem can be solved efficiently by

using randomization and redundancy. A buffer of O(D) blocks suffices

to support efficient writing of arbitrary blocks if blocks are

distributed uniformly at random to the disks (e.g., by hashing). If

two randomly allocated copies of each block exist, N arbitrary blocks

can be read within ceiling(N/D)+1 I/O steps with high probability.

The redundancy can be further reduced from 2 to 1+1/r for any integer

r. From the point of view of external memory models, these results

rehabilitate Aggarwal and Vitter's "single-disk multi-head" model that

allows access to D arbitrary blocks in each I/O step. This powerful

model can be emulated on the physically more realistic independent

disk model with small constant overhead factors. Parallel disk

external memory algorithms can therefore be developed in the

multi-head model first. The emulation result can then be applied

directly or further refinements can be added.

Two improved list-ranking algorithms are presented. The

``peeling-off'' algorithm leads to an optimal PRAM algorithm, but

was designed with application on a real parallel machine in mind.

It is simpler than earlier algorithms, and in a range of problem

sizes, where previously several algorithms where required for the

best performance, now this single algorithm suffices. If the problem

size is much larger than the number of available processors, then the

``sparse-ruling-sets'' algorithm is even better. In previous

versions this algorithm had very restricted practical application

because of the large number of communication rounds it was

performing. This main weakness of this algorithm is overcome by

adding two new ideas, each of which reduces the number of

communication rounds by a factor of two.

We investigate an online version of the scheduling problem

$P, NC|pmtn|C_{\max}$, where a set of jobs has to be scheduled

on a number of identical machines so as to minimize the makespan.

The job processing times are known in advance and preemption of

jobs is allowed. Machines are {\it non-continuously\/} available,

i.e., they can break down and recover at arbitrary time instances {\it not

known in advance}. New machines may be added as well. Thus machine

availabilities change online.

We first show that no online algorithm can construct optimal schedules.

We also show that no online algorithm can achieve a constant competitive

ratio if there may be time intervals where no machine is available.

Then we present an online algorithm that constructs schedules with an

optimal makespan of $C_{\max}^{OPT}$ if a {\it lookahead\/} of one is

given, i.e., the algorithm always knows the next point in time when

the set of available machines changes. Finally we give an online algorithm

without lookahead that constructs schedules with a nearly optimal makespan

of $C_{\max}^{OPT} + \epsilon$, for any $\epsilon >0$, if at any

time at least one machine is available. Our results

demonstrate that not knowing machine availabilities in advance is of

little harm.

Comparator networks for constructing binary heaps of size $n$ are

presented which have size $O(n\log\log n)$ and depth $O(\log n)$. A

lower bound of $n\log\log n-O(n)$ for the size of any heap

construction network is also proven, implying that the networks

presented are within a constant factor of optimal. We give a tight

relation between the leading constants in the size of selection

networks and in the size of heap constructiion networks.

We report on the use of the generic programming paradigm in the computational

geometry algorithms library CGAL. The parameterization of

the geometric algorithms in CGAL enhances flexibility and adaptability and

opens an easy way for abolishing precision and robustness problems by exact but

nevertheless efficient computation. Furthermore we discuss circulators, which

are an extension of the iterator concept to circular structures. Such structures

arise frequently in geometric computing.

With the increasing amount of DNA sequence information deposited in

our databases searching for similarity to a query sequence

has become a basic operation in molecular biology.

But even today's fast algorithms reach their limits when

applied to all-versus-all comparisons of large databases.

Here we present a new data base searching

algorithm dubbed QUASAR (Q-gram Alignment based on Suffix ARrays)

which was designed to quickly detect sequences with strong

similarity to the query in a context where many searches are

conducted on one database. Our algorithm applies a modification of

$q$-tuple filtering implemented on top of a suffix array. Two

versions were developed, one for a RAM resident suffix array and one

for access to the suffix array on disk. We compared our implementation

with BLAST and found that our approach is an order of magnitude faster.

It is, however, restricted to the search for strongly similar DNA

sequences as is typically required, e.g., in the context of clustering

expressed sequence tags (ESTs).

We solve the following problem.

For a given rational circle $C$ passing through the rational points

$p$, $q$, $r$ and a given angle $\alpha$, compute a rational point

on $C$ whose angle at $C$ differs from $\alpha$ by a value of

at most $\epsilon$.

In addition, try to minimize the bit length of the computed point.

This document contains the C++ program |rational_points_on_circle.c|.

We use the literate programming tool |noweb| by Norman Ramsey.

This document describes the LEDA program dc_delaunay.c

for computing Delaunay graphs by the divide-and-conquer method.

The program can be used either with exact primitives or with

non-exact primitives. It handles all cases of degeneracy

and is relatively robust against the use of imprecise arithmetic.

We use the literate programming tool noweb by Norman Ramsey.

We present a new recursive method for division with remainder of integers. Its

running time is $2K(n)+O(n \log n)$ for division of a $2n$-digit number by an

$n$-digit number where $K(n)$ is the Karatsuba multiplication time. It pays in p

ractice for numbers with 860 bits or more. Then we show how we can lower this bo

und to

$3/2 K(n)+O(n\log n)$ if we are not interested in the remainder.

As an application of division with remainder we show how to speedup modular

multiplication. We also give practical results of an implementation that allow u

s to say that we have the fastest integer division on a SPARC architecture compa

red to all other integer packages we know of.

We show that the well-known random incremental construction of

Clarkson and Shor can be adapted via {\it gradations}

to provide efficient external-memory algorithms for some geometric

problems. In particular, as the main result, we obtain an optimal

randomized algorithm for the problem of computing the trapezoidal

decomposition determined by a set of $N$ line segments in the plane

with $K$ pairwise intersections, that requires $\Theta(\frac{N}{B}

\log_{M/B} \frac{N}{B} +\frac{K}{B})$ expected disk accesses, where

$M$ is the size of the available internal memory and $B$ is the size

of the block transfer. The approach is sufficiently general to

obtain algorithms also for the problems of 3-d half-space

intersections, 2-d and 3-d convex hulls, 2-d abstract Voronoi

diagrams and batched planar point location, which require an optimal

expected number of disk accesses and are simpler than the ones

previously known. The results extend to an external-memory model

with multiple disks. Additionally, under reasonable conditions on

the parameters $N,M,B$, these results can be notably simplified

originating practical algorithms which still achieve optimal

expected bounds.

We report on the performance of a library

prototype for external memory algorithms and data structures called

LEDA-SM, where SM is an acronym for secondary memory. Our library

is based on LEDA and intended to complement it for large data. We

present performance results of our external memory library prototype

and compare these results with corresponding results of LEDAs

in-core algorithms in virtual memory. The results show that even if

only a small main memory is used for the external memory algorithms,

they always outperform their in-core counterpart. Furthermore we

compare different implementations of external memory data structures

and algorithms.

We study two notions of negative influence namely negative regression and

negative association. We show that if a set of symmetric binary random

variables are negatively regressed then they are necessarily negatively

associated. The proof uses a lemma that is of independent interest and

shows that every binary symmetric distribution has a variable of

``positive influence''. We also show that in general the notion of negative

regression is different from that of negative association.

CGAL is a Computational Geometry Algorithms Library written

in C++, which is developed in an ESPRIT LTR project. The goal

is to make the large body of geometric algorithms developed in the field of

computational geometry available for industrial application. In this chapter

we discuss the major design goals for CGAL, which are correctness,

flexibility, ease-of-use, efficiency, and robustness, and present our approach

to reach these goals. Templates and the relatively new generic programming

play a central role in the architecture of CGAL. We give a short

introduction to generic programming in C++, compare it to the

object-oriented programming paradigm, and present examples where

both paradigms are used effectively in CGAL.

Moreover, we give an overview on the current structure of the library

and consider software engineering aspects in the CGAL-project.

The robustness function of an optimization problem measures the maximum

change in the value of its optimal solution that can be produced by changes of

a given total magnitude on the values of the elements in its input. The

problem of computing the robustness function of matroid optimization problems is

studied under two cost models: the discrete model, which allows the

removal of elements from the input, and the continuous model, which

permits finite changes on the values of the elements in the input.

For the discrete model, an $O(\log k)$-approximation algorithm is presented

for computing the robustness function of minimum spanning trees, where $k$ is

the number of edges to be removed. The algorithm uses as key subroutine a

2-approximation algorithm for the problem of dividing a graph into the maximum

number of components by removing $k$ edges from it.

For the continuous model, a number of results are presented. First, a general

algorithm is given for computing the robustness function of any matroid. The

algorithm runs in strongly polynomial time on matroids with a strongly

polynomial time independence test. Faster algorithms are also presented for

some particular classes of matroids: (1) an $O(n^3m^2 \log (n^2/m))$-time

algorithm for graphic matroids, where $m$ is the number of elements in the

matroid and $n$ is its rank, (2) an $O(mn(m+n^2)|E|\log(m^2/|E|+2))$-time

algorithm for transversal matroids, where $|E|$ is a parameter of the matroid,

(3) an $O(m^2n^2)$-time algorithm for scheduling matroids, and (4) an

$O(m \log m)$-time algorithm for partition matroids. For this last class of

matroids an optimal algorithm is also presented for evaluating the robustness

function at a single point.

We study the problem of maintaining the distances and the shortest

paths from a source node in a directed graph with arbitrary arc

weights, when weight updates of arcs are performed. We propose

algorithms that work for any digraph and have optimal space

requirements and query time. If a negative--length cycle is introduced

during weight decrease operations it is detected by the algorithms. The

proposed algorithms explicitly deal with zero--length cycles. The cost

of update operations depends on the class of the considered digraph

and on the number of the output updates. We show that, if the digraph

has a $k$-bounded accounting function (as in the case of digraphs with

genus, arboricity, degree, treewidth or pagenumber bounded by $k$) the

update procedures require $O(k\cdot n\cdot \log n)$ worst case

time. In the case of digraphs with $n$ nodes and $m$ arcs

$k=O(\sqrt{m})$, and hence we obtain $O(\sqrt{m}\cdot n \cdot \log n)$

worst case time per operation, which is better for a factor of

$O(\sqrt{m} / \log n)$ than recomputing everything from scratch after

each input update.

If we perform also insertions and deletions of arcs all the above

bounds become amortized.

We consider the static dictionary problem of using

$O(n)$ $w$-bit words to store $n$ $w$-bit keys for

fast retrieval on a $w$-bit \ACz\ RAM, i.e., on a

RAM with a word length of $w$ bits whose

instruction set is arbitrary, except that each instruction

must be realizable through an unbounded-fanin circuit

of constant depth and $w^{O(1)}$ size, and that the

instruction set must be finite and independent of the

keys stored.

We improve the best known upper bounds

for moderate values of~$w$ relative to $n$.

If ${w/{\log n}}=(\log\log n)^{O(1)}$,

query time $(\log\log\log n)^{O(1)}$ is achieved, and if

additionally ${w/{\log n}}\ge(\log\log n)^{1+\epsilon}$

for some fixed $\epsilon>0$, the query time

is constant.

For both of these special cases, the best previous

upper bound was $O(\log\log n)$.

This paper studies the multicast routing and admission control problem

on unit-capacity tree and mesh topologies in the throughput-model.

The problem is a generalization of the edge-disjoint paths problem and

is NP-hard both on trees and meshes.

We study both the offline and the online version of the problem:

In the offline setting, we give the first constant-factor approximation

algorithm for trees, and an O((log log n)^2)-factor approximation algorithm

for meshes.

In the online setting, we give the first polylogarithmic competitive

online algorithm for tree and mesh topologies. No polylogarithmic-competitive

algorithm is possible on general network topologies [Bartal,Fiat,Leonardi, 96],

and there exists a polylogarithmic lower bound on the competitive ratio

of any online algorithm on tree topologies [Awerbuch,Azar,Fiat,Leighton, 96].

We prove the same lower bound for meshes.

We consider the problem of scheduling $n$ independent jobs on $m$ unrelated

parallel machines. Each job has to be processed by exactly one machine,

processing job $j$ on machine $i$ requires $p_{ij}$ time units, and the

objective is to minimize the makespan, i.e. the maximum job completion time.

We focus on the case when $m$ is fixed and develop a fully polynomial

approximation scheme whose running time depends only linearly on $n$. In the

second half of the paper we extend this result to a variant of the problem,

where processing job $j$ on machine $i$ also incurs a cost of $c_{ij}$, and

thus there are two optimization criteria: makespan and cost. We show that for

any fixed $m$, there is a fully polynomial approximation scheme that, given

values $T$ and $C$, computes for any fixed $\epsilon > 0$ a schedule in $O(n)$

time with makespan at most $(1+\epsilon)T$ and cost at most $(1 + \epsilon)C$,

if there exists a schedule of makespan $T$ and cost $C$.

In this paper, we give a characterization for parity graphs.

A graph is a parity graph, if and only if for every pair of vertices

all minimal chains joining them have the same parity. We prove

that $G$ is a parity graph, if and only if the cartesian product

$G \times K_2$ is a perfect graph.

Furthermore, as a consequence we get a result for the polyhedron

corresponding to an integer linear program formulation of a

coloring problem with costs. For the case that the costs $k_{v,3} = k_{v,c}$

for each color $c \ge 3$ and vertex $v \in V$, we show that the

polyhedron contains only

integral $0 / 1$ extrema if and only if the graph $G$ is a parity graph.

A malleable parallel task is one whose execution time is a function of the

number of (identical) processors alloted to it. We study the problem of

scheduling a set of $n$ independent malleable tasks on a fixed number of

parallel processors, and propose an approximation scheme that for any fixed

$\epsilon > 0$, computes in $O(n)$ time a non-preemptive schedule of length

at most $(1+\epsilon)$ times the optimum.

In this paper, we consider the mutual exclusion scheduling problem

for comparability graphs.

Given an undirected graph $G$ and a fixed constant $m$, the problem is to

find a minimum coloring of $G$ such that each color is used at most $m$

times. The complexity of this problem for comparability graphs was mentioned as an open problem

by M\"ohring (1985) and for permutation graphs (a

subclass of comparability graphs) as an open problem by Lonc (1991). We

prove that this problem is already NP-complete for permutation graphs and

for each fixed constant $m \ge 6$.

The problem of computing a maximal planar subgraph of a non planar graph has been deeply

investigated over the last 20 years. Several attempts have been tried to solve the problem

with the help of PQ-trees. The latest attempt has been reported by Jayakumar et al. [10].

In this paper we show that the algorithm presented by Jayakumar et al. is not correct. We

show that it does not necessarily compute a maximal planar subgraph and we note that the same

holds for a modified version of the algorithm presented by Kant [12]. Our conclusions most

likely suggest not to use PQ-trees at all for this specific problem.

We consider the two--dimensional compaction problem for orthogonal grid drawings in which the task is to alter the coordinates of the vertices and edge segments while preserving the shape of the drawing so that the total edge length is minimized. The problem is closely related to two--dimensional compaction in {\sc VLSI}--design and is conjectured to be {\sl NP}--hard.

We characterize the set of feasible solutions for the two--dimensional compaction problem in terms of paths in the so--called constraint graphs in $x$-- and $y$--direction. Similar graphs (known as {\em layout graphs}) have already been used for one--dimensional compaction in {\sc VLSI}--design, but this is the first time that a direct connection between these graphs is established. Given the pair of constraint graphs, the two--dimensional compaction task can be viewed as extending these graphs by new arcs so that certain conditions are satisfied and the total edge length is minimized. We can recognize those instances having only one such extension; for these cases we can solve the compaction problem in polynomial time.

We have transformed the geometrical problem into a graph--theoretical one which can

be formulated as an integer linear program. Our computational experiments have shown

that the new approach works well in practice. It is the first time that the two--dimensional

compaction problem is formulated as an integer linear program.

Orthogonal drawings of graphs are highly accepted in practice. For planar

graphs with vertex degree of at most four, Tamassia gives a polynomial time

algorithm which computes a region preserving orthogonal grid embedding with the

minimum number of bends. However, the graphs arising in practical applications

rarely have bounded vertex degree. In order to cope with general planar

graphs, we introduce the quasi--orthogonal drawing model. In this model,

vertices are drawn on grid points, and edges follow the grid paths except around

vertices of high degree. Furthermore we present an extension of Tamassia's

algorithm that constructs quasi--orthogonal drawings. We compare the drawings

to those obtained using related approaches.

The achromatic number of a graph is the greatest number of colors in a

coloring of the vertices of the graph such that adjacent vertices get

distinct colors and for every pair of colors some

vertex of the first color and some vertex of the second color are adjacent.

The problem of computing this number is NP-complete for general graphs

as proved by Yannakakis and Gavril 1980. The problem is also NP-complete

for trees, that was proved by Cairnie and Edwards 1997.

Chaudhary and Vishwanathan 1997 gave recently a $7$-approximation

algorithm for this problem on trees, and an $O(\sqrt{n})$-approximation

algorithm for the problem on

graphs with girth (length of the shortest cycle) at least six.

We present the first $2$-approximation algorithm for the problem on trees.

This is a new algorithm based on different ideas than one by Chaudhary and

Vishwanathan 1997.

We then give a $1.15$-approximation algorithm for the problem on binary trees and a

$1.58$-approximation for the problem on trees of constant degree. We show that

the algorithms for constant degree trees can be implemented in linear time.

We also present the first $O(n^{3/8})$-approximation algorithm for the problem

on graphs with girth at least six.

Our algorithms are based on an interesting tree partitioning technique.

Moreover, we improve the lower bound of Farber {\em et al.} 1986

for the achromatic number of trees with degree bounded by three.

Near-optimal gossiping algorithms are given for two- and higher

dimensional tori. It is assumed that the amount of data each PU

contributes is so large that start-up time may be neglected.

For two-dimensional tori, a previous algorithm achieved optimality

in an intricate way, with a time-dependent routing pattern.

In all steps of our algorithms, the PUs forward the received

packets in the same way.

Optimizng Over All Combinatorial Embeddings of a Planar Graph".

We study the problem of optimizing over the set of all combinatorial

embeddings of a given planar graph. Our objective function prefers certain

cycles of $G$ as face cycles in the embedding. The motivation for studying

this problem arises in graph drawing, where the chosen embedding has an

important influence on the aesthetics of the drawing.

We characterize the set of all possible embeddings of a given biconnected

planar graph $G$ by means of a system of linear inequalities with

${0,1}$-variables corresponding to the set of those cycles in $G$ which can

appear in a combinatorial embedding. This system of linear inequalities can be

constructed recursively using the data structure of SPQR-trees and a new

splitting operation.

Our computational results on two benchmark sets of graphs are surprising: The

number of variables and constraints seems to grow only linearly with the size

of the graphs although the number of embeddings grows exponentially. For all

tested graphs (up to 500 vertices) and linear objective functions, the

resulting integer linear programs could be generated within 600 seconds and

solved within two seconds on a Sun Enterprise 10000 using CPLEX.

A method proposed by Wallace for the generation of normal random

variates is examined. His method works by transforming a pool

of numbers from the normal distribution into a new pool of number.

This is in contrast to almost all other known methods that transform one

or more variates from the uniform distribution into one or more

variates from the normal distribution. Unfortunately, a direct

implementation of Wallace's method has a serious flaw:

if consecutive numbers produced by this method are added, the

resulting variate, which should also be normally distributed,

will show a significant deviation from the expected behavior.

Wallace's method is analyzed with respect to this deficiency

and simple modifications are proposed that lead to variates of

better quality. It is argued that more randomness (that is,

more uniform random numbers) is needed in the transformation

process to improve the quality of the numbers generated.

However, an implementation of the modified method has

still small deviations from the expected behavior and its running

time is much higher than that of the original.

This is a preliminary version of a chapter that will appear in the

{\em Handbook on Computational Geometry}, edited by J.R.~Sack and

J.~Urrutia.

We give a survey on techniques that have been proposed and successfully used

to attack robustness and precision problems in the implementation of geometric

algorithms.

We present C{\tt ++}-implementations of some classical algorithms for

computing

extreme points of a set of points in two-dimensional space.

The template feature of C{\tt ++} is used to provide generic code, that

works with various point types and various implementations of the primitives

used in the extreme point computation. The parameterization makes the code

flexible and adaptable. The code can be used with primitives provided by the

CGAL-kernel,

primitives provided by LEDA, and others. The interfaces of the convex

hull functions are compliant to the Standard Template Library.

We study the problem of finding a spanning tree with maximum number of leaves.

We present a simple 2-approximation algorithm for the problem, improving on the

previous best performance ratio of 3 achieved by algorithms of Ravi and Lu. Our

algorithm can be implemented to run in linear time using simple data structures.

We also study the variant of the problem in which a given subset of vertices are

required to be leaves in the tree. We provide a 5/2-approximation algorithm for

this version of the problem

We study a classical problem in online scheduling. A sequence of jobs must be

scheduled on $m$ identical parallel machines. As each job arrives, its

processing time is known. The goal is to

minimize the makespan. Bartal, Fiat, Karloff and Vohra gave a

deterministic online algorithm that is 1.986-competitive.

Karger, Phillips and Torng generalized the

algorithm and proved an upper bound of 1.945. The best lower bound currently

known on the competitive ratio that can be

achieved by deterministic online algorithms

it equal to 1.837. In this paper we present an improved deterministic online

scheduling algorithm that is 1.923-competitive, for all $m\geq 2$.

The algorithm is based on a new scheduling strategy, i.e., it is not

a generalization of the approach by Bartal {\it et al}. Also, the algorithm

has a simple structure. Furthermore,

we develop a better lower bound. We prove that,

for general $m$, no deterministic online scheduling algorithm can be

better than \mbox{1.852-competitive}.

We consider exploration problems where a robot has to construct a

complete map of an unknown environment. We assume that the environment

is modeled by a directed,

strongly connected graph. The robot's task is to visit all nodes and

edges of the graph using the minimum number $R$ of edge traversals.

Koutsoupias~\cite{K} gave a lower bound for $R$ of $\Omega(d^2 m)$,

and Deng and Papadimitriou~\cite{DP}

showed an upper bound of $d^{O(d)} m$, where $m$

is the number edges in the graph and $d$ is the minimum number of

edges that have to be added to make the graph Eulerian.

We give the first sub-exponential algorithm for this exploration

problem, which achieves an upper bound of

$d^{O(\log d)} m$. We also show a matching lower bound of

$d^{\Omega(\log d)}m$ for our algorithm. Additionally, we give lower

bounds of $2^{\Omega(d)}m$, resp.\ $d^{\Omega(\log d)}m$

for various other natural exploration algorithms.

A graph drawing algorithm produces a layout of a graph in two- or three-dimensional space that should be readable and easy to understand.

Since the aesthetic criteria differ from one application area to another,

it is unlikely that a definition of the ``optimal drawing'' of a graph in

a strict mathematical sense exists. A large number of graph drawing algorithms

taking different aesthetic criteria into account have already been proposed.

In this paper we describe the design and implementation of the AGD--Library,

a library of {\bf A}lgorithms for {\bf G}raph {\bf D}rawing. The library

offers a broad range of existing algorithms for two-dimensional graph drawing

and tools for implementing new algorithms. The library is written in \CC using

the LEDA platform for combinatorial and geometric computing

(\cite{Mehlhorn-Naeher:CACM,LEDA-Manual}).

The algorithms are implemented independently of the underlying visualization

or graphics system by using a generic layout interface.

Most graph drawing algorithms place a set of restrictions on the

input graphs like planarity or biconnectivity. We provide a mechanism

for declaring this precondition for a particular algorithm and

checking it for potential input graphs. A drawing model can be

characterized by a set of properties of the drawing. We call these properties

the postcondition of the algorithm. There is support

for maintaining and retrieving the postcondition of an algorithm.

We discuss the implementation of network flow algorithms in floating point

arithmetic. We give an example to illustrate the difficulties that may arise

when floating point arithmetic is used without care. We describe an iterative

improvement scheme that can be put around any network flow algorithm for

integer capacities. The scheme carefully scales the capacities such that all

integers arising can be handled exactly using floating point arithmetic.

For $m \le 10^9$ and double precision floating

point arithmetic the number of iterations is always bounded by three and the

relative error in the flow value is at most $2^{-19}$. For $m \le 10^6$ and

double precision arithmetic the relative error after the first iteration is

bounded by $10^{-3}$.

Das Zeichnen von Graphen ist ein junges aufblühendes Gebiet der Informatik. Es befasst sich mit

Entwurf, Analyse, Implementierung und Evaluierung von neuen Algorithmen für ästhetisch schöne

Zeichnungen von Graphen.

Anhand von selektierten Anwendungsbeispielen, Problemstellungen und Lösungsansätzen wollen wir in

dieses noch relativ unbekannte Gebiet einführen und gleichzeitig einen Überblick über die

Aktivitäten und Ziele einer von der DFG im Rahmen des Schwerpunktprogramms "`Effiziente Algorithmen

für Diskrete Probleme und ihre Anwendungen"' geförderten Arbeitsgruppe aus Mitgliedern der

Universitäten Halle, Köln und Passau und des Max-Planck-Instituts für Informatik in

Saarbrücken geben.

We present a parallel priority queue that supports the following

operations in constant time: {\em parallel insertion\/} of a sequence of

elements ordered according to key,

{\em parallel decrease key\/} for a sequence of elements ordered

according to key, {\em deletion of the minimum key element},

as well as {\em deletion of an arbitrary element}. Our data structure is

the first to

support multi insertion and multi decrease key in constant time. The

priority queue can be implemented on the EREW PRAM, and can perform any

sequence of $n$ operations in $O(n)$ time and $O(m\log n)$ work,

$m$ being the total number of keys inserted and/or updated. A main

application is a parallel implementation of Dijkstra's algorithm for the

single-source shortest path problem, which runs in $O(n)$ time and

$O(m\log n)$ work on a CREW PRAM on graphs with $n$ vertices and $m$

edges. This is a logarithmic factor improvement in the running time

compared with previous approaches.

We consider the problem of implementing finger search trees on the

pointer machine, {\it i.e.}, how to maintain a sorted list such that

searching for an element $x$, starting the search at any arbitrary

element $f$ in the list, only requires logarithmic time in the

distance between $x$ and $f$ in the list.

We present the first pointer-based implementation of finger search

trees allowing new elements to be inserted at any arbitrary position

in the list in worst case constant time. Previously, the best known

insertion time on the pointer machine was $O(\log^* n)$, where $n$

is the total length of the list. On a unit-cost RAM, a constant

insertion time has been achieved by Dietz and Raman by using

standard techniques of packing small problem sizes into a constant

number of machine words.

Deletion of a list element is supported in $O(\log^* n)$ time, which

matches the previous best bounds. Our data structure requires linear

space.

The optimal $k$-restricted 2-factor problem consists of finding,

in a complete undirected graph $K_n$, a minimum cost 2-factor

(subgraph having degree 2 at every node) with all components having more

than $k$ nodes.

The problem is a relaxation of the well-known symmetric travelling

salesman problem, and is equivalent to it when $\frac{n}{2}\leq k\leq n-1$.

We study the $k$-restricted 2-factor polytope. We present a large

class of valid inequalities, called bipartition

inequalities, and describe some of their properties; some of

these results are new even for the travelling salesman polytope.

For the case $k=3$, the triangle-free 2-factor polytope,

we derive a necessary and sufficient condition for such inequalities

to be facet inducing.

In this paper, we generalize the {\em Ski-Rental Problem}

to the {\em Bahncardproblem} which is an online problem of

practical relevance for all travelers.

The Bahncard is a railway pass of the Deutsche Bundesbahn (the German

railway company) which entitles its holder to a 50\%\ price

reduction on nearly all train tickets.

It costs 240\thinspace DM, and it is valid for 12 months.

For the common traveler, the decision at which time to buy

a Bahncard is a typical online problem, because she usually does

not know when and where to she will travel next.

We show that the greedy algorithm applied by most travelers

and clerks at ticket offices is not better in the worst case

than the trivial algorithm which never buys a Bahncard.

We present two optimal deterministic online algorithms,

an optimistic one and and a pessimistic one.

We further give a lower bound for randomized online algorithms

and present an algorithm which we conjecture to be optimal;

a proof of the conjecture is given for a special case of the problem.

It turns out that the optimal competitive ratio only depends on

the price reduction factor (50\%\ for the German Bahncardproblem),

but does not depend on the price or validity period of a Bahncard.

This paper considers the problem of designing fast, approximate,

combinatorial algorithms for multicommodity flows and other fractional

packing problems. We provide a different approach to these problems

which yields faster and much simpler algorithms. In particular we

provide the first polynomial-time, combinatorial approximation algorithm

for

the fractional packing problem; in fact the running time of our

algorithm is

strongly polynomial. Our approach also allows us to substitute

shortest path computations for min-cost flow computations in computing

maximum concurrent flow and min-cost multicommodity flow; this yields

much

faster algorithms when the number of commodities is large.

The group Steiner tree problem is a generalization of the

Steiner tree problem where we are given several subsets (groups) of

vertices in

a weighted graph,

and the goal is to find a minimum-weight connected subgraph containing

at least one vertex from each group. The problem was introduced by

Reich and Widmayer and finds applications in VLSI design.

The group Steiner tree problem generalizes the set covering

problem, and is therefore at least as hard.

We give a randomized $O(\log^3 n \log k)$-approximation

algorithm for the group Steiner tree problem on an $n$-node graph, where

$k$ is the number of groups.The best previous performance guarantee was

$(1+\frac{\ln k}{2})\sqrt{k}$ (Bateman, Helvig, Robins and Zelikovsky).

Noting that the group Steiner problem also models the

network design problems with location-theoretic constraints studied by

Marathe, Ravi and Sundaram, our results also improve their bicriteria

approximation results. Similarly, we improve previous results by

Slav{\'\i}k on a tour version, called the errand scheduling problem.

We use the result of Bartal on probabilistic approximation of finite

metric spaces by tree metrics

to reduce the problem to one in a tree metric. To find a solution on a

tree,

we use a generalization of randomized rounding. Our approximation

guarantees

improve to $O(\log^2 n \log k)$ in the case of graphs that exclude

small minors by using a better alternative to Bartal's result on

probabilistic approximations of metrics induced by such graphs

(Konjevod, Ravi and Salman) -- this improvement is valid for the group

Steiner problem on planar graphs as well as on a set of points in the

2D-Euclidean case.

In this paper we report on results obtained by an implementation of a

2-approximation algorithm for edge separators in planar

graphs. For 374 out of the 435 instances the algorithm returned the optimum

solution. For the remaining instances the solution returned was never more

than 10.6\% away from the lower bound on the optimum separator. We also

improve the worst-case running time of the algorithm from $O(n^6)$ to $O(n^5)$

and present techniques which improve the running time significantly in

practice.

We study integrated prefetching and caching problems following

the work of Cao et al. and Kimbrel and Karlin.

Cao et al. and Kimbrel and Karlin gave approximation algorithms

for minimizing the total elapsed time in single and

parallel disk settings. The total elapsed time is the sum of the processor

stall times and the length of the request sequence to be served.

We show that an optimum prefetching/caching schedule for a

single disk problem can be computed in polynomial time,

thereby settling an open question by Kimbrel and Karlin.

For the parallel disk problem we give an approximation algorithm for

minimizing stall time. Stall time is a more realistic and harder to

approximate measure for this problem. All of our algorithms are based on

a new approach which involves formulating the prefetching/caching problems

as integer programs.

Molecular dynamics simulation has become an important tool for testing

and developing hypotheses about chemical and physical processes. Since

the required amount of computing power is tremendous there is a strong

interest in parallel algorithms. We deal with efficient algorithms on

MIMD computers for

a special class of macromolecules, namely synthetic polymers, which play

a very important role in industry. This makes it worthwhile to design

fast parallel algorithms specifically for them. Contrary to existing

parallel algorithms, our algorithms take the structure of synthetic

polymers into account which allows faster simulation of their dynamics.

A number of erroneous attempts involving $PQ$-trees

in the context of automatic graph drawing algorithms have

been presented in the literature in recent years.

In order to prevent

future research from constructing algorithms with similar errors we

point out some of the major mistakes.

In particular, we examine erroneous usage of the $PQ$-tree data

structure in algorithms for computing maximal planar subgraphs and an

algorithm for testing leveled planarity of leveled directed acyclic

graphs with several sources and sinks.

We have developed and

implemented a parallel distributed algorithm for the

rigid-body protein docking problem. The algorithm is based on

a new fitness function for evaluating the surface matching

of a given conformation.

The fitness function is defined as the weighted sum

of two contact measures, the {\em geometric contact measure}

and the {\em chemical contact measure}.

The geometric contact measure measures the ``size'' of the

contact area of two molecules. It is a potential function

that counts the ``van der Waals contacts'' between the atoms of the

two molecules (the algorithm does not compute

the Lennard-Jones potential).

The chemical contact measure is also based

on the ``van der Waals contacts'' principle: We consider

all atom pairs that have a ``van der Waals'' contact,

but instead of adding a constant for each pair $(a,b)$ we add a

``chemical weight'' that depends on the atom pair $(a,b)$.

We tested our docking algorithm with a test set that contains

the test examples of Norel et al.~\cite{NLWN94} and

\protect{Fischer} et al.~\cite{FLWN95} and compared the results of our

docking algorithm with the results of Norel et al.~\cite{NLWN94,NLWN95},

with the results of Fischer et al.~\cite{FLWN95} and

with the results of Meyer et al.~\cite{MWS96}.

In 32 of 35 test examples the best conformation with respect

to the fitness function was an approximation of the real

conformation.

We consider the on-line problem of call admission and routing on

trees and meshes. Previous work considered randomized algorithms

and analyzed the {\em competitive ratio} of the algorithms.

However, these previous algorithms could obtain very low profit with

high probability.

We investigate the question if it is possible to devise on-line

competitive algorithms for these problems that would guarantee a ``good''

solution with ``good'' probability. We give a new family of

randomized algorithms with provably optimal (up to constant factors)

competitive ratios, and provably good probability to get a profit

close to the expectation. We also give lower bounds that show

bounds on how high the probability of such algorithms, to get a profit close

to the expectation, can be.

We also see

this work as a first step towards understanding

how well can the profit of an competitively-optimal randomized on-line

algorithm be concentrated around its expectation.

Multiple alignment is an important problem in computational biology. It is well known that it can be solved exactly by a dynamic programming algorithm which in turn can be interpreted as a shortest path computation in a directed acyclic graph. The $\cal{A}^*$ algorithm (or goal directed unidirectional search) is a technique that speeds up the computation of a shortest path by transforming the edge lengths without losing the optimality of the shortest path. We implemented the $\cal{A}^*$ algorithm in a computer program similar to MSA~\cite{GupKecSch95} and FMA~\cite{ShiIma97}. We incorporated in this program new bounding strategies for both, lower and upper bounds and show that the $\cal{A}^*$ algorithm, together with our improvements, can speed up comput ations considerably. Additionally we show that the $\cal{A}^*$ algorithm together with a standard bounding technique is superior to the well known Carillo-Lipman bounding since it excludes more nodes from consideration.

A common method for drawing directed graphs is, as a first step, to partition the

vertices into a set of $k$ levels and then, as a second step, to permute the verti

ces within the levels such that the number of crossings is minimized.

We suggest an alternative method for the second step, namely, removing the minimal

number of edges such that the resulting graph is $k$-level planar. For the final

diagram the removed edges are reinserted into a $k$-level planar drawing. Hence, i

nstead of considering the $k$-level crossing minimization problem, we suggest solv

ing the $k$-level planarization problem.

In this paper we address the case $k=2$. First, we give a motivation for our appro

ach.

Then, we address the problem of extracting a 2-level planar subgraph of maximum we

ight in a given 2-level graph. This problem is NP-hard. Based on a characterizatio

n of 2-level planar graphs, we give an integer linear programming formulation for

the 2-level planarization problem. Moreover, we define and investigate the polytop

e $\2LPS(G)$ associated with the set of all 2-level planar subgraphs of a given 2

-level graph $G$. We will see that this polytope has full dimension and that the i

nequalities occuring in the integer linear description are facet-defining for $\2L

PS(G)$.

The inequalities in the integer linear programming formulation can be separated in

polynomial time, hence they can be used efficiently in a branch-and-cut method fo

r solving practical instances of the 2-level planarization problem.

Furthermore, we derive new inequalities that substantially improve the quality of

the obtained

solution. We report on extensive computational results.

In this paper we examine the average running times of Batcher's bitonic

merge and Batcher's odd-even merge when they are used as parallel merging

algorithms. It has been shown previously that the running time of

odd-even merge can be upper bounded by a function of the maximal rank difference

for elements in the two input sequences. Here we give an almost matching lower bound

for odd-even merge as well as a similar upper bound for (a special version

of) bitonic merge.

>From this follows that the average running time of odd-even merge (bitonic

merge) is $\Theta((n/p)(1+\log(1+p^2/n)))$ ($O((n/p)(1+\log(1+p^2/n)))$, resp.)

where $n$ is the size of the input and $p$ is the number of processors used.

Using these results we then show that the average running times of

odd-even merge sort and bitonic merge sort are $O((n/p)(\log n + (\log(1+p^2/n))^2))$,

that is, the two algorithms are optimal on the average if

$n\geq p^2/2^{\sqrt{\log p}}$.

The derived bounds do not allow to compare the two sorting algorithms

program, for various sizes of input and numbers of processors.

In these notes, which were originally written as lecture

notes for Advanced School on Algorithmic Foundations of Geographic

Information Systems, CISM, held in Udine, Italy, in September, 1996,

we discuss issues related to the design of a computational

geometry algorithms library.

We discuss modularity and generality, efficiency and robustness, and

ease of use. We argue that exact geometric

computation is the most promising approach to ensure robustness

in a geometric algorithms library.

Many of the presented concepts have been developed

jointly in the kernel design group of CGAL and/or in the geometry group of

LEDA. However, the view held in these notes is a personal view, not

the official view of CGAL.

Novel algorithms are presented for parallel and external memory

list-ranking. The same algorithms can be used for computing basic

tree functions, such as the depth of a node.

The parallel algorithm stands out through its low memory use, its

simplicity and its performance. For a large range of problem sizes,

it is almost as fast as the fastest previous algorithms. On a

Paragon with 100 PUs, each holding 10^6 nodes, we obtain speed-up 25.

For external-memory list-ranking, the best algorithm so far is

an optimized version of independent-set-removal. Actually,

this algorithm is not good at all: for a list of length N, the

paging volume is about 72 N. Our new algorithm reduces

this to 18 N. The algorithm has been implemented,

and the theoretical results are confirmed.

In this paper we present a paradigm for solving external-memory

problems, and illustrate it by algorithms for matrix multiplication,

sorting, list ranking, transitive closure and FFT. Our paradigm is

based on the use of BSP algorithms. The correspondence is almost

perfect, and especially the notion of x-optimality carries over

to algorithms designed according to our paradigm.

The advantages of the approach are similar to the advantages of

BSP algorithms for parallel computing: scalability, portability,

predictability. The performance measure here is the total work, not

only the number of I/O operations as in previous approaches. The

predicted performances are therefore more useful for practical

applications.

The RAM complexity of deterministic linear space sorting of

integers in words is improved from $O(n\sqrt{\log n})$ to

$O(n(\log\log n)^2)$. No better

bounds are known for polynomial space. In fact, the techniques give a

deterministic linear space priority queue supporting insert and delete in

$O((\log\log n)^2)$ amortized time and find-min in constant time. The priority

queue can be implemented using addition, shift, and

bit-wise boolean operations.

We consider the single machine job sequencing problem

with release dates. The main purpose of this paper

is to investigate efficient and effective

approximation algorithms with a bicriteria performance

guarantee. That is, for some $(\rho_1, \rho_2)$, they

find schedules simultaneously within a factor of $\rho_1$ of

the minimum total weighted completion times and

within a factor of $\rho_2$ of the minimum makespan.

The main results of the paper are summarized as follows.

First, we present a new $O(n\log n)$ algorithm with the performance

guarantee $\left(1+\frac{1}{\beta}, 1+\beta\right)$ for any

$\beta \in [0,1]$. For the problem with integer processing times

and release dates, the algorithm has the bicriteria performance guarantee

$\left(2-\frac{1}{p_{max}}, 2-\frac{1}{p_{max}}\right)$,

where $p_{max}$ is the maximum processing time.

Next, we study an elegant approximation algorithm

introduced recently by Goemans. We show that

its randomized version has expected bicriteria performance

guarantee $(1.7735, 1.51)$ and the derandomized

version has the guarantee $(1.7735, 2-\frac{1}{p_{max}})$.

To establish the performance guarantee, we also use two

LP relaxations and some randomization techniques

as Goemans does, but take a different approach

in the analysis, based on a decomposition theorem. Finally, we

present a family of bad instances showing that

it is impossible to achieve $\rho_1\leq 1.5$ with this LP lower

bound.

This paper surveys results in the design and analysis of self-organizing

data structures for the search problem. We concentrate on two simple but

very popular data structures: the unsorted linear list and the binary search

tree. A self-organizing data structure has a rule or algorithm for

changing pointers or state data. The self-organizing rule is designed to

get the structure into a good state so that future operations can be

processed efficiently. Self-organizing data structures differ from constraint

structures in that no structural invariant, such as a balance constraint in

a binary search tree, has to be satisfied.

In the area of self-organizing linear lists we present a series of

deterministic and randomized on-line algorithms. We concentrate on

competitive algorithms, i.e., algorithms that have a guaranteed performance

with respect to an optimal offline algorithm.

In the area of binary search trees we present both on-line and off-line

algorithms. We also discuss a famous self-organizing

on-line rule called splaying and present important theorems and

open conjectures on splay trees. In the third part of the paper we show

that algorithms for self-organizing lists and trees can be used to build

very effective data compression schemes. We report on theoretical

and experimental results.

Algorithms are presented for the all-pairs min-cut problem in bounded tree-width, planar and sparse networks. The approach used is to preprocess the input $n$-vertex network so that, afterwards, the value of a min-cut between any two vertices can be efficiently computed. A tradeoff is shown between the preprocessing time and the time taken to compute min-cuts subsequently. In particular, after an $O(n\log n)$ preprocessing of a bounded tree-width network, it is possible to find the value of a min-cut between any two vertices in constant time. This implies that for such networks the all-pairs min-cut problem can be solved in time $O(n^2)$.

This algorithm is used in conjunction with a graph decomposition technique of Frederickson to obtain algorithms for sparse and planar networks. The running times depend upon a topological property, $\gamma$, of the input network.

The parameter $\gamma$ varies between 1 and $\Theta(n)$; the algorithms perform well when $\gamma = o(n)$.

The value of a min-cut can be found in time $O(n + \gamma^2 \log \gamma)$ and all-pairs min-cut can be solved in time $O(n^2 + \gamma^4 \log \gamma)$ for sparse networks. The corresponding running times4 for planar networks are $O(n+\gamma \log \gamma)$ and $O(n^2 + \gamma^3 \log \gamma)$, respectively. The latter bounds depend on a result of independent interest: outerplanar networks have small ``mimicking'' networks which are also outerplanar.

This paper shows that finding the row minima (maxima) in an

$n \times n$ totally monotone matrix in the worst case requires

any algorithm to make $3n-5$ comparisons or $4n -5$ matrix accesses.

Where the, so called, SMAWK algorithm of Aggarwal {\em et al\/.}

finds the row minima in no more than $5n -2 \lg n - 6$ comparisons.

This paper presents two simple approximation algorithms for the shortest superstring problem, with approximation ratios $2 {2\over 3}$ ($\approx 2.67$) and $2 {25\over 42}$ ($\approx 2.596$), improving the best previously published $2 {3\over 4}$ approximation.

The framework of our improved algorithms is similar to that of previous algorithms in the sense that they construct a superstring by computing some optimal cycle covers on the distance graph of the given strings, and then break and merge the cycles to finally obtain

a Hamiltonian path, but we make use of new bounds on the overlap between two strings.

We prove that for each periodic semi-infinite string $\alpha = a_1 a_2 \cdots$ of period $q$, there exists an integer $k$, such that for {\em any} (finite) string $s$ of period $p$ which is {\em inequivalent} to $\alpha$, the overlap between $s$ and the {\em rotation}

$\alpha[k] = a_k a_{k+1} \cdots$ is at most $p+{1\over 2}q$.

Moreover, if $p \leq q$, then the overlap between $s$ and $\alpha[k]$ is not larger than ${2\over 3}(p+q)$. In the previous shortest superstring algorithms $p+q$ was used as the standard bound on overlap between two strings with periods $p$ and $q$.

The complexity of maintaining a set under the operations {\sf Insert}, {\sf Delete} and {\sf FindMin} is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost $t$ comparisons per {\sf Insert} and {\sf Delete} has expected cost at least $n/(e2^{2t})-1$ comparisons for {\sf FindMin}. If {\sf FindMin} 474 is replaced by a weaker operation, {\sf FindAny}, then it is shown that a randomized algorithm with constant expected cost per operation exists, but no deterministic algorithm. Finally, a deterministic algorithm with constant amortized cost per operation for an offline version of the problem is given.

We describe the implementation of the LEDA data type {\bf real}. Every integer is a real and reals are closed under the operations addition, subtraction, multiplication, division and squareroot.

The main features of the data type real are

\begin{itemize}

\item The user--interface is similar to that of the built--in data type double.

\item All comparison operators $\{>, \geq, <, \leq, =\}$ are {\em exact}.

In order to determine the sign of a real number $x$ the data type first computes a rational number $q$ such that $|x| \leq q$ implies $x = 0$ and then computes an approximation of $x$ of sufficient precision to decide the sign of $x$.

The user may assist the data type by providing a separation bound $q$.

\item The data type also allows to evaluate real expressions with arbitrary precision. One may either set the mantissae length of the underlying floating point system and then evaluate the expression with that mantissa length or one may specify an error bound $q$. The data type then computes an approximation with absolute error at most $q$.

\end{itemize}

The implementation of the data type real is based on the LEDA data types {\bf integer} and {\bf bigfloat} which are the types of arbitrary precision integers and floating point numbers, respectively.The implementation takes various shortcuts for increased efficiency, e.g., a {\bf double} approximation of any real number together with an error bound is maintained and tests are first performed on these approximations.

A high precision computation is only started when the test on the {\bf double} approximation is inconclusive.

A fundamental problem in computational biology is the

construction of physical maps of chromosomes from hybridization

experiments between unique probes and clones of chromosome fragments

in the presence of error.

Alizadeh, Karp, Weisser and Zweig~\cite{AKWZ94} first considered a

maximum-likelihood model of the problem that is equivalent to finding

an ordering of the probes that minimizes a weighted sum of errors,

and developed several effective heuristics. We show that by exploiting

information about the end-probes of clones, this model can be formulated

as a weighted Betweenness Problem.

This affords the significant advantage of allowing the well-developed tools

of integer linear-programming and branch-and-cut algorithms to be brought

to bear on physical mapping, enabling us for the first time to solve

small mapping instances to optimality even in the presence of high error.

We also show that by combining the optimal solution of many small

overlapping Betweenness Problems, one can effectively screen errors

from larger instances, and solve the edited instance to optimality

as a Hamming-Distance Traveling Salesman Problem.

This suggests a new combined approach to physical map construction.

We consider the problems of computing $r$-approximate traveling salesman tours and $r$-approximate minimum spanning trees for a set of $n$ points in $\IR^d$, where $d \geq 1$ is a constant.

In the algebraic computation tree model, the complexities of both these problems are shown to be $\Theta(n \log n/r)$, for all $n$ and $r$ such that $r<n$ and $r$ is larger than some constant. In the more powerful model of computation that additionally uses the floor function and random access, both problems can be solved in $O(n)$ time if $r = \Theta( n^{1-1/d} )$.

In this paper we study the problem of finding an exact ground state of a two-dimensional $\pm J$ Ising spin glass on a square lattice with nearest neighbor interactions and periodic boundary conditions when there is

a concentration $p$ of negative bonds, with $p$ ranging between $0.1$ and $0.9$. With our exact algorithm we can determine ground states of grids of sizes up to $50\times 50$ in a moderate amount of computation time (up to one hour each) for several values of $p$. For the ground state energy of an infinite spin glass system with $p=0.5$ we estimate $E_{0.5}^\infty = -1.4015 \pm0.0008$.

We report on extensive computational tests based on more than $22\,000$ experiments.

We consider arithmetic expressions over operators

$+$, $-$, $*$, $/$, and $\sqrt{\ }$,

with integer operands. For an expression $E$, a separation bound

$sep(E)$ is a positive real number with the property that $E\neq 0$ implies

$|E| \geq sep(E)$. We propose a new separation bound that is easy to compute an

d stronger than previous bounds.

We investigate random variables arising in occupancy problems, and show the variables to be negatively associated, that is, negatively

dependent in a strong sense. Our proofs are based on the FKG correlation inequality, and they suggest a useful, general technique

for proving negative dependence among random variables. We also show that in the special case of two binary random variables, the notions of negative correlation and negative association coincide.

Algorithms are more and more made available as part of libraries or tool

kits. For a user of such a library statements of asymptotic

running times are almost meaningless as he has no way to estimate the

constants involved. To choose the right algorithm for the targeted problem

size and the available hardware, knowledge about these constants is

important.

Methods to determine the constants based on regression analysis or operation

counting are not practicable in the general case due to inaccuracy and costs

respectively.

We present a new general method to determine the implementation and hardware

specific running time constants for combinatorial

algorithms. This method requires no changes of the implementation

of the investigated algorithm and is

applicable to a wide range of

of programming languages. Only some additional code is necessary.

The determined constants

are correct within a constant factor which depends only on the

hardware platform. As an example the constants of an implementation

of a hierarchy of algorithms and data structures are determined.

The hierarchy consists of an algorithm for the

maximum weighted bipartite matching problem (MWBM), Dijkstra's algorithm,

a Fibonacci heap and a graph representation based on adjacency lists.

ion

frequencies are at most 50 \% on the tested hardware platforms.

The $k$-center problem with triangle inequality is that of placing $k$ center nodes in a weighted undirected graph in which the edge weights obey the triangle inequality, so that the maximum distance of any node to its nearest center is minimized. In this paper, we consider a generalization of this problem where, given a number $p$, we wish to place $k$ centers so as to minimize the maximum distance of any node to its $p\th$ closest center. We consider three different versions of this reliable $k$-center problem depending on which of the nodes can serve as centers and non-centers and derive best possible approximation algorithms for all three versions.

To avoid signal interference in mobile communication it is necessary that the channels used by base stations for broadcast communication within their cells are chosen so that the same channel is never concurrently used by two neighboring stations. We model this channel allocation problem as a {\em generalized list coloring problem} and we provide two distributed solutions, which are also able to cope with crash failures, by limiting the size of the network affected by a faulty station in terms of the distance from that station.

Our first solution uses a powerful synchronization mechanism to achieve a response time that depends only on $\Delta$, the maximum degree of the signal interference graph, and a failure locality of 4.

Our second solution is a simple randomized solution in which each node can expect to pick $f/4\Delta$ colors where $f$ is the size of the list at the node; the response time of this solution is a constant and the failure locality 1.

Besides being efficient (their complexity measures involve only small constants), the protocols presented in this work are simple and easy to apply in practice, provided the existence of distributed infrastructure in networks that are in use.

In this paper we study a few

important tree optimization problems with

applications to computational biology.

These problems ask for trees that are consistent with an

as large part of the given data as possible.

We show that the maximum homeomorphic agreement

subtree problem cannot be approximated within a factor of

$N^{\epsilon}$, where $N$ is the input size, for any $0 \leq \epsilon

< \frac{1}{18}$ in polynomial time, unless P=NP. On the other hand,

we present an $O(N\log N)$-time heuristic for the restriction of this

problem to instances with $O(1)$ trees of height $O(1)$,

yielding solutions within a constant factor of the optimum.

We prove that the maximum inferred consensus tree

problem is NP-complete and we provide a simple fast heuristic

for it, yielding solutions within one third of the optimum.

We also present a more specialized polynomial-time heuristic

for the maximum inferred local consensus tree problem.

We consider {\sl external inverse pattern matching} problem.

Given a text $\t$ of length $n$ over an ordered alphabet $\Sigma$,

such that $|\Sigma|=\sigma$, and a number $m\le n$.

The entire problem is to find a pattern $\pe\in \Sigma^m$ which

is not a subword of $\t$ and which maximizes the sum of Hamming

distances between $\pe$ and all subwords of $\t$ of length $m$.

We present optimal $O(n\log\sigma)$-time algorithm for the external

inverse pattern matching problem which substantially improves

the only known polynomial $O(nm\log\sigma)$-time algorithm

introduced by Amir, Apostolico and Lewenstein.

Moreover we discuss a fast parallel implementation of our algorithm on the

CREW PRAM model.

Data mining can in many instances be viewed as the task of computing a

representation of a theory of a model or of a database. In this paper

we present a randomized algorithm that can be used to compute the

representation of a theory in terms of the most specific sentences of

that theory. In addition to randomization, the algorithm uses a

generalization of the concept of hypergraph transversals. We apply

the general algorithm in two ways, for the problem of discovering

maximal frequent sets in 0/1 data, and for computing minimal keys in

relations. We present some empirical results on the performance of

these methods on real data. We also show some complexity theoretic

evidence of the hardness of these problems.

In a generalized searching problem, a set $S$ of $n$ colored

geometric objects has to be stored in a data structure, such

that for any given query object $q$, the distinct colors of

the objects of $S$ intersected by $q$ can be reported

efficiently. In this paper, a general technique is presented

for adding a range restriction to such a problem. The technique

is applied to the problem of querying a set of colored points

(resp.\ fat triangles) with a fat triangle (resp.\ point).

For both problems, a data structure is obtained having size

$O(n^{1+\epsilon})$ and query time $O((\log n)^2 + C)$.

Here, $C$ denotes the number of colors reported by the query,

and $\epsilon$ is an arbitrarily small positive constant.

We present algorithms for the two layer straightline crossing

minimization problem that are able to compute exact optima. Our

computational results lead us to the conclusion that there is no

need for heuristics if one layer is fixed, even though the problem

is NP-hard, and that for the general problem with two variable layers,

true optima can be computed for sparse instances in which the smaller

layer contains up to 15 nodes. For bigger instances, the iterated

barycenter method turns out to be the method of choice among several

popular heuristics whose performance we could assess by comparing the

results to optimum solutions.

{\em Counting networks} form a new class of distributed, low-contention data structures, made up of {\em balancers} and {\em wires,}

which are suitable for solving a variety of multiprocessor synchronization problems that can be expressed as counting problems.

A {\em linearizable} counting network guarantees that the order of the values it returns respects the real-time order they were requested.

Linearizability significantly raises the capabilities of the network, but at a possible price in network size or synchronization support.

In this work, we further pursue the systematic study of the impact of {\em timing} assumptions on linearizability for

counting networks, along the line of research recently initiated by Lynch~{\em et~al.} in [18].

We consider two basic {\em timing} models, the {instantaneous balancer} model, in which the transition of a token from an input to an output port of a balancer is modeled as an instantaneous event, and the {\em periodic balancer} model, where balancers send out tokens at a fixed rate. In both models, we assume lower and upper bounds on the delays incurred by wires connecting the balancers.

We present necessary and sufficient conditions for linearizability in these models, in the form of precise inequalities that involve not only parameters of the timing models, but also certain structural parameters of the counting network, which may be of more general interest.

Our results extend and strengthen previous impossibility and possibility results on linearizability in counting networks.

We specify and implement a kernel for computational geometry in

arbitrary finite dimensional space. The kernel provides points,

vectors, directions, hyperplanes, segments, rays, lines, affine

transformations, and operations connecting these types. Points have

rational coordinates, hyperplanes have rational coefficients, and

analogous statements hold for the other types. We therefore call our

types \emph{rat\_point}, \emph{rat\_vector}, \emph{rat\_direction},

\emph{rat\_hyperplane}, \emph{rat\_segment}, \emph{rat\_ray} and

\emph{rat\_line}. All geometric primitives are \emph{exact}, i.e.,

they do not incur rounding error (because they are implemented using

rational arithmetic) and always produce the correct result. To this

end we provide types \emph{integer\_vector} and \emph{integer\_matrix}

which realize exact linear algebra over the integers.

The kernel is submitted to the CGAL-Consortium as a proposal for its

higher-dimensional geometry kernel and will become part of the LEDA

platform for combinatorial and geometric computing.

We give a state-of-the-art survey of the thickness of a graph from both a theoretical and a practical point of view. After summarizing the relevant results concerning this topological invariant of a graph, we deal with practical computation of the thickness.

We present some modifications of a basic heuristic and investigate their usefulness for evaluating the thickness and determining a decomposition of a graph in planar subgraphs.

Multiple sequence alignment is an important problem in computational biology.

We study the Maximum Trace formulation introduced by

Kececioglu~\cite{Kececioglu91}.

We first phrase the problem in terms of forbidden subgraphs,

which enables us to express Maximum Trace as an integer linear-programming

problem,

and then solve the integer linear program using methods from polyhedral

combinatorics.

The trace {\it polytope\/} is the convex hull of all feasible solutions

to the Maximum Trace problem;

for the case of two sequences,

we give a complete characterization of this polytope.

This yields a polynomial-time algorithm

for a general version of pairwise sequence alignment

that, perhaps suprisingly, does not use dynamic programming;

this yields, for instance, a non-dynamic-programming algorithm for

sequence comparison under the 0-1 metric,

which gives another answer to a long-open question in the area of string algorithms

\cite{PW93}.

For the multiple-sequence case,

we derive several classes of facet-defining inequalities

and show that for all but one class, the corresponding separation problem

can be solved in polynomial time.

This leads to a branch-and-cut algorithm for multiple sequence alignment,

and we report on our first computational experience.

It appears that a polyhedral approach to multiple sequence alignment

can solve instances that are beyond present dynamic-programming approaches.

Let $X$ be an arrangement of $n$ algebraic sets $X_i$ in $d$-space, where the $X_i$ are either parameterized or zero-sets of dimension $0\le m_i\le d-1$. We study a number of decompositions of $d$-space into connected regions in which the distance-squared function to $X$ has certain invariances. These decompositions can be used in the following of proximity problems: given some point, find the $k$ nearest sets $X_i$ in the arrangement, find the nearest point in $X$ or (assuming that $X$ is compact) find the farthest point in $X$ and hence the smallest enclosing $(d-1)$-sphere. We give bounds on the complexity of the decompositions in terms of $n$, $d$, and the degrees and dimensions of the algebraic sets $X_i$.

We consider some geometric problems on the unit sphere which arise in

$NC$-machining. Optimal linear time algorithms are given for these

problems using linear and quadratic programming in three dimensions.

In this Research Report we want to clarify the current efficiency

of two LEDA software layers. We examine the runtime of the

LEDA big integer number type |integer| and of the linear algebra

classes |integer_matrix| and |integer_vector|.

Algorithms for performing gossiping on one- and higher dimensional

meshes are presented. As a routing model, we assume the

practically important worm-hole routing.

For one-dimensional arrays and rings, we give a novel lower bound

and an asymptotically optimal gossiping algorithm for all choices of

the parameters involved.

For two-dimensional meshes and tori, several simple algorithms

composed of one-dimensional phases are presented. For an important

range of packet and mesh sizes it gives clear improvements upon

previously developed algorithms. The algorithm is analyzed

theoretically, and the achieved improvements are also convincingly

demonstrated by simulations and by an implementation on the Paragon.

For example, on a Paragon with $81$ processors and messages of size

32 KB, relying on the built-in router requires $716$ milliseconds,

while our algorithm requires only $79$ milliseconds.

For higher dimensional meshes, we give algorithms which are based

on a generalized notion of a diagonal. These are analyzed

theoretically and by simulation.

We present a simple parallel algorithm for the {\em single-source shortest path problem} in {\em planar digraphs} with nonnegative real edge weights.

The algorithm runs on the EREW PRAM model of parallel computation in $O((n^{2\epsilon} + n^{1-\epsilon})\log n)$ time, performing

$O(n^{1+\epsilon}\log n)$ work for any $0<\epsilon<1/2$. The strength of the algorithm is its simplicity, making it easy to implement, and presumably 474 quite efficient in practice.

The algorithm improves upon the work of all previous algorithms.

The work can be further reduced to $O(n^{1+\epsilon})$, by plugging in a less practical, sequential planar shortest path

algorithm.

Our algorithm is based on a region decomposition of the input graph, and uses a well-known parallel implementation of Dijkstra's algorithm.

Computational Biology is a fairly new subject that arose in response to the computational problems posed by the analysis and the processing of biomolecular sequence and structure data. The field was initiated in the late 60's and early 70's largely by pioneers working in the life sciences. Physicists and mathematicians entered the field in the 70's and 80's, while Computer Science became

involved with the new biological problems in the late 1980's.

Computational problems have gained further importance in molecular biology through the various genome projects which produce enormous amounts of data.

For this bibliography we focus on those areas of computational molecular biology that involve discrete algorithms

or discrete optimization. We thus neglect several other areas of computational molecular biology, like most of the literature on

the protein folding problem, as well as databases for molecular and genetic data, and genetic mapping algorithms.

Due to the availability of review papers and a bibliography this bibliography.

We show that a unit-cost RAM with a word

length of $w$ bits can sort $n$ integers

in the range $0\Ttwodots 2^w-1$ in

$O(n\log\log n)$ time, for arbitrary $w\ge\log n$,

a significant improvement over

the bound of $O(n\sqrt{\log n})$ achieved

by the fusion trees of Fredman and Willard.

Provided that $w\ge(\log n)^{2+\epsilon}$

for some fixed $\epsilon>0$, the sorting can even

be accomplished in linear expected time

with a randomized algorithm.

Both of our algorithms parallelize without

loss on a unit-cost PRAM with a word

length of $w$ bits.

The first one yields an algorithm that uses

$O(\log n)$ time and\break

$O(n\log\log n)$ operations on a

deterministic CRCW PRAM.

The second one yields an algorithm that uses

$O(\log n)$ expected time and $O(n)$ expected

operations on a randomized EREW PRAM,

provided that $w\ge(\log n)^{2+\epsilon}$

for some fixed $\epsilon>0$.

Our deterministic and randomized sequential

and parallel algorithms generalize to the

lexicographic sorting problem of sorting

multiple-precision integers represented

in several words.

The problem of finding an implicit representation for a graph

such that vertex adjacency can be tested quickly is

fundamental to all graph algorithms. In particular, it

is possible to represent sparse graphs on $n$ vertices

using $O(n)$ space such that vertex adjacency is tested

in $O(1)$ time. We show here how to construct such a

representation efficiently by providing simple and optimal

algorithms, both in a sequential and a parallel setting.

Our sequential algorithm runs in $O(n)$ time.

The parallel algorithm runs in $O(\log n)$ time using

$O(n/{\log n})$ CRCW PRAM processors, or in $O(\log n\log^*n)$

time using $O(n/\log n\log^*n)$ EREW PRAM processors.

Previous results for this problem

are based on matroid partitioning and thus have a high complexity.

We describe the first parallel algorithm with

optimal speedup for constructing minimum-width

tree decompositions of graphs of bounded treewidth.

On $n$-vertex input graphs, the algorithm works in

$O((\log n)^2)$ time using $O(n)$ operations

on the EREW PRAM.

We also give faster parallel algorithms with

optimal speedup for the problem of deciding

whether the treewidth of an input graph is

bounded by a given constant and for a variety of

problems on graphs of bounded treewidth,

including all decision problems expressible

in monadic second-order logic.

On $n$-vertex input graphs, the algorithms use

$O(n)$ operations together with $O(\log n\Tlogstar n)$

time on the EREW PRAM, or $O(\log n)$ time on the CRCW PRAM.

The nuts and bolts problem is the following :

Given a collection of $n$ nuts of distinct sizes and $n$ bolts of distinct

sizes such that for each nut there is exactly one matching bolt,

find for each nut its corresponding bolt subject

to the restriction that we can {\em only} compare nuts to bolts.

That is we can neither compare nuts to nuts, nor bolts to bolts.

This humble restriction on the comparisons appears to make

this problem quite difficult to solve.

In this paper, we illustrate the existence of an algorithm

for solving the nuts and bolts problem that makes

$O(n \lg n)$ nut-and-bolt comparisons.

We show the existence of this algorithm by showing

the existence of certain expander-based comparator networks.

Our algorithm is asymptotically optimal in terms of the number

of nut-and-bolt comparisons it does.

Another view of this result is that we show the existence of a

decision tree with depth $O(n \lg n)$ that solves this problem.

We present algorithms for the two layer straightline crossing

minimization problem that are able to compute exact optima.

Our computational results lead us to the conclusion that there

is no need for heuristics if one layer is fixed, even though

the problem is NP-hard, and that for the general problem with

two variable layers, true optima can be computed for sparse

instances in which the smaller layer contains up to 15 nodes.

For bigger instances, the iterated barycenter method turns out

to be the method of choice among several popular heuristics

whose performance we could assess by comparing the results

to optimum solutions.

We give a parallel algorithm for computing all row minima

in a totally monotone $n\times n$ matrix which is simpler and more

work efficient than previous polylog-time algorithms.

It runs in

$O(\lg n \lg\lg n)$ time doing $O(n\sqrt{\lg n})$ work on a {\sf CRCW}, in

$O(\lg n (\lg\lg n)^2)$ time doing $O(n\sqrt{\lg n})$ work on a {\sf CREW},

and in $O(\lg n\sqrt{\lg n \lg\lg n})$ time

doing $O(n\sqrt{\lg n\lg\lg n})$ work on an {\sf EREW}.

The problem of matching nuts and bolts is the following :

Given a collection of $n$ nuts of distinct sizes and $n$ bolts

such that there is a one-to-one correspondence between the nuts

and the bolts, find for each nut its corresponding bolt.

We can {\em only} compare nuts to bolts.

That is we can neither compare nuts to nuts, nor bolts to bolts.

This humble restriction on the comparisons appears to make

this problem very hard to solve.

In fact, the best deterministic solution to date is due

to Alon {\it et al\/.} [1] and takes $\Theta(n \log^4 n)$

time. Their solution uses (efficient) graph expanders. In this paper,

we give a simpler $\Theta(n \log^2 n)$ time algorithm which uses only

a simple (and not so efficient) expander.

We consider the problem of preprocessing an $n$-vertex digraph with

real edge weights so that subsequent queries for the shortest path or distance

between any two vertices can be efficiently answered.

We give algorithms

that depend on the {\em treewidth} of the input graph. When the

treewidth is a constant, our algorithms can answer distance queries in

$O(\alpha(n))$ time after $O(n)$ preprocessing. This improves upon

previously known results for the same problem.

We also give a

dynamic algorithm which, after a change in an edge weight, updates the

data structure in time $O(n^\beta)$, for any constant $0 < \beta < 1$.

Furthermore, an algorithm of independent interest is given:

computing a shortest path tree, or finding a negative cycle in linear

time.

We consider the problem of preprocessing an $n$-vertex digraph with

real edge weights so that subsequent queries for the shortest path or distance

between any two vertices can be efficiently answered.

We give parallel algorithms for the EREW PRAM model of computation

that depend on the {\em treewidth} of

the input graph. When the treewidth is a constant, our algorithms

can answer distance queries in $O(\alpha(n))$ time using a single

processor, after a preprocessing of $O(\log^2n)$ time and $O(n)$ work,

where $\alpha(n)$ is the inverse of Ackermann's function.

The class of constant treewidth graphs

contains outerplanar graphs and series-parallel graphs, among

others. To the best of our knowledge, these

are the first parallel algorithms which achieve these bounds

for any class of graphs except trees.

We also give a dynamic algorithm which, after a change in

an edge weight, updates our data structures in $O(\log n)$ time

using $O(n^\beta)$ work, for any constant $0 < \beta < 1$.

Moreover, we give an algorithm of independent interest:

computing a shortest path tree, or finding a negative cycle in

$O(\log^2 n)$ time using $O(n)$ work.

In this paper we study 2-dimensional Ising spin glasses on a grid with nearest

neighbor and periodic boundary interactions, based on a Gaussian bond

distribution, and an exterior magnetic field.

We show how using a technique called branch and cut, the exact

ground states of grids of sizes up to $100\times 100$ can be determined in a

moderate amount of computation time, and we report on extensive computational

tests. With our method we produce results based on more than $20\,000$

experiments

on the properties of spin glasses whose errors depend only on the assumptions

on the

model and not on the computational process. This feature is a clear advantage

of the method over other more popular ways to compute the ground state, like

Monte Carlo simulation including simulated annealing, evolutionary, and

genetic algorithms, that provide only approximate

ground states with a degree of accuracy that cannot be determined a priori.

Our ground state energy estimation at zero field is~$-1.317$.

Luby (1988) proposed a way to derandomize randomized

computations which is based on the construction of a small probability

space whose elements are $3$-wise independent.

In this paper we prove some new properties of Luby's space.

More precisely, we analyze the fourth moment and

prove an interesting technical property which helps

to understand better Luby's distribution. As an application,

we study the behavior of random edge cuts in a weighted graph.

Past research on fault tolerant distributed systems has focussed on either

processor failures, ranging from benign crash failures to the malicious

byzantine failure types, or on transient memory failures, which can

suddenly corrupt the state of the system.

An interesting question in the theory of distributed computing is whether one

can device highly fault tolerant protocols which can

tolerate both processor failures as well as transient errors.

To answer this question we consider the construction of

self-stabilizing wait-free shared memory objects.

These objects occur naturally in distributed systems in which both processors

and memory may be faulty.

Our contribution in this paper is threefold. First, we propose a general

definition of a self-stabilizing wait-free shared memory object that

expresses safety guarantees even in the face of processor failures.

Second, we show that within this framework one cannot construct a

self-stabilizing single-reader single-writer regular bit from

single-reader single-writer safe bits. This result leads us to postulate a

self-stabilizing {\footnotesize\it dual\/}-reader single-writer safe bit with

which, as a

third contribution, we construct self-stabilizing regular and atomic registers.

The thickness problem on graphs is $\cal NP$-hard and only few

results concerning this graph invariant are known. Using a decomposition

theorem of Truemper, we show that the thickness of

the class of graphs without $G_{12}$-minors is less

than or equal to two (and therefore, the same is true for the more

well-known class of the graphs without $K_5$-minors).

Consequently, the thickness of this class of graphs can

be determined with a planarity testing algorithm in linear time.

We present algorithms for the two layer straightline crossing

minimization problem that are able to compute exact optima.

Our computational results lead us to the conclusion that there

is no need for heuristics if one layer is fixed, even though

the problem is NP-hard, and that for the general problem with

two variable layers, true optima can be computed for sparse

instances in which the smaller layer contains up to 15 nodes.

For bigger instances, the iterated barycenter method turns out

to be the method of choice among several popular heuristics

whose performance we could assess by comparing the results

to optimum solutions.

In this paper, we consider dynamic data structures for order

decomposable problems. This class of problems include the convex hull

problem, the Voronoi diagram problem, the maxima problem,

and intersection of halfspaces.

This paper first describes a scheme for maintaining convex hulls in

the plane dynamically in $O(\log n)$ amortized time for insertions and

$O(\log^2 n)$ time for deletions. $O(n)$ space is used.

The scheme improves on the time complexity of the general scheme

by Overmars and Van Leeuwen. We then consider the general class

of Order Decomposable Problems. We show improved behavior for

insertions in the presence of deletions, under some assumptions.

The main assumption we make is that the problems are required

to be {\em change sensitive}, i.e., updates to the solution

of the problem at an insertion can be obtained in time proportional

to the changes.

We describe the implementation of a data structure called radix heap,

which is a priority queue with restricted functionality.

Its restrictions are observed by Dijkstra's algorithm, which uses

priority queues to solve the single source shortest path problem

in graphs with nonnegative edge costs.

For a graph with $n$ nodes and $m$ edges and real-valued edge costs,

the best known theoretical bound for the algorithm is $O(m+n\log n)$.

This bound is attained by using Fibonacci heaps to implement

priority queues.

If the edge costs are integers in the range $[0\ldots C]$, then using

our implementation of radix heaps for Dijkstra's algorithm

leads to a running time of $O(m+n\log C)$.

We compare our implementation of radix heaps with an existing implementation

of Fibonacci heaps in the framework of Dijkstra's algorithm. Our

experiments exhibit a tangible advantage for radix heaps over Fibonacci heaps

and confirm the positive influence of small edge costs on the running time.

We have implemented a parallel distributed geometric docking

algorithm that uses a new measure for the size of the

contact area of two molecules. The measure is a potential function

that counts the ``van der Waals contacts'' between the atoms of the

two molecules (the algorithm does not compute

the Lennard-Jones potential).

An integer constant $c_a$ is added to the potential for

each pair of atoms whose

distance is in a certain interval. For each pair whose distance is

smaller than the lower bound of the interval an integer constant

$c_s$ is subtracted from the potential ($c_a <c_s$).

The number of allowed overlapping atom pairs is handled by

a third parameter $N$.

Conformations where more than $N$ atom pairs overlap are

ignored. In our ``real world'' experiments we have used

a small parameter $N$ that allows small local penetration.

Among the best five dockings found by the algorithm there was

almost always a good (rms) approximation of the real

conformation.

In 42 of 52 test examples

the best conformation with respect to the potential function

was an approximation of the real conformation.

The running time of our sequential algorithm is in the order

of the running time of the algorithm of

Norel {\it et al.}[NLW+].

The parallel version of the algorithm has a reasonable

speedup and modest communication requirements.

LEDA is a library of efficient data types and algorithms in combinatorial and

geometric computing. The main features of the library are its wide collection

of data types and algorithms, the precise and readable specification of these

types, its efficiency, its extendibility, and its ease of use.

Dieser Artikel wurde für das Jahrbuch 1995 der

Max-Planck-Gesellschaft geschrieben. Er beinhaltet eine

allgemein verständliche Einführung in das automatisierte

Zeichnen von Diagrammen sowie eine kurze Übersicht üuber die

aktuellen Forschungsschwerpunkte am MPI.

Given a planar graph $G$, the planar (biconnectivity)

augmentation problem is to add the minimum number of edges to $G$

such that the resulting graph is still planar and biconnected.

Given a nonplanar and biconnected graph, the maximum planar biconnected

subgraph problem consists of removing the minimum number of edges so

that planarity is achieved and biconnectivity is maintained.

Both problems are important in Automatic Graph Drawing.

In [JM95], the minimum planarizing

$k$-augmentation problem has been introduced, that links the planarization

step and the augmentation step together. Here, we are given a graph which is

not necessarily planar and not necessarily $k$-connected, and we want to delete

some set of edges $D$ and to add some set of edges $A$ such that $|D|+|A|$

is minimized and the resulting graph is planar, $k$-connected and spanning.

For all three problems, we have given a polyhedral formulation

by defining three different linear objective functions over the same polytope,

namely the $2$-node connected planar spanning subgraph polytope $\2NCPLS(K_n)$.

We investigate the facial structure of this polytope for $k=2$,

which we will make use of in a branch and cut algorithm.

Here, we give the dimension of the planar, biconnected, spanning subgraph

polytope for $G=K_n$ and we show that all facets of the planar subgraph

polytope $\PLS(K_n)$ are also facets of the new polytope $\2NCPLS(K_n)$.

Furthermore, we show that the node-cut constraints arising in the

biconnectivity spanning subgraph polytope, are facet-defining inequalities

for $\2NCPLS(K_n)$.

We give first computational results for all three problems, the planar

$2$-augmentation problem, the minimum planarizing $2$-augmentation problem

and the maximum planar biconnected (spanning) subgraph problem.

This is the first time that instances of any of these three problems can

be solved to optimality.

No abstract available.

In the {\em consensus} problem in a system with $n$ processes, each process

starts with a private input value and runs until it chooses irrevocably a

decision value, which was the input value of some process of the system;

moreover, all processes have to decide on the same value.

This work deals with the problem of {\em wait-free} ---fully resilient

to processor crash and napping failures--- consensus

of $n$ processes in an ``in-phase" multiprocessor system.

It proves the existence of a solution to the problem in this system by

presenting a protocol which ensures that a process will

reach decision within at most $n(n-3)/2 +3$ steps of its own in the worst case,

or within $n$ steps if no process fails.

The report is a compilation of lecture notes that were prepared during

the course ``Interactive Proof Systems'' given by the authors at Tata

Institute of Fundamental Research, Bombay. These notes were also used

for a short course ``Interactive Proof Systems'' given by the second

author at MPI, Saarbruecken. The objective of the course was to study

the recent developments in complexity theory about interactive proof

systems, which led to some surprising consequences on

nonapproximability of NP hard problems.

We start the course with an introduction to complexity theory and

covered some classical results related with circuit complexity,

randomizations and counting classes, notions which are either part of

the definitions of interactive proof systems or are used in proving

the above results.

We define arthur merlin games and interactive proof systems, which are

equivalent formulations of the notion of interactive proofs and show

their equivalence to each other and to the complexity class PSPACE.

We introduce probabilistically checkable proofs, which are special

forms of interactive proofs and show through sequence of intermediate

results that the class NP has probabilistically checkable proofs of

very special form and very small complexity. Using this we conclude

that several NP hard problems are not even weakly approximable in

polynomial time unless P = NP.

This paper is concerned with the average running time of Batcher's

odd-even merge sort when implemented on a collection of processors.

We consider the case where $n$, the size of the input,

is an arbitrary multiple of the number $p$ of processors used.

We show that Batcher's odd-even merge (for two sorted lists of length $n$ each)

can be implemented to run in time $O((n/p)(\log (2+p^2/n)))$ on the average,

and that odd-even merge sort can be implemented to run in time

$O((n/p)(\log n+\log p\log (2+p^2/n)))$ on the average.

In the case of merging (sorting), the average is taken over all possible outcomes

of the merging (all possible permutations of $n$ elements).

That means that odd-even merge and odd-even merge sort have an optimal

average running time if $n\geq p^2$. The constants involved are also

quite small.

This paper provides an overview of lower and upper bounds for

mesh-connected processor networks. Most attention goes to

routing and sorting problems, but other problems are mentioned as

well. Results from 1977 to 1995 are covered. We provide numerous

results, references and open problems. The text is completed with

an index. This is a worked-out version of the author's contribution

to a joint paper with Grammatikakis, Hsu and Kraetzl on multicomputer

routing, submitted to JPDC.

This paper provides an overview of lower and upper bounds for

algorithms for mesh-connected processor networks. Most of our

attention goes to routing and sorting problems, but other problems

are mentioned as well. Results from 1977 to 1995 are covered. We

provide numerous results, references and open problems. The text

is completed with an index.

This is a worked-out version of the author's contribution

to a joint paper with Miltos D. Grammatikakis, D. Frank Hsu and

Miro Kraetzl on multicomputer routing, submitted to the Journal

of Parallel and Distributed Computing.

Let $S$ be a set of $n$ points in $R^d$, and let each point

$p$ of $S$ have a positive weight $w(p)$. We consider the

problem of computing a ray $R$ emanating from the origin

(resp.\ a line $l$ through the origin) such that

$\min_{p\in S} w(p) \cdot d(p,R)$ (resp.

$\min_{p\in S} w(p) \cdot d(p,l)$) is maximal. If all weights

are one, this corresponds to computing a silo emanating

from the origin (resp.\ a cylinder whose axis contains the

origin) that does not contain any point of $S$ and whose

radius is maximal.

For $d=2$, we show how to solve these problems in $O(n \log n)$

time, which is optimal in the algebraic computation tree

model. For $d=3$, we give algorithms that are based on the

parametric search technique and run in $O(n \log^5 n)$ time.

The previous best known algorithms for these three-dimensional

problems had almost quadratic running time.

In the final part of the paper, we consider some related problems

This is the preliminary version of a chapter that will

appear in the {\em Handbook on Computational Geometry},

edited by J.-R.\ Sack and J.\ Urrutia.

A comprehensive overview is given of algorithms and data

structures for proximity problems on point sets in $\IR^D$.

In particular, the closest pair problem, the exact and

approximate post-office problem, and the problem of

constructing spanners are discussed in detail.

The page replication problem arises in the memory management of large

multiprocessor systems. Given a network of processors, each of which

has its local memory, the problem consists of deciding

which local memories should contain copies of pages of data so that

a sequence of memory accesses can be accomplished efficiently. We present

new competitive on-line algorithms for the page replication problem and

concentrate on important network topologies for which algorithms with

a constant competitive factor can be given. We develop the first

optimal randomized on-line replication algorithm for trees and

uniform networks; its competitive factor is

approximately 1.58. Furthermore we consider on-line

replication algorithms for rings and present general techniques that

transform large classes of $c$-competitive algorithms for trees into

$2c$-competitive algorithms for rings. As a result we obtain a randomized

on-line algorithm for rings that is 3.16-competitive. We also derive

two 4-competitive on-line algorithms for rings which are either deterministic

or memoryless. All our algorithms improve the previously best

competitive factors for the respective topologies.

We show that $n$ integers in the range

$1 \twodots n$ can be stably sorted on an

\linebreak EREW PRAM

using \nolinebreak $O(t)$ time \linebreak and

$O(n(\sqrt{\log n\log\log n}+{{(\log n)^2}/t}))$

operations, for arbitrary given \linebreak

$t\ge\log n\log\log n$, and on a CREW PRAM using

%$O(\log n\log\log n)$ time and $O(n\sqrt{\log n})$

$O(t)$ time and

$O(n(\sqrt{\log n}+{{\log n}/{2^{{t/{\log n}}}}}))$

operations, for arbitrary given $t\ge\log n$.

In addition, we are able to sort $n$ arbitrary

integers on a randomized CREW PRAM

% using

%$O(\log n\log\log n)$ time and $O(n\sqrt{\log n})$ operations

within the same resource bounds with high probability.

In each case our algorithm is

a factor of almost $\Theta(\sqrt{\log n})$

closer to optimality

than all previous algorithms for the stated problem

in the stated model, and our third result matches the operation

count of the best known sequential algorithm.

We also show that $n$ integers in the range $1 \twodots m$

can be sorted in $O((\log n)^2)$

time with $O(n)$ operations on an EREW PRAM using a nonstandard word

length of $O(\log n \log\log n \log m)$ bits,

thereby greatly improving the upper

bound on the word length necessary to sort integers

with a linear time-processor product,

even sequentially.

Our algorithms were inspired by, and in one case directly

use, the fusion trees of

Fredman and Willard.

We describe a robust and efficient implementation of the Bentley-Ottmann

sweep line algorithm based on the LEDA library

of efficient data types and algorithms. The program

computes the planar graph $G$ induced by a set $S$ of straight line segments

in the plane. The nodes of $G$ are all endpoints and all proper

intersection

points of segments in $S$. The edges of $G$ are the maximal

relatively open

subsegments of segments in $S$ that contain no node of $G$. All edges

are

directed from left to right or upwards.

The algorithm runs in time $O((n+s) log n)$ where $n$ is the number of

segments and $s$ is the number of vertices of the graph $G$. The implementation

uses exact arithmetic for the reliable realization of the geometric

primitives and it uses floating point filters to reduce the overhead of

exact arithmetic.

A sequence $d$ of integers is a degree sequence if there exists

a (simple) graph $G$ such that the components of $d$ are equal to

the degrees of the vertices of $G$. The graph $G$ is said to be a

realization of $d$. We provide an efficient

parallel algorithm to realize $d$.

Before our result, it was not known if the problem of

realizing $d$ is in $NC$.

Sparse graphs (e.g.~trees, planar graphs, relative neighborhood graphs)

are among the commonly used data-structures in computational geometry.

The problem of finding a compact representation for sparse

graphs such that vertex adjacency can be tested quickly is fundamental to

several geometric and graph algorithms.

We provide here simple and optimal algorithms for constructing

a compact representation of $O(n)$ size for an $n$-vertex sparse

graph such that the adjacency can be

tested in $O(1)$ time. Our sequential algorithm

runs in $O(n)$ time, while the parallel one runs in $O(\log n)$ time using

$O(n/{\log n})$ CRCW PRAM processors. Previous results for this problem

are based on matroid partitioning and thus have a high complexity.

Let $S$ be a set of $n$ points in $\IR^d$ and let $t>1$ be

a real number. A $t$-spanner for $S$ is a directed graph

having the points of $S$ as its vertices, such that for any

pair $p$ and $q$ of points there is a path from $p$ to $q$

of length at most $t$ times the Euclidean distance between

$p$ and $q$. Such a path is called a $t$-spanner path.

The spanner diameter of such a spanner is defined as the

smallest integer $D$ such that for any pair $p$ and $q$ of

points there is a $t$-spanner path from $p$ to $q$ containing

at most $D$ edges.

A randomized algorithm is given for constructing a

$t$-spanner that, with high probability, contains $O(n)$

edges and has spanner diameter $O(\log n)$.

A data structure of size $O(n \log^d n)$ is given that

maintains this $t$-spanner in $O(\log^d n \log\log n)$

expected amortized time per insertion and deletion, in the

model of random updates, as introduced by Mulmuley.

Previously, no results were known for spanners with low

spanner diameter and for maintaining spanners under insertions

and deletions.

Let $S$ be a set of $n$ points in $\IR^d$ and let $t>1$ be

a real number. A $t$-spanner for $S$ is a graph having the

points of $S$ as its vertices such that for any pair $p,q$ of

points there is a path between them of length at most $t$

times the euclidean distance between $p$ and $q$.

An efficient implementation of a greedy algorithm is given

that constructs a $t$-spanner having bounded degree such

that the total length of all its edges is bounded by

$O(\log n)$ times the length of a minimum spanning tree

for $S$. The algorithm has running time $O(n \log^d n)$.

Also, an application to the problem of distance enumeration

is given.

We study the short term behavior of random walks on graphs,
in particular, the rate at which a random walk
discovers new vertices and edges.
We prove a conjecture by
Linial that the expected time to find $\cal N$ distinct vertices is $O({\cal N} ^ 3)$.
We also prove an upper bound of
$O({\cal M} ^ 2)$ on the expected time to traverse $\cal M$ edges, and
$O(\cal M\cal N)$ on the expected time to either visit $\cal N$ vertices or
traverse $\cal M$ edges (whichever comes first).

We are interested in implementing data structures on shared memory
multiprocessors. A natural model for these machines is an
asynchronous parallel machine, in which the processors are subject to
arbitrary delays. On such machines, it is desirable for algorithms to
be {\em lock-free}, that is, they must allow concurrent access to data
without using mutual exclusion.
Efficient lock-free implementations are known for some specific data
structures, but these algorithms do not generalize well to other
structures. For most data structures, the only previously known lock-free
algorithm is due to Herlihy. Herlihy presents a
simple methodology to create a lock-free implementation of a general
data structure, but his approach can be very expensive.

We present a technique that provides the semantics of
exclusive access to data without using mutual exclusion.
Using
this technique,
we devise the {\em caching method},
a general method of implementing lock-free data
structures that is provably
better than Herlihy's methodology for many
well-known data structures.
The cost of one operation using the caching method
is proportional to $T \log T$, where $T$ is the sequential cost of the
operation. Under Herlihy's methodology, the
cost is proportional to $T + C$,
where $C$ is the time needed to make a logical copy of the data structure.
For many data structures, such as arrays and
{\em well connected} pointer-based structures (e.g., a doubly linked
list), the best known value for $C$ is
proportional to the size of the structure, making the copying time
much larger than the sequential cost of an operation.
The new method can also allow {\em concurrent updates} to the data
structure; Herlihy's methodology cannot.
A correct lock-free implementation can be derived
from a correct sequential implementation in a straightforward manner
using this
method.
The method is also flexible; a programmer can change many of the details
of the default implementation to optimize for a particular pattern of data
structure use.

Directed $s$-$t$ connectivity is the problem of detecting whether there
is a path from a distinguished vertex $s$ to a distinguished
vertex $t$ in a directed graph.
We prove time-space lower bounds of $ST = \Omega(n^{2}/\log n)$
and $S^{1/2}T = \Omega(m n^{1/2})$
for Cook and Rackoff's JAG model, where $n$ is the number of
vertices and $m$ the number of edges in the input graph, and
$S$ is the space and $T$ the time used by the JAG.
We also prove a time-space lower bound of
$S^{1/3}T = \Omega(m^{2/3}n^{2/3})$
on the more powerful
node-named JAG model of Poon.
These bounds approach the known upper bound
of $T = O(m)$
when $S = \Theta(n \log n)$.

In this paper we view $P\stackrel{?}{=}NP$ as the problem which symbolizes
the attempt to understand what is and is not feasibly computable.
The paper shortly reviews the history of the developments
from G"odel's 1956 letter asking for the computational
complexity of finding proofs of theorems, through
computational complexity, the exploration of complete problems for NP
and PSPACE, through the results of structural complexity to the
recent insights about interactive proofs.

The \Tstress{range product problem} is, for a given

set $S$ equipped with an associative operator

$\circ$, to preprocess a sequence $a_1,\ldots,a_n$

of elements from $S$ so as to enable efficient

subsequent processing of queries of the form:

Given a pair $(s,t)$ of integers with

$1\le s\le t\le n$, return

$a_s\circ a_{s+1}\circ\cdots\circ a_t$.

The generic range product problem

and special cases thereof,

usually with $\circ$ computing the maximum

of its arguments according to some linear

order on $S$, have been extensively studied.

We show that a large number of previous sequential

and parallel algorithms for these problems can

be unified and simplified by means of prefix graphs.