Algorithms – ESA 2004

The talk will survey the rich toolkit of FPT algorithm design methodologies that has developed over the last 20 years, including “older” techniques such as well-quasi-ordering, bounded treewidth, color-coding, reduction to a problem kernel, and bounded search trees — which have continued to deepen and advance — as well as some recently developed approaches such as win/win’s, greedy localization, iterative compression, and crown decompositions.

Web search engines have emerged as one of the central applications on the internet. In fact, search has become one of the most important activities that people engage in on the Internet. Even beyond becoming the number one source of information, a growing number of businesses are depending on web search engines for customer acquisition. In this talk I will brief review the history of web search engines: The first generation of web search engines used text-only retrieval techniques. Google revolutionized the field by deploying the PageRank technology – an eigenvector-based analysis of the hyperlink structure- to analyze the web in order to produce relevant results. Moving forward, our goal is to achieve a better understanding of a page with a view towards producing even more relevant results.Google is powered by a large number of PCs. Using this infrastructure and striving to be as efficient as possible poses challenging systems problems but also various algorithmic challenges. I will discuss some of them in my talk.

The ability to represent and query continuously moving objects is important in many applications of spatio-temporal database systems. In this paper we develop data structures for answering various queries on moving objects, including range and proximity queries, and study tradeoffs between various performance measures—query time, data structure size, and accuracy of results.

There is no known algorithm that solves the general case of approximate string matching problem with the extended edit distance, where the edit operations are: insertion, deletion, mismatch, and swap, in time o(nm), where n is the length of the text and m is the length of the pattern.In the effort to study this problem, the edit operations where analysed independently. It turns out that the approximate matching problem with only the mismatch operation can be solved in time $O(n\sqrt{m \log m})$. If the only edit operation allowed is the swap, then the problem can be solved in time O(n log mlog σ), where σ = min(m,|Σ|).In this paper we show that the approximate string matching problem with the swap and mismatch as the edit operations, can be computed in time $O(n\sqrt{m \log m})$.

We introduce a problem directly inspired by its application to DWDM (dense wavelength division multiplexing) network design. We are given a set of demands to be carried over a network. Our goal is to choose a route for each demand and to decompose the network into a collection of edge-disjoint simple paths. These paths are called optical line systems. The cost of routing one unit of demand is the number of line systems with which the demand route overlaps; our design objective is to minimize the total cost over all demands. This cost metric is motivated by the need to avoid O-E-O (optical-electrical-optical) conversions in optical transmission as well as to minimize the expense of the equipment necessary to carry the traffic.For given line systems, it is easy to find the optimal demand routes. On the other hand, for given demand routes designing the optimal line systems can be NP-hard. We first present a 2-approximation for general network topologies. As optical networks often have low node degrees, we also offer an algorithm that finds the optimal solution for the special case in which the node degree is at most 3.If neither demand routes nor line systems are fixed, the situation becomes much harder. Even for a restricted scenario on a 3-regular Hamiltonian network, no efficient algorithm can guarantee a constant approximation better than 2. For general topologies, we offer a simple algorithm with an O(log K)- and an O(log n)-approximation where K is the number of demands and n is the number of nodes. For rings, a common special topology, we offer a 3/2-approximation.

In this paper we study the external memory planar point enclosure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surprisingly, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(log _B N+K/B) I/Os, where B is the disk block size. To obtain this bound, Ω(N/B1 − ε) disk blocks are needed for some constant ε> 0. With linear space, the best obtainable query bound is O(log₂N+K/B). To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds.

We study a basic problem in Multi-Queue switches. A switch connects m input ports to a single output port. Each input port is equipped with an incoming FIFO queue with bounded capacity B. A switch serves its input queues by transmitting packets arriving at these queues, one packet per time unit. Since the arrival rate can be higher than the transmission rate and each queue has limited capacity, packet loss may occur as a result of insufficient queue space. The goal is to maximize the number of transmitted packets. This general scenario models most current networks (e.g., IP networks) which only support a “best effort” service in which all packet streams are treated equally. A 2-competitive algorithm for this problem was designed in [4] for arbitrary B. Recently, a $\frac{17}{9}\approx 1.89$-competitive algorithm was presented for B>1 in [2]. Our main result in this paper shows that for B which is not too small our algorithm can do better than 1.89, and approach a competitive ratio of $\frac{e}{e-1}\approx 1.58$.

The problem of maximizing the weighted throughput in various switching settings has been intensively studied recently through competitive analysis. To date, the most general model that has been investigated is the standard CIOQ (Combined Input and Output Queued) switch architecture with internal fabric speedup S ≥ 1. CIOQ switches, that comprise the backbone of packet routing networks, are N × N switches controlled by a switching policy that incorporates two components: admission control and scheduling. An admission control strategy is essential to determine the packets stored in the FIFO queues in input and output ports, while the scheduling policy conducts the transfer of packets through the internal fabric, from input ports to output ports. The online problem of maximizing the total weighted throughput of CIOQ switches was recently investigated by Kesselman and Rosén in [12]. They presented two different online algorithms for the general problem that achieve non-constant competitive ratios (linear in either the speedup or the number of distinct values or logarithmic in the value range). We introduce the first constant-competitive algorithm for the general case of the problem, with arbitrary speedup and packet values. Specifically, our algorithm is 9.47-competitive, and is also simple and easy to implement.

Given n distinct points p₁,p₂, ..., p _n in the plane, the map labeling problem with four squares is to place n axis-parallel equi-sized squares Q₁, ..., Q _n of maximum possible size such that p _i is a corner of Q _i and no two squares overlap. This problem is NP-hard and no algorithm with approximation ratio better than $\frac{1}{2}$ exists unless P=NP [10].In this paper, we consider a scenario where we want to visualize the information gathered by smart dust, i.e. by a large set of simple devices, each consisting of a sensor and a sender that can gather sensor data and send it to a central station. Our task is to label (the positions of) these sensors in a way described by the labeling problem above. Since these devices are not positioned accurately (for example, they might be dropped from an airplane), this gives rise to consider the map labeling problem under the assumption, that the positions of the points are not fixed precisely, but perturbed by random noise. In other words, we consider the smoothed complexity of the map labeling problem. We present an algorithm that, under such an assumption and Gaussian random noise with sufficiently large variance, has linear smoothed complexity.

