# Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions

A. Aiello; E. Burattini; A. Massarotti

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1977)

- Volume: 11, Issue: 1, page 75-82
- ISSN: 0988-3754

## Access Full Article

top## How to cite

topAiello, A., Burattini, E., and 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 11.1 (1977): 75-82. <http://eudml.org/doc/92044>.

@article{Aiello1977,

author = {Aiello, A., Burattini, E., Massarotti, A.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

language = {eng},

number = {1},

pages = {75-82},

publisher = {EDP-Sciences},

title = {Reducibility as a tool to extend the power of approximation algorithms the minimization of boolean expressions},

url = {http://eudml.org/doc/92044},

volume = {11},

year = {1977},

}

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

PB - EDP-Sciences

VL - 11

IS - 1

SP - 75

EP - 82

LA - eng

UR - http://eudml.org/doc/92044

ER -

## References

top- 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. Zbl0253.68020
- 2. D. S. JOHNSON, Approximation Algorithms for Combinatorial Problems, Conference Record of Fifth ACM Symposium on Theory of Computing, 1973, p. Zbl0316.68024MR461979
- 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. Zbl0366.68041MR378476
- 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. MR418518
- 5. S. SAHNI, Computational Related Problems, S.I.A.M. J. Comp. 4, 1974, pp. 62-279. Zbl0272.68040MR433985
- 6. S. SAHNI and T. GONZALÈS, P-Complete Problems and Approximate Solutions, Computer Science Dept., University of Minnesota, 1974. MR416113
- 7. J. D. ULLMAN, Polynomial Complete Scheduling Problems, Proc. 4th Symposium on Operating System Principles, 1973, pp. 96-101.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.