Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques

chapter

Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows

Susanne Albers, Carsten Witt

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 12-24

We study integrated prefetching and caching in single and parallel disk systems. A recent approach used linear programming to solve the problem. We show that integrated prefetching and caching can also be formulated as a min-cost multicommodity flow problem and, exploiting special properties of our network, can be solved using combinatorial techniques. Moreover, for parallel disk systems, we develop...

chapter

On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique

Reuven Bar-Yehuda, Dror Rawitz

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 24-36

We discuss two approximation approaches, the primal-dual schema and the local-ratio technique. We present two relatively simple frameworks, one for each approach, which extend known frameworks for covering problems. We show that the two are equivalent, and conclude that the integrality gap of an integer program serves as a bound to the approximation ratio when working with the local-ratio technique.

chapter

Online Weighted Flow Time and Deadline Scheduling

Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Kirk R. Pruhs

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 36-47

In this paper we study some aspects of weighted flow time on parallel machines. We first show that the online algorithm Highest Density First is an O(1)-speed O(1)-approximation algorithm for P|r _i, pmtn| Σw_iF_i. We then consider a related Deadline Scheduling Problem that involves minimizing the weight of the jobs unfinished by some unknown deadline D on a uniprocessor. We show that any c-competitive...

chapter

An Online Algorithm for the Postman Problem with a Small Penalty

Piotr Berman, Junichiro Fukuyama

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 48-54

The Postman Problem is defined in the following manner: Given a connected graph G and a start point s τ V(G), we call a path J in G a postman tour if J starts and ends at s and contains every edge in E(G). We want to find a shortest postman tour in G. Thus, we minimize the number |J| - |E(G)|, called the penalty of J for G. In this paper, we consider two online versions of The Postman Problem,...

chapter

A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem

Adriana Bumb, Walter Kern

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 55-63

We present a simple dual ascent method for the multilevel facility location problem which finds a solution within 6 times the optimum for the uncapacitated case and within 12 times the optimum for the capacitated one. The algorithm is deterministic and based on the primal-dual technique.

chapter

Approximation Schemes for Ordered Vector Packing Problems

Alberto Caprara, Hans Kellerer, Ulrich Pferschy

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 63-75

In this paper we deal with the d-dimensional vector packing problem, which is a generalization of the classical bin packing problem in which each item has d distinct weights and each bin has d corresponding capacities. We address the case in which the vectors of weights associated with the items are totally ordered, i.e., given any two weight vectors a _i, a _j, either a ...

chapter

Incremental Codes

Yevgeniy Dodis, Shai Halevi

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 75-90

We introduce the notion of incremental codes. Unlike a regular code of a given rate, which is an unordered set of elements with a large minimum distance, an incremental code is an ordered vector of elements each of whose prefixes is a good regular code (of the corresponding rate). Additionally, while the quality of a regular code is measured by its minimum distance, we measure the quality of an incremental...

chapter

A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set

Guy Even, Jon Feldman, Guy Kortsarz, Zeev Nutov

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 90-101

We consider the following problem: given a connected graph G = (V, ε E) and an additional edge set E, find a minimum size subset of edges F ⊆ E such that (V, ε ∪ F) is 2-edge connected. This problem is NP-hard. For a long time, 2 was the best approximation ratio known. Recently, Nagamochi reported a (1.875 + ε)-approximation algorithm. We give a new algorithm with a better approximation ratio of 3/2...

chapter

Approximation Algorithms for Budget-Constrained Auctions

Rahul Garg, Vijay Kumar, Vinayaka Pandit

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 102-113

Recently there has been a surge of interest in auctions research triggered on the one hand by auctions of bandwidth and other public assets and on the other by the popularity of Internet auctions and the possibility of new auction formats enabled by e-commerce. Simultaneous auction of items is a popular auction format. We consider the problem of maximizing total revenue in the simultaneous auction...

chapter

Minimizing Average Completion of Dedicated Tasks and Interval Graphs

Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 114-126

Scheduling dependent jobs on multiple machines is modeled as a graph (multi)coloring problem. The focus of this work is on the sum of completion times measure. This is known as the sum (multi)coloring of the conflict graph. We also initiate the study of the waiting time and the robust throughput of colorings. For uniform-length tasks we give an algorithm which simultaneously approximates these two...

chapter

A Greedy Facility Location Algorithm Analyzed Using Dual Fitting

Mohammad Mahdian, Evangelos Markakis, Amin Saberi, Vijay Vazirani

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 127-137

We present a natural greedy algorithm for the metric uncapacitated facility location problem and use the method of dual fitting to analyze its approximation ratio, which turns out to be 1.861. The running time of our algorithm is O(m log m), where m is the total number of edges in the underlying complete bipartite graph between cities and facilities. We use our algorithm to improve recent results...

chapter

0.863-Approximation Algorithm for MAX DICUT

Shiro Matuura, Tomomi Matsui

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 138-146

In this paper, we propose 0.863-approximation algorithm for MAX DICUT. The approximation ratio is better than the previously known result by Zwick, which is equal to 0.8596434254. The algorithm solves the SDP relaxation problem proposed by Goemans and Williamson for the first time. We do not use the ‘rotation’ technique proposed by Feige and Goemans. We improve the approximation ratio by using...

chapter

The Maximum Acyclic Subgraph Problem and Degree-3 Graphs

