Approximation and Online Algorithms

Frontmatter

Approximation Algorithms for Scheduling Problems with Exact Delays

Abstract

We give first constant-factor approximations for various cases of the coupled-task single machine and two-machine flow shop scheduling problems with exact delays and makespan as the objective function. In particular, we design 3.5- and 3-approximation algorithms for the general cases of the single-machine and the two-machine problems, respectively. We also prove that the existence of a (2−ε)-approximation algorithm for the single-machine problem as well as the existence of a (1.5−ε)-approximation algorithm for the two-machine problem implies P=NP. The inapproximability results are valid for the cases when the operations of each job have equal processing times and for these cases the approximation ratios achieved by our algorithms are very close to best possible: we prove that the single machine problem is approximable within a factor of 2.5 and the two-machine problem is approximable within a factor of 2.

Alexander A. Ageev, Alexander V. Kononov

Bidding to the Top: VCG and Equilibria of Position-Based Auctions

Abstract

Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount as their bid in the auction. This bid is interpreted as the maximum amount the advertiser is willing to pay per click on its ad. When search queries arrive, the bids are used to rank the ads linearly on the search result page. Advertisers seek to be high on the list, as this attracts more attention and more clicks. The advertisers pay for each user who clicks on their ad, and the amount charged depends on the bids of all the advertisers participating in the auction.

We study the problem of ranking ads and associated pricing mechanisms when the advertisers not only specify a bid, but additionally express their preference for positions in the list of ads. In particular, we study prefix position auctions where advertiser i can specify that she is interested only in the top κ _i positions.

We present a simple allocation and pricing mechanism that generalizes the desirable properties of current auctions that do not have position constraints. In addition, we show that our auction has an envy-free [1] or symmetric [2] Nash equilibrium with the same outcome in allocation and pricing as the well-known truthful Vickrey-Clarke-Groves (VCG) auction. Furthermore, we show that this equilibrium is the best such equilibrium for the advertisers in terms of the profit made by each advertiser. We also discuss other position-based auctions.

Gagan Aggarwal, Jon Feldman, S. Muthukrishnan

Coping with Interference: From Maximum Coverage to Planning Cellular Networks

Abstract

Cell planning includes planning a network of base stations providing a coverage of the service area with respect to current and future traffic requirements, available capacities, interference, and the desired quality-of-service. This paper studies cell planning under budget constraints through a very close-to-practice model. This problem generalizes several problems such as budgeted maximum coverage, budgeted unique coverage, and the budgeted version of the facility location problem.

We present the first study of the budgeted cell planning problem. Our model contains capacities, non-uniform demands, and interference that are modeled by a penalty-based mechanism that may reduce the contribution of a base station to a client as a result of simultaneously covering this client by other base stations. We show that this very general problem is NP-hard to approximate and thus we define a restrictive version of the problem that covers all interesting practical scenarios. We show that although this variant remains NP-hard, it can be approximated within a factor of \(\frac{e-1}{2e-1}\) of the optimum.

David Amzallag, Joseph (Seffi) Naor, Danny Raz

Online Dynamic Programming Speedups

Abstract

Consider the Dynamic Program h(n) = min _{1 ≤ j ≤ n} a(n,j) for n = 1, 2, ..., N. For arbitrary values of a(n,j), calculating all the h(n) requires Θ(N ²) time. It is well known that, if the a(n,j) satisfy the Monge property, then there are techniques to reduce the time down to O(N). This speedup is inherently static, i.e., it requires N to be known in advance.

In this paper we show that if the a(n,j) satisfy a stronger condition, then it is possible, without knowing N in advance, to compute the values of h(n) in the order of n = 1, 2, ..., N, in O(1) amortized time per h(n). This maintains the DP speedup online, in the sense that the time to compute all h(n) is O(N). A slight modification of our algorithm restricts the worst case time to be O(logN) per h(n), while maintaining the amortized time bound. For a(n,j) that satisfy our stronger condition, our algorithm is also simpler to implement than the standard Monge speedup.

