Approximation and Online Algorithms

Frontmatter

“Almost Stable” Matchings in the Roommates Problem

Abstract

An instance of the classical Stable Roommates problem (sr) need not admit a stable matching. This motivates the problem of finding a matching that is “as stable as possible”, i.e. admits the fewest number of blocking pairs. In this paper we prove that, given an sr instance with n agents, in which all preference lists are complete, the problem of finding a matching with the fewest number of blocking pairs is NP-hard and not approximable within \(n^{\frac{1}{2}-\varepsilon}\), for any ε> 0, unless P=NP. If the preference lists contain ties, we improve this result to n ^1 − ε . Also, we show that, given an integer K and an sr instance I in which all preference lists are complete, the problem of deciding whether I admits a matching with exactly K blocking pairs is NP-complete. By contrast, if K is constant, we give a polynomial-time algorithm that finds a matching with at most (or exactly) K blocking pairs, or reports that no such matching exists. Finally, we give upper and lower bounds for the minimum number of blocking pairs over all matchings in terms of some properties of a stable partition, given an sr instance I.

David J. Abraham, Péter Biró, David F. Manlove

On the Minimum Load Coloring Problem

Abstract

Given a graph G=(V,E) with n vertices, m edges and maximum vertex degree Δ, the load distribution of a coloring . \(\varphi: V \longrightarrow\) red, blue is a pair d _ϕ  = (r _ϕ , b _ϕ ), where r _ϕ is the number of edges with at least one end-vertex colored red and b _ϕ is the number of edges with at least one end-vertex colored blue. Our aim is to find a coloring ϕ such that the (maximum) load, l _ϕ := max{r _ϕ , b _ϕ }, is minimized. The problem has applications in broadcast WDM communication networks (Ageev et al., 2004). After proving that the general problem is NP-hard we give a polynomial time algorithm for optimal colorings of trees and show that the optimal load is at most m/2+\({\it \Delta}\)log₂ n. For graphs with genus g>0, we show that a coloring with load OPT(1 + o(1)) can be computed in O(n+g)-time, if the maximum degree satisfies \({\it \Delta} = o(\frac{m^{2}}{ng})\) and an embedding is given. In the general situation we show that a coloring with load at most \({\frac{3} {4}}m+O({\sqrt{{\it \Delta}m}})\) can be found in deterministic polynomial time using a derandomized version of Azuma’s martingale inequality. This bound describes the “typical” situation: in the random multi-graph model we prove that for almost all graphs, the optimal load is at least \(\frac{3}{4}m - {\sqrt{3mn}}\) . Finally, we generalize our results to k–colorings for k > 2.

Nitin Ahuja, Andreas Baltz, Benjamin Doerr, Aleš Přívětivý, Anand Srivastav

Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT

Abstract

MAX SAT and MAX NAE-SAT are central problems in theoretical computer science. We present an approximation algorithm for MAX NAE-SAT with a conjectured performance guarantee of 0.8279. This improves a previously conjectured performance guarantee of 0.7977 of Zwick [Zwi99]. Using a variant of our MAX NAE-SAT approximation algorithm, combined with other techniques used in [Asa03], we obtain an approximation algorithm for MAX SAT with a conjectured performance guarantee of 0.8434. This improves on an approximation algorithm of Asano [Asa03] with a conjectured performance guarantee of 0.8353. We also obtain a 0.7968-approximation algorithm for MAX SAT which is not based on any conjecture, improving a 0.7877-approximation algorithm of Asano [Asa03].

Adi Avidor, Ido Berkovitch, Uri Zwick

The Hardness of Network Design for Unsplittable Flow with Selfish Users

Abstract

In this paper we consider the network design for selfish users problem, where we assume the more realistic unsplittable model in which the users can have general demands and each user must choose a single path between its source and its destination. This model is also called atomic (weighted) network congestion game. The problem can be presented as follows : given a network, which edges should be removed to minimize the cost of the worst Nash equilibrium?

We consider both computational issues and existential issues (i.e. the power of network design). We give inapproximability results and approximation algorithms for this network design problem. For networks with linear edge latency functions we prove that there is no approximation algorithm for this problem with approximation ratio less then \((3+\sqrt{5})/2 \approx 2.618\) unless P=NP. We also show that for networks with polynomials of degree d edge latency functions there is no approximation algorithm for this problem with approximation ratio less then \(d^{{\it \Theta}(d)}\) unless P=NP. Moreover, we observe that the trivial algorithm that builds the entire network is optimal for linear edge latency functions and has an approximation ratio of \(d^{{\it \Theta}(d)}\) for polynomials of degree d edge latency functions. Finally, we consider general continuous, non-decreasing edge latency functions and show that the approximation ratio of any approximation algorithm for this problem is unbounded, assuming P ≠ NP. In terms of existential issues we show that network design cannot improve the maximum possible bound on the price of anarchy in the worst case.

