Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques
4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2001 and 5th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2001 Berkeley, CA, USA, August 18–20, 2001 Proceedings

Michel Goemans, Klaus Jansen, José D. P. Rolim, Luca Trevisan

Pozycje od 1 do 14 spośród 14 wyników

rozdział

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

rozdział

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.

rozdział

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

rozdział

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

rozdział

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.

rozdział

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

rozdział

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

rozdział

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

rozdział

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

rozdział

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

rozdział

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

rozdział

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

rozdział

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

rozdział

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

INFONA - portal komunikacji naukowej

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

Opcje filtrowania

Data publikacji

Słowa kluczowe

INFONA - portal komunikacji naukowej

Dodaj adresata

Anulowanie wysłania wiadomości

Czy na pewno chcesz anulować wysłanie wiadomości?

Wyślij wiadomość

Opcje filtrowania

Data publikacji

Ustawianie zakresu dat

Podaj zakres dat dla filtrowania wyświetlonych wyników. Możesz podać datę początkową, końcową lub obie daty. Daty możesz wpisać ręcznie lub wybrać za pomocą kalendarza.

Słowa kluczowe

Zgłaszanie błędu / nadużycia

Nieudane wysłanie zgłoszenia

Ułatwienia dostępu