We present basic graph decomposition lemmas and show how they apply as key ingredients in the probabilistic embedding theorem stating that every n point metric space probabilistically embeds in ultrametrics with distortion O(log n) and in the proof of a similar bound for the spreading metrics paradigm in undirected graphs. This provides a unified framework for these metric methods which have numerous algorithmic applications.

In this paper we explore the effects of locality on the performance of paging algorithms. Traditional competitive analysis fails to explain important properties of paging assessed by practical experience. In particular, the competitive ratios of paging algorithms that are known to be efficient in practice (e.g. LRU) are as poor as those of naive heuristics (e.g. FWF). It has been recognized that the main reason for these discrepancies lies in an unsatisfactory modelling of locality of reference exhibited by real request sequences.Following [13], we explicitely address this issue, proposing an adversarial model in which the probability of requesting a page is also a function of the page’s age. In this way, our approach allows to capture the effects of locality of reference. We consider several families of distributions and we prove that the competitive ratio of LRU becomes constant as locality increases, as expected. This result is strengthened when the distribution satisfies a further concavity/convexity property: in this case, the competitive ratio of LRU is always constant.We also propose a family of distributions parametrized by locality of reference and we prove that the performance of FWF rapidly degrades as locality increases, while the converse happens for LRU.We think, our results provide one contribution to explaining the behaviours of these algorithms in practice.

The process of reading a DNA molecule can be divided into three phases: sequencing,assembly and finishing. The draft sequence after assembly has gaps with no coverage and regions of poor coverage. Finishing by walks is a process by which the DNA in these regions is resequenced. Selective sequencing is expensive and time consuming. Therefore, the laboratory process of finishing is modeled as an optimization problem aimed at minimizing laboratory cost. We give an algorithm that solves this problem optimally and runs in worst case $O(n^{1{3\over4}})$ time.

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, this gives a polynomial delay algorithm for listing the anti-vertices of the perfect matching polytope P(G) = {x ∈ ℝE | Hx = e, x ≥ 0}, where H is the incidence matrix of G. We also give similar generation algorithms for other related problems, including d-factors in bipartite graphs, and perfect 2-matchings in general graphs.

Direct routing is the special case of bufferless routing where N packets, once injected into the network, must be routed along specific paths to their destinations without conflicts. We give a general treatment of three facets of direct routing:Algorithms. We present a polynomial time greedy algorithm for arbitrary direct routing problems which is worst-case optimal, i.e., there exist instances for which no direct routing algorithm is better than the greedy. We apply variants of this algorithm to commonly used network topologies. In particular, we obtain near-optimal routing time for the tree and d-dimensional mesh, given arbitrary sources and destinations; for the butterfly and the hypercube, the same result holds for random destinations.Complexity. By a reduction from Vertex Coloring, we show that Direct Routing is inapproximable, unless P=NP.Lower Bounds for Buffering. We show that certain direct routing problems cannot be solved efficiently; to solve these problems, any routing algorithm needs buffers. We give non-trivial lower bounds on such buffering requirements for general routing algorithms.

It was shown recently by Fakcharoenphol et al. [7] that arbitrary finite metrics can be embedded into distributions over tree metrics with distortion O(log n). It is also known that this bound is tight since there are expander graphs which cannot be embedded into distributions over trees with better than Ω(log n) distortion.We show that this same lower bound holds for embeddings into distributions over any minor excluded family. Given a family of graphs F which excludes minor M where |M|=k, we explicitly construct a family of graphs with treewidth-(k+1) which cannot be embedded into a distribution over F with better than Ω(log n) distortion. Thus, while these minor excluded families of graphs are more expressive than trees, they do not provide asymptotically better approximations in general. An important corollary of this is that graphs of treewidth-k cannot be embedded into distributions over graphs of treewidth-(k–3) with distortion less than Ω(log n).We also extend a result of Alon et al. [1] by showing that for any k, planar graphs cannot be embedded into distributions over treewidth-k graphs with better than Ω(log n) distortion.

Upward planarity testing, or checking whether a directed graph has a drawing in which no edges cross and all edges point upward, is NP-complete. All of the algorithms for upward planarity testing developed previously focused on special classes of graphs. In this paper we develop a parameterized algorithm for upward planarity testing that can be applied to all graphs and runs in O(f(k)n3 + g(k,ℓ)n) time, where n is the number of vertices, k is the number of triconnected components, and ℓ is the number of cutvertices. The functions f(k) and g(k,ℓ) are defined as f(k)=k!8k and $g(k,\ell)=2^{3\cdot 2^\ell}k^{3\cdot 2^\ell} k!8^k$. Thus if the number of triconnected components and the number of cutvertices are small, the problem can be solved relatively quickly, even for a large number of vertices. This is the first parameterized algorithm for upward planarity testing.

In this paper we study efficient algorithms for computing equilibrium price in the Fisher model for a class of nonlinear concave utility functions, the logarithmic utility functions. We derive a duality relation between buyers and sellers under such utility functions, and use it to design a polynomial time algorithm for calculating equilibrium price, for the special case when either the number of sellers or the number of buyers is bounded by a constant.

We study approximation algorithms and hardness of approximation for several versions of the problem of packing Steiner trees. For packing edge-disjoint Steiner trees of undirected graphs, we show APX-hardness for 4 terminals. For packing Steiner-node-disjoint Steiner trees of undirected graphs, we show a logarithmic hardness result, and give an approximation guarantee of $O(\sqrt{n}\log n)$, where n denotes the number of nodes. For the directed setting (packing edge-disjoint Steiner trees of directed graphs), we show a hardness result of $\Omega(m^{\frac{1}{3}-\epsilon})$ and give an approximation guarantee of $O(m^{\frac{1}{2}+\epsilon})$, where m denotes the number of edges. The paper has several other results.