Previous results of Roughgarden for networks with n vertices where each user controls only a negligible fraction of the overall traffic showed optimal inapproximability results of 4/3 for linear edge latency functions, \({\it \Theta}(d /{\rm ln} d)\) for polynomial edge latency functions and n/2 for general continuous non-decreasing edge latency functions. He also showed that the trivial algorithm that builds the entire network is optimal for that case.

Yossi Azar, Amir Epstein

Improved Approximation Algorithm for Convex Recoloring of Trees

Abstract

A pair (T,C) of a tree T and a coloring C is called a colored tree. Given a colored tree (T,C) any coloring C′ of T is called a recoloring of T. Given a weight function on the vertices of the tree the recoloring distance of a recoloring is the total weight of recolored vertices. A coloring of a tree is convex if for any two vertices u and v that are colored by the same color c, every vertex on the path from u to v is also colored by c. In the minimum convex recoloring problem we are given a colored tree and a weight function and our goal is to find a convex recoloring of minimum recoloring distance.

The minimum convex recoloring problem naturally arises in the context of phylogenetic trees. Given a set of related species the goal of phylogenetic reconstruction is to construct a tree that would best describe the evolution of this set of species. In this context a convex coloring correspond to perfect phylogeny. Since perfect phylogeny is not always possible the next best thing is to find a tree which is as close to convex as possible, or, in other words, a tree with minimum recoloring distance.

We present a (2+ε)-approximation algorithm for the minimum convex recoloring problem, whose running time is O(n ² + n(1/ε)² 4^1/ε ). This result improves the previously known 3-approximation algorithm for this NP-hard problem.

Reuven Bar-Yehuda, Ido Feldman, Dror Rawitz

Exploiting Locality: Approximating Sorting Buffers

Abstract

The Sorting Buffers problem is motivated by many applications in manufacturing processes and computer science, among them car-painting and file servers architecture. The input is a sequence of items of various types. All the items must be processed, one by one, by a service station. We are given a random-access sorting buffer with a limited capacity. Whenever a new item arrives it may be moved directly to the service station or stored in the buffer. Also, at any time items can be removed from the buffer and assigned to the service station. Our goal is to give the service station a sequence of items with minimum type transitions. We generalize the problem to allow items with different sizes and type transitions with different costs. We give a polynomial-time 9-approximation algorithm for the maximization variant of this problem, which improves the best previously known 20-approximation algorithm.

Reuven Bar-Yehuda, Jonathan Laserson

Approximate Fair Cost Allocation in Metric Traveling Salesman Games

Abstract

A traveling salesman game is a cooperative game \(\mathcal{G} = (N, c_{D})\). Here N, the set of players is the set of cities (or the vertices of the complete graph) and c _D is the characteristic function where D is the underlying cost matrix. For all S ⊆ N, define c _D (S) to be the cost of a minimum cost Hamiltonian tour through the vertices of S∪ {0} where 0 ∉ N is called as the home city. Define Core \((\mathcal{G})= \{x \in \Re^{N} :x(N) = c_{D}(N)\ {\rm and}\ \forall S\subseteq N, x(S) \leq c_{D} (S)n\} \) as the core of a traveling salesman game (\(\mathcal{G}\)). Okamoto [15] conjectured that for the traveling salesman game \(\mathcal{G} = (N, c_{D})\) with D satisfying triangle inequality, the problem of testing whether Core (\(\mathcal{G}\)) is empty or not is NP–hard. We prove that this conjecture is true. This result directly implies the NP–hardness for the general case when D is asymmetric. We also study approximate fair cost allocations for these games. For this, we introduce the cycle cover games and show that the core of a cycle cover game is non–empty by finding a fair cost allocation vector in polynomial time. For a traveling salesman game, let \(\epsilon-{\rm Core} (\mathcal{G})=\{x \in \Re^{N} :x(N) = c_{D}(N) {\rm and}\ \forall S\subseteq N, x(S) \leq {\epsilon}\cdot c_{D}(S)\}\) be an ε–approximate core, for a given ε > 1. By viewing an approximate fair cost allocation vector for this game as a sum of exact fair cost allocation vectors of several related cycle cover games, we provide a polynomial time algorithm demonstrating the non–emptiness of the log₂(|N|–1)– approximate core by exhibiting a vector in this approximate core for the asymmetric traveling salesman game. We also show that there exists an ε ₀ > 1 such that it is NP–hard to decide whether ε ₀–Core(\(\mathcal{G})\) is empty or not.

M. Bläser, L. Shankar Ram

Rounding of Sequences and Matrices, with Applications

Abstract

We show that any real matrix can be rounded to an integer matrix in such a way that the rounding errors of all row sums are less than one, and the rounding errors of all column sums as well as all sums of consecutive row entries are less than two.Such roundings can be computed in linear time. This extends and improves previous results on rounding sequences and matrices in several directions. It has particular applications in just-in-time scheduling, where balanced schedules on machines with negligible switch over costs are sought after. Here we extend existing results to multiple machines and non-constant production rates.

