×

Bridging gap between standard and differential polynomial approximation: The case of bin-packing. (English) Zbl 0942.68144

Summary: The purpose of this paper is mainly to prove the following theorem: for every polynomial time algorithm running in time \(T(n)\) and guaranteeing standard-approximation ratio \(\rho\) for bin-packing, there exists an algorithm running in time \(O(nT(n))\) and achieving differential-approximation ratio \(2-\rho\) 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.

MSC:

68W05 Nonnumerical algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Garey, M. R.; Johnson, D. S., Computers and Intractability. A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco, CA · Zbl 0411.68039
[2] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithms and Complexity (1981), Prentice Hall: Prentice Hall Englewood Cliffs, NJ
[3] Demange, M.; Paschos, V. T., On an approximation measure founded on the links between optimization and polynomial approximation theory, Theoret. Comput. Sci., 158, 117-141 (1996) · Zbl 0871.90069
[4] M. Demange, P. Grisoni and V.T. Paschos, Differential approximation algorithms for some combinatorial optimization problems, Theoret. Comput. Sci.; M. Demange, P. Grisoni and V.T. Paschos, Differential approximation algorithms for some combinatorial optimization problems, Theoret. Comput. Sci. · Zbl 0912.68061
[5] Ausiello, G.; D’Atri, A.; Protasi, M., Structure preserving reductions among convex optimization problems, J. Comput. System Sci., 21, 136-153 (1980) · Zbl 0441.68049
[6] Halldórsson, M. M., Approximating \(k\)-set cover and complementary graph coloring, (Proc. International Integer Programming and Combinatorial Optimization Conference. Proc. International Integer Programming and Combinatorial Optimization Conference, Number 1084 in Lecture Notes in Computer Science (1996), Springer-Verlag), 118-131 · Zbl 1415.90103
[7] Feige, U.; Kilian, J., Zero knowledge and the chromatic number, (Proc. Conference on Computational Complexity (1996)), 278-287
[8] Håstad, J., Clique is hard to approximate within \(n^{1−ϵ}\), (Proc. FOCS ’96 (1996)), 627-636
[9] Håstad, J., Testing on the long code and hardness for clique, (Proc. STOC ’96 (1996)), 11-19 · Zbl 0922.68066
[10] Bar-Yehuda, R.; Even, S., A local-ratio theorem for approximating the weighted vertex cover problem, Ann. Discrete Appl. Math., 25, 27-46 (1985) · Zbl 0557.90072
[11] Johnson, D. S., Fast algorithms for bin packing, J. Comput. System Sci., 8, 272-314 (1974) · Zbl 0284.68023
[12] Johnson, D. S.; Demers, A.; Ullman, J. D.; Garey, M. R.; Graham, R. L., Worst-case performance bounds for simple one-dimensional packing algorithms, SIAM J. Comput., 3, 4, 298-325 (1974) · Zbl 0297.68028
[13] Fernandez de la Vega, W.; Lueker, G. S., Bin packing can be solved within \(1 + ϵ\) in linear time, Combinatorica, 1, 4, 349-355 (1981) · Zbl 0485.68057
[14] J. Monnot, Familles d’instances critiques et approximation polynomiale, Ph.D. Thesis, LAMSADE, Université Paris-Dauphine (in preparation).; J. Monnot, Familles d’instances critiques et approximation polynomiale, Ph.D. Thesis, LAMSADE, Université Paris-Dauphine (in preparation).
[15] Paz, A.; Moran, S., Nondeterministic polynomial optimization problems and their approximations, Theoret. Comput. Sci., 15, 251-277 (1981) · Zbl 0459.68015
[16] Anstreicher, K. M., Linear programming in \(O((n^3\)/log \(n)L)\) operations, (Discussion Paper 9746 (June 1997), CORE, Université Catholique de Louvain) · Zbl 0955.90085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.