✦ LIBER ✦

Strongly polynomial-time approximation for a class of bicriteria problems

✍ Scribed by Asaf Levin

Publisher: Elsevier Science
Year: 2004
Tongue: English
Weight: 190 KB
Volume: 32
Category: Article
ISSN: 0167-6377
DOI: 10.1016/j.orl.2004.02.002

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

A fully polynomial bicriteria approximat

A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem

✍ Sung-Pil Hong; Sung-Jin Chung; Bum Hwan Park 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 213 KB

We propose a fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then uti

A class of linear complementarity proble

A class of linear complementarity problems solvable in polynomial time

✍ Yinyu Ye; Panos M. Pardalos 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 653 KB

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

A polynomial time approximation scheme f

A polynomial time approximation scheme for the SONET ring loading problem

✍ Sanjeev Khanna 📂 Article 📅 2002 🏛 Institute of Electrical and Electronics Engineers 🌐 English ⚖ 110 KB 👁 1 views

A linear time 53-approximation for the m

A linear time 53-approximation for the minimum strongly-connected spanning subgraph problem

✍ Liang Zhao; Hiroshi Nagamochi; Toshihide Ibaraki 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 134 KB

A linear time 5 3 -approximation algorithm is presented for the NP-hard problem of finding a minimum strongly-connected spanning subgraph. It is based on cycle contraction that was first introduced by Khuller, Raghavachari and Young [SIAM J. Comput. 24 (1995) 859-872]. We improve their result by con