We illustrate the use of our algorithm on two examples from the literature. The first shows how to make the speedup of the D-median on a line problem in an online settings. The second shows how to improve the running time for a DP used to reduce the amount of bandwidth needed when paging mobile wireless users.

Amotz Bar-Noy, Mordecai J. Golin, Yan Zhang

Covering Many or Few Points with Unit Disks

Abstract

Let P be a set of n weighted points. We study approximation algorithms for the following two continuous facility-location problems.

In the first problem we want to place m unit disks, for a given constant m≥1, such that the total weight of the points from P inside the union of the disks is maximized. We present a deterministic algorithm that can compute, for any ε>0, a (1−ε)-approximation to the optimal solution in O(n logn + ε \(^{{\rm -4}{\it m}}\)log\(^{\rm 2{\it m}}\) (1/ε)) time.

In the second problem we want to place a single disk with center in a given constant-complexity region X such that the total weight of the points from P inside the disk is minimized. Here we present an algorithm that can compute, for any ε>0, with high probability a (1+ε)-approximation to the optimal solution in O(n (log³ n + ε ^− 4 log² n )) expected time.

Mark de Berg, Sergio Cabello, Sariel Har-Peled

On the Minimum Corridor Connection Problem and Other Generalized Geometric Problems

Abstract

In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into “rooms”, one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give an subexponential time exact algorithm. For the special case of k-outerplanar graphs the running time becomes O(n ³). We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.

Hans Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, René Sitters, Thomas Wolle

Online k-Server Routing Problems

Abstract

In an online k-server routing problem, a crew of k servers has to visit points in a metric space as they arrive in real time. Possible objective functions include minimizing the makespan (k-Traveling Salesman Problem) and minimizing the average completion time (k-Traveling Repairman Problem). We give competitive algorithms, resource augmentation results and lower bounds for k-server routing problems on several classes of metric spaces. Surprisingly, in some cases the competitive ratio is dramatically better than that of the corresponding single server problem. Namely, we give a 1+O((logk)/k)-competitive algorithm for the k-Traveling Salesman Problem and the k-Traveling Repairman Problem when the underlying metric space is the real line. We also prove that similar results cannot hold for the Euclidean plane.

Vincenzo Bonifaci, Leen Stougie

Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem

Abstract

The paging algorithm LRU-2 was proposed for use in data-base disk buffering and shown experimentally to perform better than LRU [O’Neil, O’Neil, and Weikum, 1993]. We compare LRU-2 and LRU theoretically, using both the standard competitive analysis and the newer relative worst order analysis. The competitive ratio for LRU-2 is shown to be 2k for cache size k, which is worse than LRU’s competitive ratio of k. However, using relative worst order analysis, we show that LRU-2 and LRU are asymptotically comparable in LRU-2’s favor, giving a theoretical justification for the experimental results.

Joan Boyar, Martin R. Ehmsen, Kim S. Larsen

Improved Approximation Bounds for Edge Dominating Set in Dense Graphs

Abstract

We analyze the simple greedy algorithm that iteratively removes the endpoints of a maximum-degree edge in a graph, where the degree of an edge is the sum of the degrees of its endpoints. This algorithm provides a 2-approximation to the minimum edge dominating set and minimum maximal matching problems. We refine its analysis and give an expression of the approximation ratio that is strictly less than 2 in the cases where the input graph has n vertices and at least \(\epsilon \binom{n}{2}\) edges, for ε> 1/2. This ratio is shown to be asymptotically tight for ε> 1/2.

Jean Cardinal, Stefan Langerman, Eythan Levy

A Randomized Algorithm for Online Unit Clustering

Abstract

In this paper, we consider the online version of the following problem: partition a set of input points into subsets, each enclosable by a unit ball, so as to minimize the number of subsets used. In the one-dimensional case, we show that surprisingly the naïve upper bound of 2 on the competitive ratio can be beaten: we present a new randomized 15/8-competitive online algorithm. We also provide some lower bounds and an extension to higher dimensions.

Timothy M. Chan, Hamid Zarrabi-Zadeh

On Hierarchical Diameter-Clustering, and the Supplier Problem

Abstract

