Bridging gap between standard and differential polynomial approxiamtion: the case of bin-packing
Demange, Marc ; Monnot, Jérôme ; Paschos, Vangelis.
HAL, hal-00004007 / Harvested from HAL
Text on HAL
The purpose of this paper is to mainly prove the following theorem: for every polynomial time algorithm running in time T(n) and guaranteeing standard-approximation ratio p for bin-packing, there exists an algorithm running in time O(nT(n)) and achieving differential-approximation ratio 2 - p for BP. This theorem has two main impacts. The first one is operational, deriving a polynomial time differential-approximation schema for bin-packing. The second one is structural, establishing a kind of reduction (to our knowledge not existing until now) between standard approximation and differential one.
Publié le : 1999-07-05
Classification:  Reductions,  Approximate algorithms,  Differential ratio,  Performance ratio,  Analysis of Algorithms,  F.1.3, G.2,  [MATH.MATH-GM]Mathematics [math]/General Mathematics [math.GM],  [INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC],  [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 
@article{hal-00004007,
     author = {Demange, Marc and Monnot, J\'er\^ome and Paschos, Vangelis.},
     title = {Bridging gap between standard and differential polynomial approxiamtion: the case of bin-packing},
     journal = {HAL},
     volume = {1999},
     number = {0},
     year = {1999},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00004007}
}

Demange, Marc; Monnot, Jérôme; Paschos, Vangelis. Bridging gap between standard and differential polynomial approxiamtion: the case of bin-packing. HAL, Tome 1999 (1999) no. 0, . http://gdmltest.u-ga.fr/item/hal-00004007/