On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems

Abstract

This paper addresses the competitiveness of online algorithms for two Steiner Tree problems. In the first problem, the underlying graph is directed and has bounded asymmetry, namely the maximum weight of antiparallel links in the graph does not exceed a parameter α. Previous work on this problem has left a gap on the competitive ratio which is as large as logarithmic in k. We present a refined analysis, both in terms of the upper and the lower bounds, that closes the gap and shows that a greedy algorithm is optimal for all values of the parameter α.

The second part of the paper addresses the Euclidean Steiner tree problem on the plane. Alon and Azar [SoCG 1992, Disc. Comp. Geom. 1993] gave an elegant lower bound on the competitive ratio of any deterministic algorithm equal to Ω(logk/ loglogk); however, the best known upper bound is the trivial bound O(logk). We give the first analysis that makes progress towards closing this long-standing gap. In particular, we present an online algorithm with competitive ratio O(logk/ loglogk), provided that the optimal offline Steiner tree belongs in a class of trees with relatively simple structure. This class comprises not only the adversarial instances of Alon and Azar, but also all rectilinear Steiner trees which can be decomposed in a polylogarithmic number of rectilinear full Steiner trees.

Spyros Angelopoulos

Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications

Abstract

The Nemhauser&Trotter Theorem provides an algorithm which is frequently used as a subroutine in approximation algorithms for the classical Vertex Cover problem. In this paper we present an extension of this theorem so it fits a more general variant of Vertex Cover, namely the Generalized Vertex Cover problem, where edges are allowed not to be covered at a certain predetermined penalty. We show that many applications of the original Nemhauser&Trotter Theorem can be applied using our extension to Generalized Vertex Cover. These applications include a \((2-\frac{2}{d})\)-approximation algorithm for graphs of bounded degree d, a PTAS for planar graphs, a \((2-\frac{\lg \lg n}{2 \lg n})\)-approximation algorithm for general graphs, and a 2k kernel for the parameterized Generalized Vertex Cover problem.

Reuven Bar-Yehuda, Danny Hermelin, Dror Rawitz

Price Fluctuations: To Buy or to Rent

Abstract

We extend the classic online ski rental problem, so that the rental price may change over time. We consider several models which differ in the knowledge given to the algorithm: whereas the price development is unknown, an algorithm may have full, partial or no knowledge about the duration of the game. We construct algorithms whose competitive ratios are up to constant or logarithmic factors optimal.

Marcin Bienkowski

Approximation Algorithms for Multiple Strip Packing

Abstract

In this paper we study the Multiple Strip Packing (MSP) problem, a generalization of the well-known Strip Packing problem. For a given set of rectangles, r ₁,...,r _n, with heights and widths ≤ 1, the goal is to find a non-overlapping orthogonal packing without rotations into k ∈ ℕ strips [0,1]×[0, ∞ ), minimizing the maximum of the heights. We present an approximation algorithm with absolute ratio 2, which is the best possible, unless \({\cal P}={\cal NP}\), and an improvement of the previous best result with ratio 2 + ε. Furthermore we present simple shelf-based algorithms with short running-time and an AFPTAS for MSP. Since MSP is strongly \({\cal NP}\)-hard, an FPTAS is ruled out and an AFPTAS is also the best possible result in the sense of approximation theory.

Marin Bougeret, Pierre Francois Dutot, Klaus Jansen, Christina Otte, Denis Trystram

Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window

Abstract

In an asynchronous data stream, the data items may be out of order with respect to their original timestamps. This paper gives a space-efficient data structure to maintain such a data stream so that it can approximate the frequent item set over a sliding time window with sufficient accuracy. Prior to our work, Cormode et al. [3] have the best solution, with space complexity \(O(\frac{1}{\varepsilon} \log W \log (\frac{\varepsilon B}{\log W}) \min\{\log W, \frac{1}{\varepsilon}\}\log U)\), where ε is the given error bound, W and B are parameters of the sliding window, and U is the number of all possible item names. Our solution reduces the space to \(O(\frac{1}{\varepsilon} \log W \log (\frac{\varepsilon B}{\log W}))\). We also unify the study of synchronous and asynchronous data stream by quantifying the delay of the data items. When the delay is zero, our solution matches the space complexity of the best solution to the synchronous data streams [8].

