Search

In the layered-graph query model of network discovery, a query at a node v of an undirected graph G discovers all edges and non-edges whose endpoints have different distance from v. We study the number of queries at randomly selected nodes that are needed for approximate network discovery in Erdős-Rényi random graphs Gn,p. We show that a constant number of queries is sufficient if p is a constant, while Ω(nα) queries are needed if p = nε/n, for arbitrarily small choices of ε = 3 / (6 ·i + 5) with i ∈ ℕ. Note that α> 0 is a constant depending only on ε. Our proof of the latter result yields also a somewhat surprising result on pairwise distances in random graphs which may be of independent interest: We show that for a random graph Gn,p with p = nε/n, for arbitrarily small choices of ε> 0 as above, in any constant cardinality subset of the nodes the pairwise distances are all identical with high probability. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. Keywords: Online Algorithms, Competitive Analysis, Distributed Algorithms, Data Management, Object Oriented Programming. [ABSTRACT FROM AUTHOR]

In the unweighted set-cover problem we are given a set of elements E={ e1,e2...,en } and a collection $\cal F$ of subsets of E. The problem is to compute a sub-collection $SOL\subseteq$$\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 Hk-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. [ABSTRACT FROM AUTHOR]

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. Keywords: Approximation algorithms, allocation problem, maximum coverage problem. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. Keywords: randomized algorithm, approximation algorithm, semidefinite programming. [ABSTRACT FROM AUTHOR]

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(n3/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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 s1,s2 ...,sn ∈[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 si=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$. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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(n3). 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. Keywords: minimum corridor connection, generalized geometric problems, complexity, exact algorithms, approximations. [ABSTRACT FROM AUTHOR]

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 + ε−4mlog2m (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 (log3n + ε−4 log2n )) expected time. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Consider the Dynamic Program h(n) = min 1 ≤j ≤na(n,j) for n = 1, 2..., N. For arbitrary values of a(n,j), calculating all the h(n) requires Θ(N2) 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In the online capacitated interval coloring problem, a sequence of requests arrive online. Each of the requests is an interval Ij ⊆ {1,2,...,n} with bandwidth bj. Initially a vector of capacities (c1,c2,...,cn) is given. Each color can support a set of requests such that the total bandwidth of intervals containing i is at most ci. The goal is to color the requests using a minimum number of colors. We present a constant competitive algorithm for the case where the maximum bandwidth bmax =  max jbj is at most the minimum capacity cmin =  min ici. For the case bmax > cmin, we give an algorithm with competitive ratio $O({\rm log}{{b_{\rm max}}\over{c_{\rm min}}})$ and, using resource augmentation, a constant competitive algorithm. We also give a lower bound showing that constant competitive ratio cannot be achieved in this case without resource augmentation. [ABSTRACT FROM AUTHOR]

This chapter surveys on-line and approximation algorithms for the maximum independent set and coloring problems on intersection graphs of disks. It includes a more detailed treatment of recent upper and lower bounds on the competitive ratio of on-line algorithms for coloring such graphs. [ABSTRACT FROM AUTHOR]

In the maximum edge-disjoint paths problem (MEDP) the input consists of a graph and a set of requests (pairs of vertices), and the goal is to connect as many requests as possible along edge-disjoint paths. We give a survey of known results about the complexity and approximability of MEDP and sketch some of the main ideas that have been used to obtain approximation algorithms for the problem. We consider also the generalization of MEDP where the edges of the graph have capacities and each request has a profit and a demand, called the unsplittable flow problem. [ABSTRACT FROM AUTHOR]

We consider online coloring of intervals with bandwidth in a setting where colors have variable capacities. Whenever the algorithm opens a new color, it must choose the capacity for that color and cannot change it later. The goal is to minimize the total capacity of all the colors used. We consider the bounded model, where all capacities must be chosen in the range (0,1], and the unbounded model, where the algorithm may use colors of any positive capacity. For the absolute competitive ratio, we give an upper bound of 14 and a lower bound of 4.59 for the bounded model, and an upper bound of 4 and a matching lower bound of 4 for the unbounded model. We also consider the offline version of these problems and show that the unbounded model is polynomially solvable, while the bounded model is NP-hard in the strong sense and admits a 3.6-approximation algorithm. [ABSTRACT FROM AUTHOR]

For a given graph with weighted vertices, the goal of the minimum-weight dominating set problem is to compute a vertex subset of smallest weight such that each vertex of the graph is contained in the subset or has a neighbor in the subset. A unit disk graph is a graph in which each vertex corresponds to a unit disk in the plane and two vertices are adjacent if and only if their disks have a non-empty intersection. We present the first constant-factor approximation algorithm for the minimum-weight dominating set problem in unit disk graphs, a problem motivated by applications in wireless ad-hoc networks. The algorithm is obtained in two steps: First, the problem is reduced to the problem of covering a set of points located in a small square using a minimum-weight set of unit disks. Then, a constant-factor approximation algorithm for the latter problem is obtained using enumeration and dynamic programming techniques exploiting the geometry of unit disks. Furthermore, we also show how to obtain a constant-factor approximation algorithm for the minimum-weight connected dominating set problem in unit disk graphs. [ABSTRACT FROM AUTHOR]

We consider two variants of the classical bin packing problem in which items may be fragmented. This can potentially reduce the total number of bins needed for packing the instance. However, since fragmentation incurs overhead, we attempt to avoid it as much as possible. In bin packing with size increasing fragmentation (BP-SIF), fragmenting an item increases the input size (due to a header/footer of fixed size that is added to each fragment). In bin packing with size preserving fragmentation (BP-SPF), there is a bound on the total number of fragmented items. These two variants of bin packing capture many practical scenarios, including message transmission in community TV networks, VLSI circuit design and preemptive scheduling on parallel machines with setup times/setup costs. While both BP-SPF and BP-SIF do not belong to the class of problems that admit a polynomial time approximation scheme (PTAS), we show in this paper that both problems admit a dual PTAS and an asymptotic PTAS. We also develop for each of the problems a dual asymptotic fully polynomial time approximation scheme (AFPTAS). The AFPTASs are based on a non-trivial application of a fast combinatorial FPTAS for packing linear programs with negative entries, proposed recently by Garg and Khandekar [5]. [ABSTRACT FROM AUTHOR]

Let T = (V,E) be an undirected tree, in which each edge is associated with a non-negative cost, and let { s1, t1 }..., { sk, tk } be a collection of k distinct pairs of vertices. Given a requirement parameter t ≤ k, the partial multicut on a tree problem asks to find a minimum cost set of edges whose removal from T disconnects at least t out of these k pairs. This problem generalizes the well-known multicut on a tree problem, in which we are required to disconnect all given pairs. The main contribution of this paper is an -approximation algorithm for partial multicut on a tree, whose run time is strongly polynomial for any fixed ε > 0. This result is achieved by introducing problem-specific insight to the general framework of using the Lagrangian relaxation technique in approximation algorithms. Our algorithm utilizes a heuristic for the closely related prize-collecting variant, in which we are not required to disconnect all pairs, but rather incur penalties for failing to do so. We provide a Lagrangian multiplier preserving algorithm for the latter problem, with an approximation factor of 2. Finally, we present a new 2-approximation algorithm for multicut on a tree, based on LP-rounding. [ABSTRACT FROM AUTHOR]

We present a polynomial-time approximation scheme (PTAS) for the minimum dominating set problem in unit disk graphs. In contrast to previously known approximation schemes for the minimum dominating set problem on unit disk graphs, our approach does not assume a geometric representation of the vertices (specifying the positions of the disks in the plane) to be given as part of the input. The runtime of the PTAS is nO(1/ε log 1/ε ). The algorithm accepts any undirected graph as input, and returns a (1+ε )-approximate minimum dominating set, or a certificate showing that the input graph is no unit disk graph, making the algorithm robust. The PTAS can easily be adapted to other classes of geometric intersection graphs. [ABSTRACT FROM AUTHOR]

An induced matching is a matching in which each two edges of the matching are not connected by a joint edge. Induced matchings are well-studied combinatorial objects and a lot of consideration has been given to finding maximum induced matchings, which is an NP-complete problem. Specifically, finding maximum induced matchings in regular graphs is well-known to be NP-complete. A couple of papers lately showed a couple of simple greedy algorithm that approximate a maximum induced matching with a factor of and d-1 (different papers - different factors), where d is the degree of regularity. We show here a simple algorithm with an 0.75d + 0.15 approximation factor. The algorithm is simple - the analysis is not. [ABSTRACT FROM AUTHOR]

We consider the problem of speed scaling to conserve energy in a multiprocessor setting where there are precedence constraints between tasks, and where the performance measure is the makespan. That is, we consider an energy bounded version of the classic problem Pm prec Cmax. We show that, without loss of generality, one need only consider constant power schedules. We then show how to reduce this problem to the problem Qm prec Cmax to obtain a poly-log(m)-approximation algorithm. [ABSTRACT FROM AUTHOR]

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. A special case of L-cycle covers are k-cycle covers for , where the length of each cycle must be at least k. The weight of a cycle cover of an edge-weighted graph is the sum of the weights of its edges. We come close to settling the complexity and approximability of computing L-cycle covers. On the one hand, we show that for almost all L, computing L-cycle covers of maximum weight in directed and undirected graphs is -hard and -hard. Most of our hardness results hold even if the edge weights are restricted to zero and one. On the other hand, we show that the problem of computing L-cycle covers of maximum weight can be approximated with factor 2.5 for undirected graphs and with factor 3 in the case of directed graphs. Finally, we show that 4-cycle covers of maximum weight in graphs with edge weights zero and one can be computed in polynomial time. As a by-product, we show that the problem of computing minimum vertex covers in λ-regular graphs is -complete for every λ≥3. [ABSTRACT FROM AUTHOR]

In the online dial-a-ride problem (), objects must be transported by a server between points in a metric space. Transportation requests ("rides") arrive online, specifying the objects to be transported and the corresponding source and destination. We investigate the for the objective of minimizing the maximum flow time. It has been well known that there can be no strictly competitive online algorithm for this objective and no competitive algorithm at all on unbounded metric spaces. However, the question whether on metric spaces with bounded diameter there are competitive algorithms if one allows an additive constant in the definition competitive ratio, had been open for quite a while. We provide a negative answer to this question already on the uniform metric space with three points. Our negative result is complemented by a strictly 2-competitive algorithm for the Online Traveling Salesman Problem on the uniform metric space, a special case of the problem. [ABSTRACT FROM AUTHOR]

Given a graph with a source and a sink node, the NP-hard maximum k-splittable flow (MkSF) problem is to find a flow of maximum value with a flow decomposition using at most k paths [6]. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values on these paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Our main contributions are as follows: - We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal MkSF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed , the computed set of alternatives contains a packing used by a (1-ε)-approximate solution. The latter result is based on the observation that (1-ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. - Based on (i), we prove that, for constant k, the MkSF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it. - Finally, we provide a comprehensive overview of the complexity and approximability landscape of MkSF for different values of k. [ABSTRACT FROM AUTHOR]

The online removable square packing problem is a two dimensional version of the online removable Knapsack problem. For a sequence of squares with side length at most 1, we are requested to pack a subset of them into a unit square in an online fashion where the online player can decide whether to take the current square or not and which squares currently in the unit square to remove. The goal is to maximize the total packed area. Our results include: (i) Any online algorithm cannot achieve a better competitive ratio than . (ii) The matching upper bound is achieved by a relatively simple online algorithm if repacking is allowed. (iii) Without repacking, we can achieve an upper bound of 3 by using the concept of bricks by Januszewski and Lassak [11]. (iv) The offline version of the problem admits a PTAS. [ABSTRACT FROM AUTHOR]

Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain "subinstances" (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an Online Target Date Assignment Problem () as a general framework for online problems with this nature. Requests for the become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e. g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the downstream cost, the optimal cost of processing all requests at that date w. r. t. some fixed downstream offline optimization problem (e. g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the particular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman. [ABSTRACT FROM AUTHOR]

In the problem of Online Call Admission in Optical Networks, briefly called oca, we are given a graph G=(V,E) together with a set of wavelengths W (χ:=W) and a finite sequence σ=r1,r2,... of calls which arrive in an online fashion. Each call rj specifies a pair of nodes to be connected. A lightpath is a path in G together with a wavelength λ ∈ W. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide a lightpath to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. The objective in oca is to maximize the overall profit, that is, the number of accepted calls. A result by Awerbuch et al. states that a c-competitive algorithm for oca with one wavelength, i.e., χ:=W=1, implies a (c+1)-competitive algorithm for general numbers of wavelengths. However, for instance, for the line with n+1 nodes, a lower bound of n for the competitive ratio of deterministic algorithms for χ=1 makes this result void in many cases. We provide a deterministic competitive algorithm for wavelengths which achieves a competitive ratio of on the line with n+1 nodes. As long as is fixed, this is the first competitive ratio which is sublinear in n+1, the number of nodes. [ABSTRACT FROM AUTHOR]

We consider a scheduling problem where a set of jobs is a-priori distributed over parallel machines. The processing time of any job is dependent on the usage of a scarce renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The dependence of processing times on the amount of resources is linear for any job. The objective is to find a resource allocation and a schedule that minimizes the makespan. Utilizing an integer quadratic programming relaxation, we show how to obtain a (3 + ε) -approximation algorithm for that problem, for any ε > 0. This generalizes and improves previous results, respectively. Our approach relies on a fully polynomial time approximation scheme to solve the quadratic programming relaxation. This result is interesting in itself, because the underlying quadratic program is NP-hard to solve. We also derive lower bounds, and discuss further generalizations of the results. [ABSTRACT FROM AUTHOR]

In this paper we study optimization problems with verifiable one-parameter selfish agents introduced by Auletta et al. [ICALP 2004]. Our goal is to allocate load among the agents, provided that the secret data of each agent is a single positive rational number: the cost they incur per unit load. In such a setting the payment is given after the load completion, therefore if a positive load is assigned to an agent, we are able to verify if the agent declared to be faster than she actually is. We design truthful mechanisms when the agents' type sets are upper-bounded by a finite value. We provide a truthful mechanism that is c·(1+ε)-approximate if the underlying algorithm is c-approximate and weakly-monotone. Moreover, if type sets are also discrete, we provide a truthful mechanism preserving the approximation ratio of the used algorithm. Our results improve the existing ones which provide truthful mechanisms dealing only with finite type sets and do not preserve the approximation ratio of the underlying algorithm. Finally we give a full characterization of the problem by using only our results. Even if our payment schemes need upper-bounded type sets, every instance of can be "mapped" into an instance with upper-bounded type sets preserving the approximation ratio. [ABSTRACT FROM AUTHOR]

The set multicover (MC) problem is a natural extension of the set cover problem s.t. each element requires to be covered a prescribed number of times (instead of just once as in set cover). The k-set multicover (k-MC) problem is a variant in which every subset is of size at most k. Due to the multiple coverage requirement, two versions of MC have been studied; the one in which each subset can be chosen only once (constrained MC) and the other in which each subset can be chosen any number of times (unconstrained MC). For both versions the best approximation algorithm known so far is the classical greedy heuristic, whose performance ratio is H(k), where H(k)= ∑i=1k (1/i). It is no hard, however, to come up with a natural modification of the greedy algorithm such that the resulting performance is never worse, but could also be strictly better. This paper will verify that this is indeed the case by showing that such a modification leads to an improved performance ratio of H(k)-1/6 for both versions of k-MC. [ABSTRACT FROM AUTHOR]

We study computational and coordination efficiency issues of Nash equilibria in symmetric network congestion games. We first propose a simple and natural greedy method that computes a pure Nash equilibrium with respect to traffic congestion in a network. In this algorithm each user plays only once and allocates her traffic to a path selected via a shortest path computation. We then show that this algorithm works for series-parallel networks when users are identical or when users are of varying demands but have the same best response strategy for any initial network traffic. We also give constructions where the algorithm fails if either the above condition is violated (even for series-parallel networks) or the network is not series-parallel (even for identical users). Thus, we essentially indicate the limits of the applicability of this greedy approach. We also study the price of anarchy for the objective of maximum latency. We prove that for any network of m uniformly related links and for identical users, the price of anarchy is . [ABSTRACT FROM AUTHOR]

Cellular telephony systems, where locations of mobile users are unknown at some times, are becoming more common. Mobile users are roaming in a zone. A user reports its location only if it leaves the zone entirely. The Conference Call Search problem (CCS) deals with tracking a set of mobile users in order to establish a call. To find a single roaming user, the system may need to search each cell where the user may be located. The goal is to identify the location of all users, within bounded time, satisfying some additional constraints on the search scheme. We consider cellular systems with n cells and m mobile users (cellular phones). The uncertain location of users is given by m probability distribution vectors. Whenever the system needs to find the users, it conducts a search operation lasting at most d rounds. A request for a single search step specifies a user and a cell. In this search step, the cell is asked whether the given user is located there. In each round the system may perform an arbitrary number of such requests. An integer number B≥ 1 bounds the number of distinct requests per cell in every round. The bounds d and B result from quality of service considerations. Every search step consumes expensive wireless links, which motivates search techniques minimizing the expected number of requests thus reducing the total search costs. We distinguish between oblivious, semi-adaptive and adaptive search protocols. An oblivious search protocol decides on all requests in advance, and stops only when all users are found. A semi-adaptive search protocol decides on all the requests in advance, but it stops searching for a user once it is found. An adaptive search protocol stops searching for a user once it has been found (and its search strategy may depend on the subsets of users that were found in each previous round). We establish the difference between those three search models. We show that for oblivious "single query per cell" systems (B=1), and a tight environment (d=m), it is NP-hard to compute an optimal solution (the case d=m=2 was proven to be NP-hard already by Bar-Noy and Naor) and we develop a PTAS for these cases (for fixed values of d=m). However, we show that semi-adaptive systems allow polynomial time algorithms. This last result also shows that the case B=1 and d=m=2 is polynomially solvable also for adaptive search systems, answering an open question of Bar-Noy and Naor. [ABSTRACT FROM AUTHOR]

In the machine cover problem we are given m machines and n jobs to be assigned (scheduled) so that the smallest load of a machine is as large as possible. A semi-online algorithm is given in advance the optimal value of the smallest load for the given instance, and then the jobs are scheduled one by one as they arrive, without any knowledge of the following jobs. We present a deterministic algorithm with competitive ratio 11/6≤ 1.834 for machine covering with any number of machines and a lower bound showing that no deterministic algorithm can have a competitive ratio below 43/24≥ 1.791. [ABSTRACT FROM AUTHOR]

We consider an optical routing problem. SONET add-drop multiplexers (ADMs) are the dominant cost factor in SONET /WDM rings. The number of SONET ADMs required by a set of traffic streams is determined by the routing and wavelength assignment of the traffic streams. In this paper we consider the version where a traffic stream may be divided into several parts and assigned different wavelengths. A specific division may increase or decrease the number of ADMs needed for a given input. Following previous work, we consider two versions. In the arc version, the route of each traffic stream is given as input, and we need to decide on divisions of streams, and then to assign wavelengths so as to minimize the total number of used SONET ADMs. In the chord version, the route is not prespecified, but is assigned by the algorithm, and only after this step the divisions are done and wavelengths are assigned. The previously best known approximation algorithm for the arc version has a performance guarantee of whereas the previously best known approximation algorithm for the chord version has a performance guarantee of . We improve both these results. We present a -approximation algorithm for the arc version and a -approximation algorithm for the chord version. [ABSTRACT FROM AUTHOR]