We study approximation hardness of the Minimum Dominating Set problem and its variants in undirected and directed graphs. We state the first explicit approximation lower bounds for various kinds of domination problems (connected, total, independent) in bounded degree graphs. For most of dominating set problems we prove asymptotically almost tight lower bounds. The results are applied to improve the lower bounds for other related problems such as the Maximum Induced Matching problem and the Maximum Leaf Spanning Tree problem.

The following buffer management problem is studied: packets with specified weights and deadlines arrive at a network switch and need to be forwarded so that the total weight of forwarded packets is maximized. A packet not forwarded before its deadline brings no profit. The main result is an online $\frac{64}{33}\approx 1.939$-competitive algorithm, the first deterministic algorithm for this problem with competitive ratio below 2. In the s-uniform case, where for all packets the deadline equals the arrival time plus s, we give an ${5}-\sqrt{10} \approx 1.838$-competitive algorithm. This algorithm achieves the same ratio in a more general scenario when all packets are similarly ordered. For the 2-uniform case we give an algorithm with ratio ≈ 1.377 and a matching lower bound.

Many network applications that need to distribute contents and data to a large number of clients use a hybrid scheme in which one or more multicast channel is used in parallel to a unicast dissemination. This way the application can distribute data using one of its available multicast channels or by sending one or more unicast transmissions. In such a model the utilization of the multicast channels is critical for the overall performance of the system. We study the scheduling algorithm of the sender in such a model. We describe this scheduling problem as an optimization problem where the objective is to maximize the utilization of the multicast channel. Our model captures the fact that it may be beneficial to multicast an object more than once (e.g. page update). Thus, the benefit depends, among other things, on the last time the object was sent, which makes the problem much more complex than previous related scheduling problems. Using the local ratio technique we obtain a 4-approximation algorithm for the case where the objects are of fixed size and a 10-approximation algorithm for the general case. We also consider a special case which may be of practical interest, and prove that a simple greedy algorithm is a 3-approximation algorithm in this case.

This paper considers the convergence problem in autonomous mobile robot systems. A natural algorithm for the problem requires the robots to move towards their center of gravity. Previously it was known that the gravitational algorithm converges in the synchronous or semi-synchronous model, and that two robots converge in the asynchronous model. The current paper completes the picture by proving the correctness of the gravitational algorithm in the fully asynchronous model for any number of robots. It also analyses its convergence rate, and establishes its convergence in the presence of crash faults.

This paper introduces a new family of in-place sorting algorithms, the partition sorts. They are appealing both for their relative simplicity and their efficient performance. They perform Θ(n log n) operations on the average, and $\Theta(n \log^2\!n)$ operations in the worst case.The partition sorts are related to another family of sorting algorithms discovered recently by Chen [Che02]. He showed empirically that one version ran faster, on the average, than quicksort, and that the algorithm family performed Θ(n log n) comparisons in the worst case; however no average case analysis was obtained.This paper completes the analysis of Chen’s algorithm family. In particular, a bound of n log n +O(n) comparisons and Θ(n log n) operations is shown for the average case, and $\Theta (n \log^2\!n)$ operations for the worst case. The average case analysis is somewhat unusual. It proceeds by showing that Chen’s sorts perform, on the average, no more comparisons than the partition sorts.Optimised versions of the partition sort and Chen’s algorithm are very similar in performance, and both run marginally faster than an optimised quasi-best-of-nine variant of quicksort [BM93]. They both have a markedly smaller variance than the quicksorts.

We present a distributed approximation algorithm that computes in every graph G a matching M of size at least $\frac 23 \beta(G),$ where β(G) is the size of a maximum matching in G. The algorithm runs in O(log4|V(G)|) rounds in the synchronous, message passing model of computation and matches the best known asymptotic complexity for computing a maximal matching in the same protocol. This improves the running time of an algorithm proposed recently by the authors in [2].

Given a point set $\mathcal{P} =\{p_1,\dots,p_n\}$ in the d-dimensional unit hypercube, we give upper bounds on the maximal expected number of extreme points when each point p _i is perturbed by small random noise chosen independently for each point from the same noise distribution Δ. Our results are parametrized by the variance of the noise distribution. For large variance we essentially consider the average case for distribution Δ while for variance 0 we consider the worst case. Hence our results give upper bounds on the number of extreme points where our input distributions range from average case to worst case.Our main contribution is a rather general lemma that can be used to obtain upper bounds on the expected number of extreme points for a large class of noise distributions. We then apply this lemma to obtain explicit bounds for random noise coming from the Gaussian normal distribution of variance σ2 and the uniform distribution in a hypercube of side length ε. For these noise distributions we show upper bounds of $\mathcal{O}((\frac{1}{\sigma})^d \cdot \log^{3/2 \cdot d - 1} n)$ and $\mathcal{O}((\frac{n\log n}{\epsilon} )^{d/(d+1)})$, respectively. Besides its theoretical motivation our model is also motivated by the observation that in many applications of convex hull algorithms the input data is inherently noisy, e.g. when the data comes from physical measurement or imprecise arithmetic is used.

We study the fixed parameter tractability of the parameterized counting and decision version of the restrictive H-coloring problem. These problems are defined by fixing the number of preimages of a subset C of the vertices in H through a partial weight assignment (H,C,K). We consider two families of partial weight assignment the simple and the plain. For simple partial weight assignments we show an FPT algorithm for counting list (H,C,K)-colorings and faster algorithms for its decision version. For the more general class of plain partial weight assignment we give an FPT algorithm for the (H,C,K)-coloring decision problem. We introduce the concept of compactor and an algorithmic technique, compactor enumeration, that allow us to design the FPT algorithms for the counting version (and probably export the technique to other problems).