Given a data set in metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter, and the hierarchical k-supplier problem with customers arriving online.

We prove that two previously known algorithms for hierarchical clustering, one (offline) due to Dasgupta and Long and the other (online) due to Charikar, Chekuri, Feder and Motwani, are essentially the same algorithm when points are considered in the same order. We show that the analysis of both algorithms are tight and exhibit a new lower bound for hierarchical clustering. Finally we present the first constant factor approximation algorithm for the online hierarchical k-supplier problem.

Aparna Das, Claire Kenyon

Bin Packing with Rejection Revisited

Abstract

We consider the following generalization of bin packing. Each item is associated with a size bounded by 1, as well as a rejection cost, that an algorithm must pay if it chooses not to pack this item. The cost of an algorithm is the sum of all rejection costs of rejected items plus the number of unit sized bins used for packing all other items.

We first study the offline version of the problem and design an APTAS for it. This is a non-trivial generalization of the APTAS given by Fernandez de la Vega and Lueker for the standard bin packing problem. We further give an approximation algorithm of absolute approximation ratio \(\frac 32\), this value is best possible unless P= NP.

Finally, we study an online version of the problem. For the bounded space variant, where only a constant number of bins can be open simultaneously, we design a sequence an algorithms whose competitive ratios tend to the best possible asymptotic competitive ratio. We show that our algorithms have the same asymptotic competitive ratios as these known for the standard problem, whose ratios tend to Π_∞≈1.691. Furthermore, we introduce an unbounded space algorithm which achieves a much smaller asymptotic competitive ratio. All our results improve upon previous results of Dósa and He.

Leah Epstein

On Bin Packing with Conflicts

Abstract

We consider the offline and online versions of a bin packing problem called bin packing with conflicts. Given a set of items V={ 1,2, ...,n} with sizes s ₁,s ₂ ...,s _n ∈[0,1] and a conflict graph G=(V,E), the goal is to find a partition of the items into independent sets of G, where the total size of each independent set is at most one, so that the number of independent sets in the partition is minimized. This problem is clearly a generalization of both the classical (one-dimensional) bin packing problem where E=∅ and of the graph coloring problem where s _i =0 for all i=1,2, ...,n. Since coloring problems on general graphs are hard to approximate, following previous work, we study the problem on specific graph classes. For the offline version we design improved approximation algorithms for perfect graphs and other special classes of graphs, these are a \(\frac 52=2.5\)-approximation algorithm for perfect graphs, a \(\frac 73\approx 2.33333\)-approximation for a sub-class of perfect graphs, which contains interval graphs, and a \(\frac 74=1.75\)-approximation for bipartite graphs. For the online problem on interval graphs, we design a 4.7-competitive algorithm and show a lower bound of \(\frac {155}{36}\approx 4.30556\) on the competitive ratio of any algorithm. To derive the last lower bound, we introduce the first lower bound on the asymptotic competitive ratio of any online bin packing algorithm with known optimal value, which is \(\frac {47}{36}\approx 1.30556\).

Leah Epstein, Asaf Levin

Approximate Distance Queries in Disk Graphs

Abstract

We present efficient algorithms for approximately answering distance queries in disk graphs. Let G be a disk graph with n vertices and m edges. For any fixed ε> 0, we show that G can be preprocessed in \(O(m\sqrt{n}\epsilon^{-1}+m\epsilon^{-2}\log S)\) time, constructing a data structure of size O(n ^3/2 ε ^− 1+nε ^− 2logS), such that any subsequent distance query can be answered approximately in \(O(\sqrt{n}\epsilon^{-1}+\epsilon^{-2}\log S)\) time. Here S is the ratio between the largest and smallest radius. The estimate produced is within an additive error which is only ε times the longest edge on some shortest path.

The algorithm uses an efficient subdivision of the plane to construct a sparse graph having many of the same distance properties as the input disk graph. Additionally, the sparse graph has a small separator decomposition, which is then used to answer distance queries. The algorithm extends naturally to the higher dimensional ball graphs.

Martin Fürer, Shiva Prasad Kasiviswanathan

