Wyniki wyszukiwania - Biblioteka Nauki

Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl

Ograniczanie wyników

2 Foundations of Computing and Decision Sciences

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

A note on the NP-completeness of the precoloring extension coloring problem in triangle free planar graphs

100%

Monnot J.

Foundations of Computing and Decision Sciences

2006

tom Vol. 31, No. 2

169-173

The precoloring extension coloring problem consists in deciding, given a positive integer k, a graph G = (V,E] and k pairwise disjoint subsets Vo, ..., Vk-1 of V, if there exists a (vertex) coloring S = (So,...,Sk-i) of G such that Vi ⊇ Si, for all i = 0,...,k-1:— 1. In this note, we show that the precoloring extension coloring problem is NP-complete in triangle free planar graphs with maximum degree 4.

Maximizing the number of unused bins

51%

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

Foundations of Computing and Decision Sciences

2001

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