The main contribution of this paper is an optimal bounded space online algorithm for variable-sized multidimensional packing. In this problem, hyperboxes must be packed in d-dimensional bins of various sizes, and the goal is to minimize the total volume of the used bins. We show that the method used can also be extended to deal with the problem of resource augmented multidimensional packing, where the online algorithm has larger bins than the offline algorithm that it is compared to. Finally, we give new lower bounds for unbounded space multidimensional bin packing of hypercubes.

We prove that all planar Laman graphs (i.e. minimally generically rigid graphs with a non-crossing planar embedding) can be generated from a single edge by a sequence of vertex splits. It has been shown recently [6,12] that a graph has a pointed pseudo-triangular embedding if and only if it is a planar Laman graph. Due to this connection, our result gives a new tool for attacking problems in the area of pseudo-triangulations and related geometric objects. One advantage of vertex splitting over alternate constructions, such as edge-splitting, is that vertex splitting is geometrically more local.We also give new inductive constructions for duals of planar Laman graphs and for planar generically rigid graphs containing a unique rigidity circuit. Our constructions can be found in O(n3) time, which matches the best running time bound that has been achieved for other inductive contructions.

We obtain faster algorithms for problems such as r-dimensional matching, r-set packing, graph packing, and graph edge packing when the size k of the solution is considered a parameter. We first establish a general framework for finding and exploiting small problem kernels (of size polynomial in k). Previously such a kernel was known only for triangle packing. This technique lets us combine, in a new and sophisticated way, Alon, Yuster and Zwick’s color-coding technique with dynamic programming on the structure of the kernel to obtain faster fixed-parameter algorithms for these problems. Our algorithms run in time O(n+2O(k)), an improvement over previous algorithms for some of these problems running in time O(n+kO(k)). The flexibility of our approach allows tuning of algorithms to obtain smaller constants in the exponent.

We introduce a model to study the temporal behaviour of selfish agents in networks. So far, most of the analysis of selfish routing is concerned with static properties of equilibria which is one of the most fundamental paradigms in classical Game Theory. By adopting a generalised approach of Evolutionary Game Theory we extend the model of selfish routing to study the dynamical behaviour of agents.For symmetric games corresponding to singlecommodity flow, we show that the game converges to a Nash equilibrium in a restricted strategy space. In particular we prove that the time for the agents to reach an ε-approximate equilibrium is polynomial in ε and only logarithmic in the ratio between maximal and optimal latency. In addition, we present an almost matching lower bound in the same parameters.Furthermore, we extend the model to asymmetric games corresponding to multicommodity flow. Here we also prove convergence to restricted Nash equilibria, and we derive upper bounds for the convergence time that are linear instead of logarithmic.

How efficiently can we search an unknown environment for a goal in unknown position? How much would it help if the environment were known? We answer these questions for simple polygons and for general graphs, by providing online search strategies that are as good as the best offline search algorithms, up to a constant factor. For other settings we prove that no such online algorithms exist.

In the incremental versions of Facility Location and k-Median, the demand points arrive one at a time and the algorithm must maintain a good solution by either adding each new demand to an existing cluster or placing it in a new singleton cluster. The algorithm can also merge some of the existing clusters at any point in time. We present the first incremental algorithm for Facility Location with uniform facility costs which achieves a constant performance ratio and the first incremental algorithm for k-Median which achieves a constant performance ratio using $\mbox{O}(k)$ medians.

We present a new algorithm for dynamic prefix-free coding, based on Shannon coding. We give a simple analysis and prove a better upper bound on the length of the encoding produced than the corresponding bound for dynamic Huffman coding. We show how our algorithm can be modified for efficient length-restricted coding, alphabetic coding and coding with unequal letter costs.

We present a Lagrangian relaxation technique to solve a class of linear programs with negative coefficients in the objective function and the constraints. We apply this technique to solve (the dual of) covering linear programs with upper bounds on the variables: min {c ⊤ x|Ax ≥ b, x ≤ u, x ≥ 0} where $c,u\in{\mathbb{R}}_{+}^m,b\in\mathbb{R}_+^n$ and $A\in\mathbb{R}_+^{n\times m}$ have non-negative entries. We obtain a strictly feasible, (1+ε)-approximate solution by making O(mε− 2logm + min {n,loglogC}) calls to an oracle that finds the most-violated constraint. Here C is the largest entry in c or u, m is the number of variables, and n is the number of covering constraints. Our algorithm follows naturally from the algorithm for the fractional packing problem and improves the previous best bound of O(mε− − 2log (mC)) given by Fleischer [1]. Also for a fixed ε, if the number of covering constraints is polynomial, our algorithm makes a number of oracle calls that is strongly polynomial.

Negotiation-range mechanisms offer a novel approach to achieving efficient markets based on finding the maximum weighted matching in a weighted bipartite graph connecting buyers and sellers. Unlike typical markets, negotiation-range mechanisms establish negotiation terms between paired bidders rather than set a final price for each transaction. This subtle difference allows single-unit heterogenous negotiation-range markets to achieve desirable properties that cannot coexist in typical markets. This paper extends the useful properties of negotiation-range mechanisms to include coalition-resistance, making them the first markets known to offer protection from coalitions. Additionally, the notion of negotiation-range mechanisms is extended to include a restricted setting of combinatorial markets.

Let G=(V,E) be an undirected multi-graph with a special vertex root ∈ V, and where each edge e ∈ E is endowed with a length l(e) ≥ 0 and a capacity c(e) > 0. For a path P that connects u and v, the transmission time of P is defined as $t(P)=\sum_{e \in P} l(e) + \max_{e \in P} {1 \over c(e)}$. For a spanning tree T, let P$_{u,v}^{T}$ be the unique u–v path in T. The quickest radius spanning tree problem is to find a spanning tree T of G such that $\max _{v \in V} t(P^T_{root,v})$ is minimized. In this paper we present a 2-approximation algorithm for this problem, and show that unless P =NP, there is no approximation algorithm with performance guarantee of 2 – ε for any ε >0. The quickest diameter spanning tree problem is to find a spanning tree T of G such that $\max_{u,v \in V} t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation to this problem, and prove that unless P=NP there is no approximation algorithm with performance guarantee of ${3 \over 2}-\epsilon$ for any ε >0.

