Differential approximation algorithms for some combinatorial optimization problems. (English) Zbl 0912.68061
Summary: We use a new approximation measure, the differential approximation ratio, to derive polynomial-time approximation algorithms for minimum set covering (for both weighted and unweighted cases), minimum graph coloring and bin-packing. We also propose differential-approximation-ratio preserving reductions linking minimum coloring, minimum vertex covering by cliques, minimum edge covering by cliques and minimum edge covering of a bipartite graph by complete bipartite graphs.
MSC:
| 68W10 | Parallel algorithms in computer science |
Keywords:
NP-complete problem; polynomial time approximation algorithm; set covering; coloring; bin-packingReferences:
| [1] | Arora, S.; Lund, C.; Motwani, R.; Sudan, M.; Szegedy, M., Proof verification and intractability of approximation problems, (Proc. FOCS’92 (1992)), 14-23 · Zbl 0977.68539 |
| [2] | 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 |
| [3] | Blum, A., New approximation algorithms for graph coloring, J. ACM, 41, 3, 470-516 (1994) · Zbl 0821.68092 |
| [4] | Brooks, R. L., On coloring the nodes of a network, (Proc. Cambridge Philos. Soc., 37 (1941)), 194-197 · Zbl 0027.26403 |
| [5] | Chvátal, V., A greedy — heuristic for the set covering problem, Math. Oper. Res., 4, 233-235 (1979) · Zbl 0443.90066 |
| [6] | Demange, M.; Grisoni, P.; Paschos, V. Th., Approximation results for the minimum graph coloring problem, Inform. Process. Lett., 50, 19-23 (1994) · Zbl 0806.68085 |
| [7] | Demange, M.; Paschos, V. Th., On an approximation measure founded on the links between optimization and polynomial approximation theory, Theoret. Comput. Sci., 158, 117-141 (1996) · Zbl 0871.90069 |
| [8] | de la Vega, W. Fernandez; Lueker, G. S., Bin packing can be solved within \(1 + ε\) in linear time, Combinatorica, 1, 4, 349-355 (1981) · Zbl 0485.68057 |
| [9] | Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company San Francisco · Zbl 0411.68039 |
| [10] | Halldórsson, M. M., A still better performance guarantee for approximate graph coloring, Inform. Process. Lett., 45, 19-23 (1993) · Zbl 0768.68043 |
| [11] | Halldórsson, M. M., Approximating discrete collections via local improvements, (Proc. Symp. on Disc. Maths (1995)), 160-169 · Zbl 0847.90136 |
| [12] | Halldórsson, M. M., Approximating set cover via local improvements, (JAIST Resarch Report IS-RR-95-0002F (1995), JAIST: JAIST Tatsunokuchi, Japan) · Zbl 0847.90136 |
| [13] | Hassin, R.; Lahav, S., Maximizing the number of unused colors in the vertex coloring problem, Inform. Process. Lett., 52, 87-90 (1994) · Zbl 0809.05047 |
| [14] | Johnson, D. S., Approximation algorithms for combinatorial problems, J. Comput. System Sci., 9, 256-278 (1974) · Zbl 0296.65036 |
| [15] | Kou, L. T.; Stockmeyer, L. J.; Wong, C. K., Covering edges by cliques with regard to keyword conflicts and intersection graphs, Comm. ACM, 21, 135-139 (1978) · Zbl 0367.68035 |
| [16] | Lovász, L., Three short proofs in graph theory, J. Comb. Theory B, 19, 269-271 (1975) · Zbl 0322.05142 |
| [17] | Lovász, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383-390 (1975) · Zbl 0323.05127 |
| [18] | Lund, C.; Yannakakis, M., On the hardness of approximating minimization problems, (Proc. STOC’93 (1993)), 286-293 · Zbl 1310.68094 |
| [19] | Simon, H. U., On approximate solutions for combinatorial optimization problems, SIAM J. Discrete Math., 3, 2, 294-310 (1990) · Zbl 0699.68077 |
| [20] | Vavasis, S. A., Approximation algorithms for indefinite quadratic programming, Math. Programming, 57, 279-311 (1992) · Zbl 0845.90095 |
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.