Ho-Leung Chan, Tak-Wah Lam, Lap-Kei Lee, Hing-Fung Ting

Longest Wait First for Broadcast Scheduling [Extended Abstract]

Abstract

We consider online algorithms for broadcast scheduling. In the pull-based broadcast model there are n unit-sized pages of information at a server and requests arrive online for pages. When the server transmits a page p, all outstanding requests for that page are satisfied. There is a lower bound of Ω(n) on the competitiveness of online algorithms to minimize average flow-time; therefore we consider resource augmentation analysis in which the online algorithm is given extra speed over the adversary. The longest-wait-first (LWF) algorithm is a natural algorithm that has been shown to have good empirical performance [2]. Edmonds and Pruhs showed that LWF is 6-speed O(1)-competitive using a novel yet complex analysis; they also showed that LWF is not O(1)-competitive with less than 1.618-speed. In this paper we make two main contributions to the analysis of LWF and broadcast scheduling.

We give an intuitive and easy to understand analysis of LWF which shows that it is O(1/ε ²)-competitive for average flow-time with (4 + ε) speed.
We show that a natural extension of LWF is O(1)-speed O(1)-competitive for more general objective functions such as average delay-factor and L _k norms of delay-factor (for fixed k). These metrics generalize average flow-time and L _k norms of flow-time respectively and ours are the first non-trivial results for these objective functions in broadcast scheduling.

Chandra Chekuri, Sungjin Im, Benjamin Moseley

The Routing Open Shop Problem: New Approximation Algorithms

Abstract

We consider the routing open shop problem being a generalization of the open shop and the metric travelling salesman problems. The jobs are located at nodes of some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a non-preemptive schedule that minimizes the makespan. The problem is NP-hard even on a two-node network with two machines. We present new polynomial-time approximation algorithms with worst-case performance guarantees.

Ilya Chernykh, Nikita Dryuck, Alexander Kononov, Sergey Sevastyanov

On the Price of Stability for Undirected Network Design

Abstract

We continue the study of the effects of selfish behavior in the network design problem. We provide new bounds for the price of stability for network design with fair cost allocation for undirected graphs. We consider the most general case, for which the best known upper bound is the Harmonic number H _n, where n is the number of agents, and the best previously known lower bound is 12/7 ≈ 1.778.

We present a nontrivial lower bound of 42/23 ≈ 1.8261. Furthermore, we show that for two players, the price of stability is exactly 4/3, while for three players it is at least 74/48 ≈ 1.542 and at most 1.65. These are the first improvements on the bound of H _n for general networks. In particular, this demonstrates a separation between the price of stability on undirected graphs and that on directed graphs, where H _n is tight. Previously, such a gap was only known for the cases where all players have a shared source, and for weighted players.

George Christodoulou, Christine Chung, Katrina Ligett, Evangelia Pyrga, Rob van Stee

Finding Dense Subgraphs in G(n,1/2)

Abstract

Finding the largest clique in random graphs is a well known hard problem. It is known that a random graph G(n, 1/2) almost surely has a clique of size about 2logn. A simple greedy algorithm finds a clique of size logn, and it is a long-standing open problem to find a clique of size (1 + ε)logn in randomized polynomial time. In this paper, we study the generalization of finding the largest subgraph of any given edge density. We show that a simple modification of the greedy algorithm finds a subset of 2logn vertices with induced edge density at least 0.951. We also show that almost surely there is no subset of 2.784logn vertices whose induced edge density is at least 0.951.

Atish Das Sarma, Amit Deshpande, Ravi Kannan

Parameterized Analysis of Paging and List Update Algorithms

Abstract

