Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977) no. 1, pp. 75-82.
@article{ITA_1977__11_1_75_0,
author = {Aiello, A. and Burattini, E. and Massarotti, A.},
title = {Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {75--82},
publisher = {Centrale des revues, Dunod-Gauthier-Villars},
volume = {11},
number = {1},
year = {1977},
zbl = {0366.94048},
mrnumber = {478742},
language = {en},
url = {http://www.numdam.org/item/ITA_1977__11_1_75_0/}
}
TY  - JOUR
AU  - Aiello, A.
AU  - Burattini, E.
AU  - Massarotti, A.
TI  - Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1977
DA  - 1977///
SP  - 75
EP  - 82
VL  - 11
IS  - 1
PB  - Centrale des revues, Dunod-Gauthier-Villars
PP  - Montreuil
UR  - http://www.numdam.org/item/ITA_1977__11_1_75_0/
UR  - https://zbmath.org/?q=an%3A0366.94048
UR  - https://www.ams.org/mathscinet-getitem?mr=478742
LA  - en
ID  - ITA_1977__11_1_75_0
ER  - 
Aiello, A.; Burattini, E.; Massarotti, A. Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 11 (1977) no. 1, pp. 75-82. http://www.numdam.org/item/ITA_1977__11_1_75_0/

1. S. Cook, The Complexity of Theorem Proving Procedures, Proc. 3rd Annual ACM Symposium on Theory of Computing, 1971, pp. 151-158. p. 38-49. | Zbl 0253.68020

2. D. S. Johnson, Approximation Algorithms for Combinatorial Problems, Conference Record of Fifth ACM Symposium on Theory of Computing, 1973, p. | MR 461979 | Zbl 0316.68024

3. R. M. Karp, Reducibility Among Combinatorial Problems, In Complexity of Computer Computations, R. E. MILLER and J. W. THATCHER Eds and Plenum Press, New York, 1972, pp. 85-104. | MR 378476 | Zbl 0366.68041

4. A. R. Meyer and L. Stockmeyer, Non Elementary Word Problems in Automata and Logic, Proc. AMS Symposium on Complexity of Computation, 1973, pp. 38-49. | MR 418518

5. S. Sahni, Computational Related Problems, S.I.A.M. J. Comp. 4, 1974, pp. 62-279. | MR 433985 | Zbl 0272.68040

6. S. Sahni and T. Gonzalès, P-Complete Problems and Approximate Solutions, Computer Science Dept., University of Minnesota, 1974. | MR 416113

7. J. D. Ullman, Polynomial Complete Scheduling Problems, Proc. 4th Symposium on Operating System Principles, 1973, pp. 96-101.