Alantha Newman

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 147-158

We study the problem of finding a maximum acyclic subgraph of a given directed graph in which the maximum total degree (inplus out) is 3. For these graphs, we present: (i) a simple combinatorial algorithm that achieves an 11/12-approximation (the previous best factor was 2/3 [1]), (ii) a lower bound of 125/126 on approximability, and (iii) an approximation-preserving reduction from the general case:...

chapter

Some Approximation Results for the Maximum Agreement Forest Problem

Estela Maris Rodrigues, Marie-France Sagot, Yoshiko Wakabayashi

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of APPROX > 159-169

There are various techniques for reconstructing phylogenetic trees from data, and in this context the problem of determining how distant two such trees are from each other arises naturally. Various metrics (NNI, SPR, TBR) for measuring the distance between two phylogenies have been defined. Another way of comparing two trees $$ \mathcal{T} $$ and $$ \mathcal{U} $$ is to compute the so called maximum agreement forest...

chapter

Near-optimum Universal Graphs for Graphs with Bounded Degrees

Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, more

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of RANDOM > 170-180

Let $$ \mathcal{H} $$ be a family of graphs. We say that G is $$ \mathcal{H} $$-universal if, for each H ∈ $$ \mathcal{H} $$, the graph G contains a subgraph isomorphic to H. Let $$ \mathcal{H} $$ (k, n) denote the family of graphs on n vertices with maximum degree at most k. For each fixed k and each n sufficiently large, we explicitly construct an $$ \mathcal{H} $$ (k, n)-universal graph Γ(k, n)...

chapter

On a Generalized Ruin Problem

Kazuyuki Amano, John Tromp, Paul M. B. Vitányi, Osamu Watanabe

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of RANDOM > 181-191

We consider a natural generalization of the classical ruin problem to more than two parties. Our “ruin” problem, which we will call the (k, I)-game, starts with k players each having I units as its initial capital. At each round of the game, all remaining k′ players pay 1/k′th unit as game fee, play the game, and one of the players wins and receives the combined game fees of 1 unit. A player who cannot...

chapter

On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation

Andreas Baltz, Tomasz Schoen, Anand Srivastav

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of RANDOM > 192-201

We study the relationship between the value of optimal solutions to the random asymmetric b-partite traveling salesman problem and its assignment relaxation. In particular we prove that given a bn×bn weight matrix W = (w _ij) such that each finite entry has probability p _n of being zero, the optimal values bATSP(W) and AP(W) are equal (almost surely), whenever...

chapter

Exact Sampling in Machine Scheduling Problems

Sung-woo Cho, Ashish Goel

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of RANDOM > 202-210

Analysis of machine scheduling problem can get very complicated even for simple scheduling policies and simple arrival processes. The problem becomes even harder if the scheduler and the arrival process are complicated, or worse still, given to us as a black box. In such cases it is useful to obtain a typical state of the system which can then be used to deduce information about the performance of...

chapter

On Computing Ad-hoc Selective Families

Andrea E. F. Clementi, Pilu Crescenzi, Angelo Monti, Paolo Penna, more

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of RANDOM > 211-222

We study the problem of computing ad-hoc selective families: Given a collection $$ \mathcal{F} $$ of subsets of [n] = {1,2,...,n}, a selective family for $$ \mathcal{F} $$ is a collection $$ \mathcal{S} $$ of subsets of [n] such that for any F ∈ $$ \mathcal{F} $$ there exists S ∈ $$ \mathcal{S} $$ such that |F ∩ S|=1. We first provide a polynomial-time algorithm that, for any instance $$ \mathcal{F}...

chapter

L Infinity Embeddings

Don Coppersmith

Lecture Notes in Computer Science > Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques > Contributed Talks of RANDOM > 223-228

Given ε, for N sufficiently large, we give a metric on N points which cannot be isometrically embedded in l ^b _∞ for b <; N - N ^ε.

INFONA - science communication portal

Minimizing Stall Time in Single and Parallel Disk Systems Using Multicommodity Network Flows

On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique

Online Weighted Flow Time and Deadline Scheduling

An Online Algorithm for the Postman Problem with a Small Penalty

A Simple Dual Ascent Algorithm for the Multilevel Facility Location Problem

Approximation Schemes for Ordered Vector Packing Problems

Incremental Codes

A 3/2-Approximation Algorithm for Augmenting the Edge-Connectivity of a Graph from 1 to 2 Using a Subset of a Given Edge Set

Approximation Algorithms for Budget-Constrained Auctions

Minimizing Average Completion of Dedicated Tasks and Interval Graphs

A Greedy Facility Location Algorithm Analyzed Using Dual Fitting

0.863-Approximation Algorithm for MAX DICUT

The Maximum Acyclic Subgraph Problem and Degree-3 Graphs

Some Approximation Results for the Maximum Agreement Forest Problem

Near-optimum Universal Graphs for Graphs with Bounded Degrees

On a Generalized Ruin Problem

On the b-Partite Random Asymmetric Traveling Salesman Problem and Its Assignment Relaxation

Exact Sampling in Machine Scheduling Problems

On Computing Ad-hoc Selective Families

L Infinity Embeddings

Filter options

Publication date

Content availability

Publication language

Keywords

INFONA - science communication portal

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Content availability

Publication language

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options