Benjamin Doerr, Tobias Friedrich, Christian Klein, Ralf Osbild

A Note on Semi-online Machine Covering

Abstract

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.

Tomáš Ebenlendr, John Noga, Jiří Sgall, Gerhard Woeginger

SONET ADMs Minimization with Divisible Paths

Abstract

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 \(\frac{5}{4} = 1.25\) whereas the previously best known approximation algorithm for the chord version has a performance guarantee of \(\frac{3}{2} = 1.5\). We improve both these results. We present a \(\frac{36}{29} \approx 1.24138\)-approximation algorithm for the arc version and a \(\frac{7}{5} = 1.4\)-approximation algorithm for the chord version.

Leah Epstein, Asaf Levin

The Conference Call Search Problem in Wireless Networks

Abstract

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.

Leah Epstein, Asaf Levin

Improvements for Truthful Mechanisms with Verifiable One-Parameter Selfish Agents

Abstract

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 Q||C _max problem by using only our results. Even if our payment schemes need upper-bounded type sets, every instance of Q||C _max can be ”mapped” into an instance with upper-bounded type sets preserving the approximation ratio.

A. Ferrante, G. Parlato, F. Sorrentino, C. Ventre

Symmetry in Network Congestion Games: Pure Equilibria and Anarchy Cost

Abstract

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 \({\it \Theta}({\frac{{\rm log} m}{{\rm log log} m}}\)).

Dimitris Fotakis, Spyros Kontogiannis, Paul Spirakis

A Better-Than-Greedy Algorithm for k-Set Multicover

Abstract

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=1}^{k}\) (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.

Toshihiro Fujito, Hidekazu Kurahashi

Deterministic Online Optical Call Admission Revisited

Abstract

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 σ=r ₁,r ₂,... of calls which arrive in an online fashion. Each call r _j 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 χ> 1 wavelengths which achieves a competitive ratio of  \(\chi(\sqrt[\chi]{n} + 2)\) on the line with n+1 nodes. As long as  χ> 1 is fixed, this is the first competitive ratio which is sublinear in n+1, the number of nodes.

Elisabeth Gassner, Sven O. Krumke

Scheduling Parallel Jobs with Linear Speedup

Abstract

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.

Alexander Grigoriev, Marc Uetz

Online Removable Square Packing

Abstract

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 (\(\sqrt{5}+3)/2 \approx 2.618\). (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.

Xin Han, Kazuo Iwama, Guochuan Zhang

The Online Target Date Assignment Problem

Abstract

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 (OnlineTDAP) as a general framework for online problems with this nature. Requests for the OnlineTDAP 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 OnlineTDAP 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.

S. Heinz, S. O. Krumke, N. Megow, J. Rambau, A. Tuchscherer, T. Vredeveld

Approximation and Complexity of k–Splittable Flows

Abstract

Given a graph with a source and a sink node, the NP–hard maximum k–splittable flow (M k SF) 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 M k SF 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 ε> 0, 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 M k SF 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 M k SF for different values of k.

Ronald Koch, Martin Skutella, Ines Spenke

On Minimizing the Maximum Flow Time in the Online Dial-a-Ride Problem

Abstract

In the online dial-a-ride problem (OlDarp), 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 OlDarp 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.

Sven O. Krumke, Willem E. de Paepe, Diana Poensgen, Maarten Lipmann, Alberto Marchetti-Spaccamela, Leen Stougie

Tighter Approximations for Maximum Induced Matchings in Regular Graphs

Abstract

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 \(d - {\frac{1}{2}}\) 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.

Zvi Gotthilf, Moshe Lewenstein

On Approximating Restricted Cycle Covers

Abstract

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 k ∈ ℕ, 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 APX-hard and NP-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 APX-complete for every λ≥3.

Bodo Manthey

A PTAS for the Minimum Dominating Set Problem in Unit Disk Graphs

Abstract

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 n ^{O(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.

Tim Nieberg, Johann Hurink

Speed Scaling of Tasks with Precedence Constraints

Abstract

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 | C _max . 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 | C _max to obtain a poly-log(m)-approximation algorithm.

Kirk Pruhs, Rob van Stee, Patchrawat Uthaisombut

Partial Multicuts in Trees

Abstract

Let T = (V,E) be an undirected tree, in which each edge is associated with a non-negative cost, and let { s ₁, t ₁ }, ..., { s _k , t _k } 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 (\({\frac{8}{3}}+{\epsilon}\))-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.

Asaf Levin, Danny Segev

Approximation Schemes for Packing with Item Fragmentation

Abstract

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].

Hadas Shachnai, Tami Tamir, Omer Yehezkely

Backmatter