We present a randomized $\left({89\over169}-\epsilon\right)$-approximation algorithm for the weighted maximum triangle packing problem, for any given ε> 0. This is the first algorithm for this problem whose performance guarantee is better than ${1\over2}$. The algorithm also improves the best known approximation bound for the maximum 2-edge path packing problem.

Two equal length strings s and s′, over alphabets Σ _s and Σ _s′, parameterize match if there exists a bijection π:Σ _s → Σ _s′, such that π (s)=s′, where π (s) is the renaming of each character of s via π. Approximate parameterized matching is the problem of finding for a pattern p, at each location of a text string t, a bijection π that maximizes the number of characters that are mapped from p to the appropriate |p|-length substring of t.Our main result is an O(nk1.5+mklog m) time algorithm for this problem where m=|p| and n = |t|.

The weighted rectangle multi-stabbing problem (WRMS) can be described as follows: given is a grid in $\mathop{I\!\!R}^2$consisting of columns and rows each having a positive integral weight, and a set of closed axis-parallel rectangles each having a positive integral demand. The rectangles are placed arbitrarily in the grid with the only assumption that each rectangle is intersected by at least one column and at least one row. The objective is to find a minimum weight (multi)set of columns and rows of the grid so that for each rectangle the total multiplicity of selected columns and rows stabbing it is at least its demand. (A column or row is said to stab a rectangle if it intersects it.)

We show the first o(n2) algorithm for coloring vertices of triangle-free planar graphs using three colors. The time complexity of the algorithm is $\mathcal{O}$ (n log n). Our approach can be also used to design $\mathcal{O}$(n polylog n)-time algorithms for two other similar coloring problems.A remarkable ingredient of our algorithm is the data structure processing short path queries introduced recently in [9]. In this paper we show how to adapt it to the fully dynamic environment where edge insertions and deletions are allowed.

We study the complexity of and algorithms to construct approximations of the union of lines, and of the Minkowski sum of two simple polygons. We also study thick unions of lines and Minkowski sums, which are inflated with a small disc. Let b=D/ε be the ratio of the diameter of the region of interest and the distance (or error) of the approximation. We present upper and lower bounds on the combinatorial complexity of approximate and thick unions of lines and Minkowski sums, with bounds expressed in b and the input size n. We also give efficient algorithms for the computation.

We propose a novel randomized algorithm for computing a dominating set based clustering in wireless ad-hoc and sensor networks. The algorithm works under a model which captures the characteristics of the set-up phase of such multi-hop radio networks: asynchronous wake-up, the hidden terminal problem, and scarce knowledge about the topology of the network graph. When modelling the network as a unit disk graph, the algorithm computes a dominating set in polylogarithmic time and achieves a constant approximation ratio.

For planar graphs, counting the number of perfect matchings (and hence determining whether there exists a perfect matching) can be done in NC [4,10]. For planar bipartite graphs, finding a perfect matching when one exists can also be done in NC [8,7]. However in general planar graphs (when the bipartite condition is removed), no NC algorithm for constructing a perfect matching is known.We address a relaxation of this problem. We consider the fractional matching polytope $\mathbb{{\cal P}}(G)$ of a planar graph G. Each vertex of this polytope is either a perfect matching, or a half-integral solution: an assignment of weights from the set {0,1/2,1} to each edge of G so that the weights of edges incident on each vertex of G add up to 1 [6]. We show that a vertex of this polytope can be found in NC, provided G has at least one perfect matching to begin with. If, furthermore, the graph is bipartite, then all vertices are integral, and thus our procedure actually finds a perfect matching without explicitly exploiting the bipartiteness of G.

Given a polygonal region with n vertices, a group of searchers with vision are trying to find an intruder inside the region. Can the searchers find the intruder or can the intruder evade searchers’ detection for ever? It is likely that the answer depends on the visibility of the searchers, but we present quite a general result against it. We assume that the searchers always form a simple polygonal chain within the polygon such that the first searcher moves along the boundary of the polygon and any two consecutive searchers along the chain are always mutually visible. Two types of visibility of the searchers are considered: on the one extreme every searcher has 360° vision – called an ∞-searcher; on the other extreme every searcher has one-ray vision – called a 1-searcher. We show that if any polygon is searchable by a chain of ∞-searchers it is also searchable by a chain of 1-searchers consisting of the same number of searchers as the ∞-searchers. Our proof uses simple simulation techniques. The proof is also interesting from an algorithmic point of view because it allows an O(n2)-time algorithm for finding the minimum number of 1-searchers (and thus ∞-searchers) required to search a polygon [9]. No polynomial-time algorithm for a chain of multiple ∞-searchers was known before, even for a chain of two ∞-searchers.

There has been a considerable amount of recent research on load balancing for distributed hash tables (DHTs), a fundamental tool in Peer-to-Peer networks. Previous work in this area makes the assumption of homogeneous processors, where each processor has the same power. Here, we study load balancing strategies for a class of DHTs, called hypercubic DHTs, with heterogenous processors. We assume that each processor has a size, representing its resource capabilities, and our objective is to balance the load density (load divided by size) over the processors in the system. Our main focus is the offline version of this load balancing problem, where all of the processor sizes are known in advance. This reduces to a natural question concerning the construction of binary trees. Our main result is an efficient algorithm for this problem. The algorithm is simple to describe, but proving that it does in fact solve our binary tree construction problem is not so simple. We also give upper and lower bounds on the competitive ratio of the online version of the problem.

