| Автор | Demange, Marc |
| Автор | Paschos, Vangelis Th. |
| Дата выпуска | 1999 |
| dc.description | We first motivate and define a notion of asymptotic differential approximation ratio. For this, we introduce a new class of problems called radial problems including in particular the hereditary ones. Next, we validate the definition of the asymptotic differential approximation ratio by proving positive, conditional and negative approximation results for some combinatorial problems. We first derive a differential approximation analysis of a classical greedy algorithm for bin packing, the “first fit decreasing”. Next we deal with minimum vertex-covering-by-cliques of a graph and the minimum edge-covering-by-complete-bipartite-subgraphs of a bipartite graph and devise a differential-approximation preserving reduction from the former to the latter. Finally, we prove two negative differential approximation results about the ability of minimum vertex-coloring to be approximated by a polynomial time approximation schema. |
| Формат | application.pdf |
| Издатель | EDP Sciences |
| Копирайт | © EDP Sciences, 1999 |
| Тема | NP-complete problem |
| Тема | complexity |
| Тема | polynomial time approximation algorithm |
| Тема | bin packing |
| Тема | coloring |
| Тема | covering. |
| Название | Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems |
| Тип | research-article |
| DOI | 10.1051/ro:1999121 |
| Electronic ISSN | 1290-3868 |
| Print ISSN | 0399-0559 |
| Журнал | RAIRO - Operations Research |
| Том | 33 |
| Первая страница | 481 |
| Последняя страница | 507 |
| Аффилиация | Demange Marc; CERMSEM, Universite Paris I, 106-112 boulevard de l'Hôpital, 75647 Paris Cedex 13, France. |
| Аффилиация | Paschos Vangelis Th.; LAMSADE, Universite Paris-Dauphine, Place du Marechal de Lattre de Tassigny, 75775 Paris Cedex 16, France. |
| Выпуск | 4 |