Network Design with Edge-Connectivity and Degree Constraints

Abstract

We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v∈V is equal to b(v). This problem generalizes metric TSP. In this paper, we propose that the problem admits a ρ-approximation algorithm if b(v)≥2, v∈V, where ρ=2.5 if k is even, and ρ=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization of metric TSP.

Takuro Fukunaga, Hiroshi Nagamochi

Approximating Maximum Cut with Limited Unbalance

Abstract

We present polynomial time randomized approximation algorithms with non trivial performance guarantees for the problem of partitioning the vertices of a weighted graph into two sets of sizes that differ at most by a given threshold B, so as to maximize the weight of the crossing edges. For B equal to 0 this problem is known as Max Bisection, whereas for B equal to the number n of nodes it is the Maximum Cut problem. The approximation results are obtained by extending the methodology used by Y. Ye for Max Bisection and by combining this technique with another one that uses the algorithm of Goemans and Williamson for the Maximum Cut problem. When B is equal to zero the approximation ratio achieved coincides with the one obtained by Y. Ye; otherwise it is always above this value and tends to the value obtained by Goemans and Williamson as B approaches the number n of nodes.

Giulia Galbiati, Francesco Maffioli

Worst Case Analysis of Max-Regret, Greedy and Other Heuristics for Multidimensional Assignment and Traveling Salesman Problems

Abstract

Optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance ratio reflecting the quality of returned solution in the worst case. The domination number is a complement parameter indicating the quality of the heuristic in hand by determining how many feasible solutions are dominated by the heuristic solution. We prove that the Max-Regret heuristic introduced by Balas and Saltzman finds the unique worst possible solution for some instances of the s-dimensional (s≥3) assignment and asymmetric traveling salesman problems of each possible size. We show that the Triple Interchange heuristic (for s=3) also introduced by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching) have factorial domination numbers for the s-dimensional (s≥3) assignment problem.

Gregory Gutin, Boris Goldengorin, Jing Huang

Improved Online Hypercube Packing

Abstract

In this paper, we study online multidimensional bin packing problem when all items are hypercubes. Based on the techniques in one dimensional bin packing algorithm Super Harmonic by Seiden, we give a framework for online hypercube packing problem and obtain new upper bounds of asymptotic competitive ratios. For square packing, we get an upper bound of 2.1439, which is better than 2.24437. For cube packing, we also give a new upper bound 2.6852 which is better than 2.9421 by Epstein and van Stee.

Xin Han, Deshi Ye, Yong Zhou

Competitive Online Multicommodity Routing

Abstract

In this paper we study online multicommodity minimum cost routing problems in networks, where commodities have to be routed sequentially. The flow of each commodity can be split on several paths. Arcs are equipped with load dependent price functions defining routing costs. We discuss a greedy online algorithm that routes each commodity by minimizing a convex cost function that only depends on the demands previously routed. We present a competitive analysis of this algorithm showing that for affine linear price functions this algorithm is \(\tfrac{4K}{2+K}\)-competitive, where K is the number of commodities. For the parallel arc case, this algorithm is optimal. Without restrictions on the price functions and network, no algorithm is competitive. Finally, we investigate a variant in which the demands have to be routed unsplittably.

Tobias Harks, Stefan Heinz, Marc E. Pfetsch

The k-Allocation Problem and Its Variants

Abstract

In the process of reviewing and ranking projects by a group of reviewers, each reviewer is assumed to review a partial list of projects, up to k projects. Each individual reviewer then ranks and compares all pairs of k projects. The k-allocation problem is to determine the allocation of up to k projects to each reviewer within the expertise set of the reviewer so that the resulting union of reviewed projects has certain desirable properties. One property of the k-allocation is to have all pairs of projects compared by at least one reviewer. This we call the k-complete problem.

In cases when the property of k-complete cannot be achieved, one might settle for other properties. One such basic requirement is that each pair of projects is comparable via a ranking path which is a sequence of pairwise rankings of projects implying a comparison of all pairs on the path. A k-allocation with a ranking path between each pair is the connectivity-k-aloc. Since the robustness of relative comparisons deteriorates with the length of the ranking path, another property is that between each pair of projects there will be at least one ranking path that has at most two hops or q hops for fixed values of q. Another property that increases robustness of the ranking is to find a k-allocation so there are at least p disjoint ranking paths between each pair.