We consider the generalized version of the stable marriage problem where each man and woman’s preference list may have ties. Furthermore, each man and woman wishes to be matched to as many of acceptable partners as possible, up to his or her specified quota. Many-to-many version of the stable marriage problem has wide applications in matching retailers and shopkeepers in e-marketplaces. We investigate different forms of stability in this context and describe an algorithm to find strongly stable matchings (if one exists) in the context of multiple partner stable marriage problem with ties. In the context of Hospital-Residents problem for which only the resident-oriented algorithm for finding a strongly stable matching is known, this algorithm gives a hospital-oriented version (for the same) as well. Furthermore, in any instance of many-to-many stable marriage problem with ties, we show that the set of strongly stable matchings forms a distributive lattice. The results in this paper extend those already known for the one-to-one version and many-to-one version (Hospitals-Residents problem) of the problem.

In classical network flow theory, flow being sent from a source to a destination may be split into a large number of chunks traveling on different paths through the network. This effect is undesired or even forbidden in many applications. Kleinberg introduced the unsplittable flow problem where all flow traveling from a source to a destination must be sent on only one path. This is a generalization of the NP-complete edge-disjoint paths problem. In particular, the randomized rounding technique of Raghavan and Thompson can be applied. A generalization of unsplittable flows are k-splittable flows where the number of paths used by a commodity i is bounded by a given integer k _i .The contribution of this paper is twofold. First, for the unsplittable flow problem, we prove a lower bound of Ω(log m/loglog m) on the performance of randomized rounding. This result almost matches the best known upper bound of O(log m). To the best of our knowledge, the problem of finding a non-trivial lower bound has so far been open.In the second part of the paper, we study a new variant of the k-splittable flow problem with additional constraints on the amount of flow being sent along each path. The motivation for these constraints comes from the following packing and routing problem: A commodity must be shipped using a given number of containers of given sizes. First, one has to make a decision on the fraction of the commodity packed into each container. Then, the containers must be routed through a network whose edges correspond, for example, to ships or trains. Each edge has a capacity bounding the total size or weight of containers which are being routed on it. We present approximation results for two versions of this problem with multiple commodities and the objective to minimize the congestion of the network. The key idea is to reduce the problem under consideration to an unsplittable flow problem while only losing a constant factor in the performance ratio.

We present a randomized algorithm for finding maximum matchings in planar graphs in time O(nω/2), where ω is the exponent of the best known matrix multiplication algorithm. Since ω< 2.38, this algorithm breaks through the O(n1.5) barrier for the matching problem. This is the first result of this kind for general planar graphs.Our algorithm is based on the Gaussian elimination approach to maximum matchings introduced in [1].

We generalize univariate multipoint evaluation of polynomials of degree n at sublinear amortized cost per point. More precisely, it is shown how to evaluate a bivariate polynomial p of maximum degree less than n, specified by its n2 coefficients, simultaneously at n2 given points using a total of $\mathcal{O}(n^{2.667})$ arithmetic operations. In terms of the input size N being quadratic in n, this amounts to an amortized cost of $\mathcal{O}(N^{0.334})$ per point.

This paper considers integer sorting on a RAM. We show that adaptive sorting of a sequence with qn inversions is asymptotically equivalent to multisorting groups of at most q keys, and a total of n keys. Using the recent $O(n\sqrt{\log\log n})$ expected time sorting of Han and Thorup on each set, we immediately get an adaptive expected sorting time of $O(n\sqrt{\log\log q})$. Interestingly, for any positive constant ε, we show that multisorting and adaptive inversion sorting can be performed in linear time if $q\leq 2^{(\log n)^{1-\varepsilon}}$. We also show how to asymptotically improve the running time of any traditional sorting algorithm on a class of inputs much broader than those with few inversions.

We fix two rectangles with integer dimensions. We give a quadratic time algorithm which, given a polygon F as input, produces a tiling of F with translated copies of our rectangles (or indicates that there is no tiling). Moreover, we prove that any pair of tilings can be linked by a sequence of local transformations of tilings, called flips. This study is based on the use of J. H. Conway’s tiling groups and extends the results of C. Kenyon and R. Kenyon (limited to the case when each rectangle has a side of length 1).

We obtain the following results related to dynamic versions of the shortest-paths problem:(i). Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem. We also obtain slightly weaker results for the corresponding unweighted problems.(ii). A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of $\tilde{O}(m\sqrt n)$ and a worst case query time is O(n3/4).(iii). A deterministic O(n2log n) time algorithm for constructing a (log n)-spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance.

We consider the problem of linear space deterministic dictionaries over the universe {0,1}w. The model of computation is the unit-cost RAM with word length w. Many modern solutions to the dictionary problem are weakly non-uniform, i.e. they require a number of constants to be computed at “compile time” for stated time bounds to hold. We present an improvement in the class of dictionaries free from weak non-uniformity and with stress on faster searches. Various search-update time trade-offs are obtained. The time bounds for the construction of a static dictionary and update bounds for dynamic case contain log w term; the query times are independent of w. In the case of optimal query time, we achieve construction time O(n1 + εlog w), for any ε> 0. The construction requires division, whereas searching uses multiplication only.

Let A and B two n× n matrices over a ring R (e.g., the reals or the integers) each containing at most m non-zero elements. We present a new algorithm that multiplies A and B using O(m0.7n1.2+n2 + o(1)) algebraic operations (i.e., multiplications, additions and subtractions) over R. For m≤ n1.14, the new algorithm performs an almost optimal number of only n2 + o(1) operations. For m≤ n1.68, the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O(n2.38) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.