It is well-established that input sequences for paging and list update have locality of reference. In this paper we analyze the performance of algorithms for these problems in terms of the amount of locality in the input sequence. We define a measure for locality that is based on Denning’s working set model and express the performance of well known algorithms in term of this parameter. This introduces parameterized-style analysis to online algorithms. The idea is that rather than normalizing the performance of an online algorithm by an (optimal) offline algorithm, we explicitly express the behavior of the algorithm in terms of two more natural parameters: the size of the cache and Denning’s working set measure. This technique creates a performance hierarchy of paging algorithms which better reflects their intuitive relative strengths. Also it reflects the intuition that a larger cache leads to a better performance. We obtain similar separation for list update algorithms. Lastly, we show that, surprisingly, certain randomized algorithms which are superior to MTF in the classical model are not so in the parameterized case, which matches experimental results.

Reza Dorrigiv, Martin R. Ehmsen, Alejandro López-Ortiz

Online Scheduling of Bounded Length Jobs to Maximize Throughput

Abstract

We consider an online scheduling problem, motivated by the issues present at the joints of networks using ATM and TCP/IP. Namely, IP packets have to broken down to small ATM cells and sent out before their deadlines, but cells corresponding to different packets can be interwoven. More formally, we consider the online scheduling problem with preemptions, where each job j is revealed at release time r _j, has processing time p _j, deadline d _j and weight w _j. A preempted job can be resumed at any time. The goal is to maximize the total weight of all jobs completed on time. Our main results are as follows: we prove that if all jobs have processing time exactly k, the deterministic competitive ratio is between 2.598 and 5, and when the processing times are at most k, the deterministic competitive ratio is Θ(k/logk).

Christoph Dürr, Łukasz Jeż, Kim Thang Nguyen

On the Additive Constant of the k-Server Work Function Algorithm

Abstract

We consider the Work Function Algorithm for the k-server problem [2,4]. We show that if the Work Function Algorithm is c-competitive, then it is also strictly (2c)-competitive. As a consequence of [4] this also shows that the Work Function Algorithm is strictly (4k − 2)-competitive.

Yuval Emek, Pierre Fraigniaud, Amos Korman, Adi Rosén

A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs

Abstract

We present a (4 + ε)-approximation algorithm for the problem of computing a minimum-weight dominating set in unit disk graphs, where ε is an arbitrarily small constant. The previous best known approximation ratio was 5 + ε. The main result of this paper is a 4-approximation algorithm for the problem restricted to constant-size areas. To obtain the (4 + ε)-approximation algorithm for the unrestricted problem, we then follow the general framework from previous constant-factor approximations for the problem: We consider the problem in constant-size areas, and combine the solutions obtained by our 4-approximation algorithm for the restricted case to get a feasible solution for the whole problem. Using the shifting technique (selecting a best solution from several considered partitionings of the problem into constant-size areas) we obtain the claimed (4 + ε)-approximation algorithm. By combining our algorithm with a known algorithm for node-weighted Steiner trees, we obtain a 7.875-approximation for the minimum-weight connected dominating set problem in unit disk graphs.

Thomas Erlebach, Matúš Mihalák

Guard Games on Graphs: Keep the Intruder Out!

Abstract

A team of mobile agents, called guards, tries to keep an intruder out of an assigned area by blocking all possible attacks. In a graph model for this setting, the agents and the intruder are located on the vertices of a graph, and they move from node to node via connecting edges. The area protected by the guards is a subgraph of the given graph. We investigate the algorithmic aspects of finding the minimum number of guards sufficient to patrol the area. We show that this problem is PSPACE-hard in general and proceed to investigate a variant of the game where the intruder must reach the guarded area in a single step in order to win. We show that this case approximates the general problem, and that for graphs without cycles of length 5 the minimum number of required guards in both games coincides. We give a polynomial time algorithm for solving the one-step guarding problem in graphs of bounded treewidth, and complement this result by showing that the problem is W[1]-hard parameterized by the treewidth of the input graph. We conclude the study of the one-step guarding problem in bounded treewidth graphs by showing that the problem is fixed parameter tractable (FPT) parameterized by the treewidth and maximum degree of the input graph. Finally, we turn our attention to a large class of sparse graphs, including planar graphs and graphs of bounded genus, namely graphs excluding some fixed apex graph as a minor. We prove that the problem is FPT and give a PTAS on apex-minor-free graphs.

Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov

Between a Rock and a Hard Place: The Two-to-One Assignment Problem

Abstract

We describe the two-to-one assignment problem, a problem in between the axial three-index assignment problem and the three-dimensional matching problem, having applications in various domains. For the (relevant) case of decomposable costs satisfying the triangle inequality we provide, on the positive side, two constant factor approximation algorithms. These algorithms involve solving minimum weight matching problems and transportation problems, leading to a 2-approximation, and a \(\frac32\)-approximation. Moreover, we further show that the best of these two solutions is a \(\frac43\)-approximation for our problem. On the negative side, we show that the existence of a polynomial time approximation scheme for our problem would imply P=NP.

Dries Goossens, Sergey Polyakovskiy, Frits C. R. Spieksma, Gerhard J. Woeginger

Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width

Abstract

We study two related problems in non-preemptive scheduling and packing of malleable tasks with precedence constraints to minimize the makespan. We distinguish the scheduling variant, in which we allow the free choice of processors, and the packing variant, in which a task must be assigned to a contiguous subset of processors.

For precedence constraints of bounded width, we completely resolve the complexity status for any particular problem setting concerning width bound and number of processors, and give polynomial-time algorithms with best possible performance. For both, scheduling and packing malleable tasks, we present an FPTAS for the NP-hard problem variants and exact algorithms for all remaining special cases. To obtain the positive results, we do not require the common monotonous penalty assumption on processing times, whereas our hardness results hold even when assuming this restriction.

With the close relation between contiguous scheduling and strip packing, our FPTAS is the first (and best possible) constant factor approximation for (malleable) strip packing under special precedence constraints.

Elisabeth Günther, Felix G. König, Nicole Megow

Online Minimization Knapsack Problem

Abstract

In this paper, we address the online minimization knapsack problem, i. e., the items are given one by one over time and the goal is to minimize the total cost of items that covers a knapsack. We study the removable model, where it is allowed to remove old items from the knapsack in order to accept a new item. We obtain the following results.

1

We propose an 8-competitive deterministic and memoryless algorithm for the problem, which contrasts to the result for the online maximization knapsack problem that no online algorithm has a bounded competitive ratio [8].

2

We propose a 2e-competitive randomized algorithm for the problem.

3

We derive a lower bound 2 for deterministic algorithms for the problem.

4

We propose a 1.618-competitive deterministic algorithm for the case in which each item has its size equal to its cost, and show that this is best possible.

Xin Han, Kazuhisa Makino

Optimization Problems in Multiple Subtree Graphs

Abstract

We study various optimization problems in t-subtree graphs, the intersection graphs of t-subtrees, where a t-subtree is the union of t disjoint subtrees of some tree. This graph class generalizes both the class of chordal graphs and the class of t-interval graphs, a generalization of interval graphs that has recently been studied from a combinatorial optimization point of view. We present approximation algorithms for the Maximum Independent Set, Minimum Coloring, Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique problems in t-subtree graphs.

Danny Hermelin, Dror Rawitz

Multi-Criteria TSP: Min and Max Combined

Abstract

We present randomized approximation algorithms for multi-criteria traveling salesman problems (TSP), where some objective functions should be minimized while others should be maximized. For the symmetric multi-criteria TSP (STSP), we present an algorithm that computes (2/3 − ε, 4 + ε) approximate Pareto curves. Here, the first parameter is the approximation ratio for the objectives that should be maximized, and the second parameter is the ratio for the objectives that should be minimized. For the asymmetric multi-criteria TSP (ATSP), we present an algorithm that computes (1/2 − ε, log₂ n + ε) approximate Pareto curves. In order to obtain these results, we simplify the existing approximation algorithms for multi-criteria Max-STSP and Max-ATSP. Finally, we give algorithms with improved ratios for some special cases.

Bodo Manthey

Packet Routing: Complexity and Algorithms

Abstract