We model all these problems as graph problems and show that the connectivity-k-aloc problem is polynomially solvable using matroid intersection, the k-complete problem is NP-hard unless k = 2, and all other considered variants of the k-allocation properties problem are NP-complete for all values of k ≥2. We provide approximation algorithms for an optimization problem related to the k-complete problem.

Dorit S. Hochbaum, Asaf Levin

An Experimental Study of the Misdirection Algorithm for Combinatorial Auctions

Abstract

Single-minded combinatorial auctions (CA) are auctions in which a seller wants to sell diverse kinds of goods and each of the potential buyers, also called bidders, places a bid on a combination, i.e., a subset of the goods. There is a severe computational limitation in CA, as the problem of computing the optimal allocation is NP-hard and even hard to approximate. There is thus interest in polynomial time approximation algorithms for this problem. Recently, many such approximation algorithms were designed, among them greedy and local search based algorithms. One of these is a so-called misdirection algorithm combining both approaches and using a non-standard, misdirected, local search approach with neighborhood of size 2. This algorithm has the best known provable approximation ratio for the problem in terms of the sizes of bids. Its analysis, however, is quite complicated. We study this algorithm and its variants on typical instances designed for CAs. On question is if larger neighborhood helps – the question that seems quite difficult to address theoretically at the moment, taking into account already complex analysis for size 2 neighborhood. We also study experimentally other aspects of the misdirection algorithm, and finally present a comparison to other approximation algorithms.

Jörg Knoche, Piotr Krysta

Reversal Distance for Strings with Duplicates: Linear Time Approximation Using Hitting Set

Abstract

In the last decade there has been an ongoing interest in string comparison problems; to a large extend the interest was stimulated by genome rearrangement problems in computational biology but related problems appear in many other areas of computer science. Particular attention has been given to the problem of sorting by reversals (SBR): given two strings, A and B, find the minimum number of reversals that transform the string A into the string B (a reversalρ(i,j), i<j, transforms a string A=a ₁...a _n into a string A′=a ₁...a _i − 1 a _j a _j − 1 ...a _i a _j + 1 ...a _n ).

Primarily the problem has been studied for strings in which every symbol appears exactly once (that is, for permutations) and only recently attention has been given to the general case where duplicates of the symbols are allowed. In this paper we consider the problem k-SBR, a version of SBR in which each symbol is allowed to appear up to k times in each string, for some k≥1. The main result of the paper is a Θ(k)-approximation algorithm for k-SBR running in time O(n); compared to the previously known algorithm for k-SBR, this is an improvement by a factor of Θ(k) in the approximation ratio, and by a factor of Θ(k) in the running time. Crucial ingredients of our algorithm are the suffix tree data structure and a linear time algorithm for a special case of a disjoint set union problem.

Petr Kolman, Tomasz Waleń

Approximating the Unweighted k-Set Cover Problem: Greedy Meets Local Search

Abstract

In the unweighted set-cover problem we are given a set of elements E={ e ₁,e ₂, ...,e _n } and a collection \(\cal F\) of subsets of E. The problem is to compute a sub-collection SOL ⊆\(\cal F\) such that \(\bigcup_{S_j\in SOL}S_j=E\) and its size |SOL| is minimized. When |S|≤k for all \(S\in\cal F\) we obtain the unweighted k-set cover problem. It is well known that the greedy algorithm is an H _k -approximation algorithm for the unweighted k-set cover, where \(H_k=\sum_{i=1}^k {1 \over i}\) is the k-th harmonic number, and that this bound on the approximation ratio of the greedy algorithm, is tight for all constant values of k. Since the set cover problem is a fundamental problem, there is an ongoing research effort to improve this approximation ratio using modifications of the greedy algorithm. The previous best improvement of the greedy algorithm is an \(\left( H_k-{1\over 2}\right)\)-approximation algorithm. In this paper we present a new \(\left( H_k-{196\over 390}\right)\)-approximation algorithm for k ≥4 that improves the previous best approximation ratio for all values of k≥4 . Our algorithm is based on combining local search during various stages of the greedy algorithm.