The size of the Pareto curve for the bicriteria version of the knapsack problem is polynomial on average. This has been shown for various random input distributions. We experimentally investigate the number of Pareto optimal knapsack fillings. Our experiments suggests that the theoretically proven upper bound of O(n3) for uniform instances and O(φμn4) for general probability distributions is not tight. Instead we conjecture an upper bound of O(φμn2) matching a lower bound for adversarial weights.In the second part we study advanced algorithmic techniques for the knapsack problem. We combine several ideas that have been used in theoretical studies to bound the average-case complexity of the knapsack problem. The concepts used are simple and have been known since at least 20 years, but apparently have not been used together. The result is a very competitive code that outperforms the best known implementation Combo by orders of magnitude also for harder random knapsack instances.

Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree. The degeneracy is polynomial time computable. We introduce the notion of contraction degeneracy: the maximum over all graphs that can be obtained by contracting edges of the minimum degree. We show that the problem to compute the contraction degeneracy is NP-hard, but for fixed k, it is polynomial time decidable if a given graph G has contraction degeneracy at least k. Heuristics for computing the contraction degeneracy are proposed and experimentally evaluated. It is shown that these can lead to considerable improvements to the lower bound for treewidth. A similar study is made for the combination of contraction with Lucena’s lower bound based on Maximum Cardinality Search [12] .

The task of balancing dynamically generated work load occurs in a wide range of parallel and distributed applications. Diffusion based schemes, which belong to the class of nearest neighbor load balancing algorithms, are a popular way to address this problem. Originally created to equalize the amount of arbitrarily divisible load among the nodes of a static and homogeneous network, they have been generalized to heterogeneous topologies. Additionally, some simple diffusion algorithms have been adapted to work in dynamic networks as well. However, if the load is not divisible arbitrarily but consists of indivisible unit size tokens, diffusion schemes are not able to balance the load properly. In this paper we consider the problem of balancing indivisible unit size tokens on dynamic and heterogeneous systems. By modifying a randomized strategy invented for homogeneous systems, we can achieve an asymptotically minimal expected overload in l₁, l₂ and l_∞ norm while only slightly increasing the run-time by a logarithmic factor. Our experiments show that this additional factor is usually not required in applications.

We study polynomials of degree up to 4 over the rationals or a computable real subfield. Our motivation comes from the need to evaluate predicates in nonlinear computational geometry efficiently and exactly. We show a new method to compare real algebraic numbers by precomputing generalized Sturm sequences, thus avoiding iterative methods; the method, moreover handles all degenerate cases. Our first contribution is the determination of rational isolating points, as functions of the coefficients, between any pair of real roots. Our second contribution is to exploit invariants and Bezoutian subexpressions in writing the sequences, in order to reduce bit complexity. The degree of the tested quantities in the input coefficients is optimal for degree up to 3, and for degree 4 in certain cases. Our methods readily apply to real solving of pairs of quadratic equations, and to sign determination of polynomials over algebraic numbers of degree up to 4. Our third contribution is an implementation in a new module of library synaps v2.1. It improves significantly upon the efficiency of certain publicly available implementations: Rioboo’s approach on axiom, the package of Guibas-Karavelas-Russel [11], and core v1.6, maple v9, and synaps v2.0. Some existing limited tests had shown that it is faster than commercial library leda v4.5 for quadratic algebraic numbers.

Arrangements of planar curves are fundamental structures in computational geometry. We describe the recent developments in the arrangement package of Cgal, the Computational Geometry Algorithms Library, making it easier to use, to extend and to adapt to a variety of applications. This improved flexibility of the code does not come at the expense of efficiency as we mainly use generic-programming techniques, which make dexterous use of the compilation process. To the contrary, we expedited key operations as we demonstrate by experiments.

The computation of dominators in a flowgraph has applications in program optimization, circuit testing, and other areas. Lengauer and Tarjan [17] proposed two versions of a fast algorithm for finding dominators and compared them experimentally with an iterative bit vector algorithm. They concluded that both versions of their algorithm were much faster than the bit-vector algorithm even on graphs of moderate size. Recently Cooper et al. [9] have proposed a new, simple, tree-based iterative algorithm. Their experiments suggested that it was faster than the simple version of the Lengauer-Tarjan algorithm on graphs representing computer program control flow. Motivated by the work of Cooper et al., we present an experimental study comparing their algorithm (and some variants) with careful implementations of both versions of the Lengauer-Tarjan algorithm and with a new hybrid algorithm. Our results suggest that, although the performance of all the algorithms is similar, the most consistently fast are the simple Lengauer-Tarjan algorithm and the hybrid algorithm, and their advantage increases as the graph gets bigger or more complicated.

Our work is motivated by the problem of managing data on storage devices, typically a set of disks. Such storage servers are used as web servers or multimedia servers, for handling high demand for data. As the system is running, it needs to dynamically respond to changes in demand for different data items. There are known algorithms for mapping demand to a layout. When the demand changes, a new layout is computed. In this work we study the data migration problem, which arises when we need to quickly change one layout to another. This problem has been studied earlier when for each disk the new layout has been prescribed. However, to apply these algorithms effectively, we identify another problem that we refer to as the correspondence problem, whose solution has a significant impact on the solution for the data migration problem. We study algorithms for the data migration problem in more detail and identify variations of the basic algorithm that seem to improve performance in practice, even though some of the variations have poor worst case behavior.

The algorithms of computational geometry are designed for a machine model with exact real arithmetic. Substituting floating point arithmetic for the assumed real arithmetic may cause implementations to fail. Although this is well known, there is no comprehensive documentation of what can go wrong and why. In this extended abstract, we study a simple incremental algorithm for planar convex hulls and give examples which make the algorithm fail in all possible ways. We also show how to construct failure-examples semi-systematically and discuss the geometry of the floating point implementation of the orientation predicate. We hope that our work will be useful for teaching computational geometry. The full paper is available at www.mpi-sb.mpg.de/~mehlhorn/ftp/ClassRoomExamples.ps. It contains further examples, more theory, and color pictures. We strongly recommend to read the full paper instead of this extended abstract.

We introduce a new stable minimum storage algorithm for merging that needs $O(m\log(\frac{n}{m}+1))$ element comparisons, where m and n are the sizes of the input sequences with m≤ n. According to the lower bound for merging, our algorithm is asymptotically optimal regarding the number of comparisons.The presented algorithm rearranges the elements to be merged by rotations, where the areas to be rotated are determined by a simple principle of symmetric comparisons. This style of minimum storage merging is novel and looks promising.Our algorithm has a short and transparent definition. Experimental work has shown that it is very efficient and so might be of high practical interest.

