Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Foundations of Computing and Decision Sciences

2 2001

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Maximizing the number of unused bins

Demange M., Monnot J., Paschos V. T.

Foundations of Computing and Decision Sciences

2001

Vol. 26, No. 2

169-186

We analyze the approximation behavior of some of the best-known polynomial-time approximation algorithms for bin-packing under an approximation criterion, called differential ratio, informally the ratio (n — where n is the size of the input list, is the size of the solution provided by an approximation algorithm and Beta(I) is the size of the optimal one. This measure has originally been introduced by Ausiello, D'Atri and Protasi and more recently revisited, in a more systematic way, by the first and the third authors of the present paper. Under the differential ratio, bin-packing has a natural formulation as the problem of maximizing the number of unused bins. We first show that two basic fit bin-packing algorithms, the first-fit and the best-fit, admit differential approximation ratios 1/2. Next, we show that slightly improved versions of them achieve ratios 2/3. Refining our analysis we show that the famous first-fit-decreasing and best-fit decreasing algorithms achieve differential approximation ratio 3/4: Finally, we show that first-fit-decreasing achieves asymptotic differential approximation ratio 7/9.

Approximating values and solutions of NP-optimization problems: concepts and examples

Demange M., Lorenzo J.

Foundations of Computing and Decision Sciences

2001

Vol. 26, No. 2

145-168

We shape a formal framework for distinguishing the behaviour of constructive and non-constructive polynomial time approximation algorithms for NP optimization problems. We introduce a new class, called SubNPO (sub-problems of NPO), that includes NPO and also some other problems used in recent works. For this class, we define two types of approximation algorithms: the constructive ones and the non-constructive ones. For both cases we extend the notions of approximation level, of approximation-preserving' reductions and of related completeness. Then, we devise, under a completeness hypothesis, an equivalence result between constructive approximation and the non-constructive one. It generalizes to the case of polynomial time approximation a famous result of A. Paz and S. Moran. We finally point out some cases where both points of view differ from each other. In particular, we show that several problems, known to be complete for polynomial time constructive approximation, are not complete for the non-constructive one.