Store-and-forward packet routing belongs to the most fundamental tasks in network optimization. Limited bandwidth requires that some packets cannot move to their destination directly but need to wait at intermediate nodes on their path or take detours. In particular, for time critical applications, it is desirable to find schedules that ensure fast delivery of the packets. It is thus a natural objective to minimize the makespan, i.e., the time at which the last packet arrives at its destination. In this paper we present several new ideas and techniques that lead to novel algorithms and hardness results.

Britta Peis, Martin Skutella, Andreas Wiese

Minimal Cost Reconfiguration of Data Placement in Storage Area Network

Abstract

Video-on-Demand (VoD) services require frequent updates in file configuration on the storage subsystem, so as to keep up with the frequent changes in movie popularity. This defines a natural reconfiguration problem in which the goal is to minimize the cost of moving from one file configuration to another. The cost is incurred by file replications performed throughout the transition. The problem shows up also in production planning, preemptive scheduling with set-up costs, and dynamic placement of Web applications. We show that the reconfiguration problem is NP-hard already on very restricted instances. We then develop algorithms which achieve the optimal cost by using servers whose load capacities are increased by O(1), in particular, by factor 1 + δ for any small 0 < δ< 1 when the number of servers is fixed, and by factor of 2 + ε for arbitrary number of servers, for some ε ∈ [0,1). To the best of our knowledge, this fundamental optimization problem is studied here for the first time.

Hadas Shachnai, Gal Tamir, Tami Tamir

Competitive Multi-dimensional Dynamic Bin Packing via L-Shape Bin Packing

Abstract

We study d-dimensional dynamic bin packing for general d-dimensional boxes, for d ≥ 2. This problem is a generalization of the bin packing problem in which items may arrive and depart dynamically. Our main result is a 3^d-competitive online algorithm. We further study the 2- and 3-dimensional problem closely and improve the competitive ratios. Technically speaking, our d-dimensional result is due to a space efficient offline single bin packing algorithm, which is a variant of d-dimensional NFDH. We introduce an interesting notion of d-dimensional L-shape bin and show that effective offline packing into L-shape bin leads to effective online dynamic packing into unit-sized bins.

We also investigate the resource augmentation version of the problem where the online algorithm can use d-dimensional bins of size s ₁ ×s ₂ × ⋯ ×s _d for s _i ≥ 1 while the optimal offline algorithm uses unit-sized bins. We give conditions for the online algorithm to match the performance of the optimal offline algorithm, i.e., 1-competitive.

Prudence W. H. Wong, Fencol C. C. Yung

Springer Professional

Approximation and Online Algorithms

7th International Workshop,WAOA 2009, Copenhagen Denmark, September 10-11, 2009. Revised Papers

Inhaltsverzeichnis

Frontmatter

WAOA 2009

On the Competitiveness of the Online Asymmetric and Euclidean Steiner Tree Problems

Extension of the Nemhauser and Trotter Theorem to Generalized Vertex Cover with Applications

Price Fluctuations: To Buy or to Rent

Approximation Algorithms for Multiple Strip Packing

Approximating Frequent Items in Asynchronous Data Stream over a Sliding Window

Longest Wait First for Broadcast Scheduling [Extended Abstract]

The Routing Open Shop Problem: New Approximation Algorithms

On the Price of Stability for Undirected Network Design

Finding Dense Subgraphs in G(n,1/2)

Parameterized Analysis of Paging and List Update Algorithms

Online Scheduling of Bounded Length Jobs to Maximize Throughput

On the Additive Constant of the k-Server Work Function Algorithm

A (4 + ε)-Approximation for the Minimum-Weight Dominating Set Problem in Unit Disk Graphs

Guard Games on Graphs: Keep the Intruder Out!

Between a Rock and a Hard Place: The Two-to-One Assignment Problem

Scheduling and Packing Malleable Tasks with Precedence Constraints of Bounded Width

Online Minimization Knapsack Problem

Optimization Problems in Multiple Subtree Graphs

Multi-Criteria TSP: Min and Max Combined

Packet Routing: Complexity and Algorithms

Minimal Cost Reconfiguration of Data Placement in Storage Area Network

Competitive Multi-dimensional Dynamic Bin Packing via L-Shape Bin Packing

Backmatter

Premium Partner