A rectangular cartogram is a type of map where every region is a rectangle. The size of the rectangles is chosen such that their areas represent a geographic variable (e.g., population). Good rectangular cartograms are hard to generate: The area specifications for each rectangle may make it impossible to realize correct adjacencies between the regions and so hamper the intuitive understanding of the map.Here we present the first algorithms for rectangular cartogram construction. Our algorithms depend on a precise formalization of region adjacencies and are building upon existing VLSI layout algorithms. Furthermore, we characterize a non-trivial class of rectangular subdivisions for which exact cartograms can be efficiently computed. An implementation of our algorithms and various tests show that in practice, visually pleasing rectangular cartograms with small cartographic error can be effectively generated.

Modern multiprocessor systems offer advanced synchronization primitives, built in hardware, to support the development of efficient parallel algorithms. In this paper we develop a simple and efficient algorithm for atomic registers (variables) of arbitrary length. The simplicity and better complexity of the algorithm is achieved via the utilization of two such common synchronization primitives. In this paper we also evaluate the performance of our algorithm and the performance of a practical previously know algorithm that is based only on read and write primitives. The evaluation is performed on 3 well-known, parallel architectures. This evaluation clearly shows that both algorithms are practical and that as the size of the register increases our algorithm performs better, accordingly to its complexity behavior.

Game tree search is the core of most attempts to make computers play games. Yet another approach is to store all possible positions in a database and to precompute the true values for all the positions. The databases allow computers to play optimally, in the sense that they will win every game once they reach a winning position. Moreover, they will never lose from a draw or win position. This is the situation that we find in games like Connect-4, in endgames of chess and in many other settings. Nevertheless, it has been observed that the programs do not play strongly when they have to play a tournament with strong, but non-perfect human players attending. In this paper we propose a mixture of game tree search and the database approach which attacks this problem on the basis of a known theoretical error analysis in game trees. Experiments show encouraging results.

We consider a scenario where stops are to be placed along an already existing public transportation network in order to improve its attractiveness for the customers. The core problem is a geometric set covering problem which is $\mathcal{NP}$-hard in general. However, if the corresponding covering matrix has the consecutive ones property, it is solvable in polynomial time. In this paper, we present data reduction techniques for set covering and report on an experimental study considering real world data from railway systems as well as generated instances. The results show that data reduction works very well on instances that are in some sense “close” to having the consecutive ones property. In fact, the real world instances considered could be reduced significantly, in most cases even to triviality. The study also confirms and explains findings on similar techniques for related problems.

IP address lookup is a critical operation for high bandwidth routers in packet switching networks such as Internet. The lookup is a non-trivial operation since it requires searching for the longest prefix, among those stored in a (large) given table, matching the IP address. Ever increasing routing tables size, traffic volume and links speed demand new and more efficient algorithms. Moreover, the imminent move to IPv6 128-bit addresses will soon require a rethinking of previous technical choices. This article describes a the new data structure for solving the IP table look up problem christened the Adaptive Stratified Tree (AST). The proposed solution is based on casting the problem in geometric terms and on repeated application of efficient local geometric optimization routines. Experiments with this approach have shown that in terms of storage, query time and update time the AST is at a par with state of the art algorithms based on data compression or string manipulations (and often it is better on some of the measured quantities).

Sample sort, a generalization of quicksort that partitions the input into many pieces, is known as the best practical comparison based sorting algorithm for distributed memory parallel computers. We show that sample sort is also useful on a single processor. The main algorithmic insight is that element comparisons can be decoupled from expensive conditional branching using predicated instructions. This transformation facilitates optimizations like loop unrolling and software pipelining. The final implementation, albeit cache efficient, is limited by a linear number of memory accesses rather than the $\mathcal{O}\!\left(n\log n\right)$ comparisons. On an Itanium 2 machine, we obtain a speedup of up to 2 over std::sort from the GCC STL library, which is known as one of the fastest available quicksort implementations.

Spanners are sparse subgraphs that preserve distances up to a given factor in the underlying graph. Recently spanners have found important practical applications in metric space searching and message distribution in networks. These applications use some variant of the so-called greedy algorithm for constructing the spanner — an algorithm that mimics Kruskal’s minimum spanning tree algorithm. Greedy spanners have nice theoretical properties, but their practical performance with respect to total weight is unknown. In this paper we give an exact algorithm for constructing minimum-weight spanners in arbitrary graphs. By using the solutions (and lower bounds) from this algorithm, we experimentally evaluate the performance of the greedy algorithm for a set of realistic problem instances.

We propose the linear axis, a new skeleton for polygonal shapes. It is related to the medial axis and the straight skeleton, being the result of a wavefront propagation process. The wavefront is linear and propagates by translating edges at constant speed. The initial wavefront is an altered version of the original polygon: zero-length edges are added at reflex vertices. The linear axis is a subset of the straight skeleton of the altered polygon. In this way, the counter-intuitive effects in the straight skeleton caused by sharp reflex vertices are alleviated. We introduce the notion of ε-equivalence between two skeletons, and give an algorithm that computes the number of zero-length edges for each reflex vertex which yield a linear axis ε-equivalent to the medial axis. This linear axis and thus the straight skeleton can be computed from the medial axis in linear time for polygons with a constant number of “nearly co-circular” sites. All previous algorithms for straight skeleton computation are sub-quadratic.

The non-additive shortest path (NASP) problem asks for finding an optimal path that minimizes a certain multi-attribute non-linear cost function. In this paper, we consider the case of a non-linear convex and non-decreasing function on two attributes. We present an efficient polynomial algorithm for solving a Lagrangian relaxation of NASP. We also present an exact algorithm that is based on new heuristics we introduce here, and conduct a comparative experimental study with synthetic and real-world data that demonstrates the quality of our approach.