✦ LIBER ✦

Approximation schemes for ordered vector packing problems

✍ Scribed by Alberto Caprara; Hans Kellerer; Ulrich Pferschy

Publisher: John Wiley and Sons
Year: 2003
Tongue: English
Weight: 134 KB
Volume: 50
Category: Article
ISSN: 0894-069X
DOI: 10.1002/nav.10058

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Polynomial time approximation schemes fo

Polynomial time approximation schemes for class-constrained packing problems

✍ Hadas Shachnai; Tami Tamir 📂 Article 📅 2001 🏛 Springer US 🌐 English ⚖ 207 KB

We consider variants of the classic bin packing and multiple knapsack problems, in which sets of items of di erent classes (colours) need to be placed in bins; the items may have di erent sizes and values. Each bin has a limited capacity, and a bound on the number of distinct classes of items it can

Packing and Decomposition Problems for P

Packing and Decomposition Problems for Polynomial Association Schemes

✍ V.I. Levenshtein 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 496 KB

We consider \(P\) - and \(Q\)-polynomial association schemes and introduce definitions of Delsarte codes and decomposable schemes. Many known combinatorial notions can be defined as Delsarte codes in suitable association schemes, and almost all classical association schemes turn out to be decomposab

Efficient Approximation Algorithms for T

Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles

✍ Piotr Berman; Bhaskar DasGupta; S Muthukrishnan; Suneeta Ramaswami 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 202 KB

We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE, and d-RPACK) studied in the literature. Most of our algorithms are highly efficient since their running times are near-linear in the sparse input size rather than in the domain size. In add

An improved approximation scheme for the

An improved approximation scheme for the Group Steiner Problem

✍ C. S. Helvig; Gabriel Robins; Alexander Zelikovsky 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 322 KB 👁 1 views

the Group Steiner Problem asks for a minimumcost tree which contains at least one node from each group N i N i N i . In this paper, we give polynomial-time O O O(k k k )approximation algorithms for any fixed > > > 0. This result improves the previously known O O O(k k k)-approximation. We also apply

NC-Approximation Schemes for NP- and PSP

NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs

✍ Harry B Hunt III; Madhav V Marathe; Venkatesh Radhakrishnan; S.S Ravi; Daniel J 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 303 KB

We present NC-approximation schemes for a number of graph problems when restricted to geometric graphs including unit disk graphs and graphs drawn in a civilized manner. Our approximation schemes exhibit the same time versus performance trade-off as the best known approximation schemes for planar gr

Polynomial Time Approximation Schemes fo

Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems

✍ Sanjeev Arora; David Karger; Marek Karpinski 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 250 KB

We present a unified framework for designing polynomial time approximation schemes (PTASs) for ``dense'' instances of many NP-hard optimization problems, including maximum cut, graph bisection, graph separation, minimum k-way cut with and without specified terminals, and maximum 3-satisfiability. By