Asaf Levin

Approximation Algorithms for Multi-criteria Traveling Salesman Problems

Abstract

In multi-criteria optimization, several objective functions are to be optimized. Since the different objective functions are usually in conflict with each other, one cannot consider only one particular solution as optimal. Instead, the aim is to compute so-called Pareto curves. Since Pareto curves cannot be computed efficiently in general, we have to be content with approximations to them.

We are concerned with approximating Pareto curves of multi-criteria traveling salesman problems (TSP). We provide algorithms for computing approximate Pareto curves for the symmetric TSP with triangle inequality (Δ− STSP), symmetric and asymmetric TSP with strengthened triangle inequality (Δ(γ)−STSP and Δ(γ)− ATSP), and symmetric and asymmetric TSP with weights one and two (STSP(1,2) and ATSP(1,2)).

We design a deterministic polynomial-time algorithm that computes (1+γ+ ε)-approximate Pareto curves for multi-criteria Δ(γ)−STSP for \(\gamma \in [\frac 12, 1]\). We also present two randomized approximation algorithms for multi-criteria Δ(γ)−STSP achieving approximation ratios of \(\frac{2\gamma^3 + \gamma^2 + 2 \gamma-1}{2\gamma^2} + \varepsilon\) and \(\frac{1+\gamma}{1+3 \gamma -- 4 \gamma^2}\) + ε, respectively. Moreover, we design randomized approximation algorithms for multi-criteria Δ(γ)−ATSP (ratio \(\frac 12+ \frac{\gamma^3}{1-3\gamma^2}\) + ε for \(\gamma < 1/\sqrt{3}\)), STSP(1,2) (ratio 4/3) and ATSP(1,2) (ratio 3/2).

The algorithms for Δ(γ)−ATSP, STSP(1,2), and ATSP(1,2) as well as one algorithm for Δ(γ)−STSP are based on cycle covers. Therefore, we design randomized approximation schemes for multi-criteria cycle cover problems by showing that multi-criteria graph factor problems admit fully polynomial-time randomized approximation schemes.

Bodo Manthey, L. Shankar Ram

The Survival of the Weakest in Networks

Abstract

We study here dynamic antagonism in a fixed network, represented as a graph G of n vertices. In particular, we consider the case of k ≤n particles walking randomly independently around the network. Each particle belongs to exactly one of two antagonistic species, none of which can give birth to children. When two particles meet, they are engaged in a (sometimes mortal) local fight. The outcome of the fight depends on the species to which the particles belong. Our problem is to predict (i.e. to compute) the eventual chances of species survival. We prove here that this can indeed be done in expected polynomial time on the size of the network, provided that the network is undirected.

S. Nikoletseas, C. Raptopoulos, P. Spirakis

Online Distributed Object Migration

Abstract

We study Distributed Object Migration using competitive analysis. The problem is motivated by distributed object-oriented computing, for which intelligent dynamic migration of (Java or other object-oriented) objects during runtime is important for efficient implementation on multiprocessor systems. In the online version of the problem, k mobile objects reside at n nodes of a network and they respond to a sequence of requests. Each request specifies two objects which have to communicate, and the algorithm has to decide whether to bring the objects together or not. We focus on the case of uniform networks with relatively large communication costs and show tight upper and lower bounds of k, for any network size n≥2. Our algorithm Timestamp uses a timestamp for each object, and we analyze it using an implicit potential function argument; the analysis is interesting in its own right, and may be applicable to a wider class of problems, but it doesn’t seem to be widely used. This implicit potential function argument gives a simple and intuitive proof of the (suboptimal) competitive ratio of 2k−1, within a factor of 2 of the optimal deterministic competitive ratio. To show the optimal competitive ratio of k, we use an explicit, yet less intuitive, potential function.

David Scot Taylor

Backmatter