Abstract
In this paper the concept of combinatorial problem associated to an optimization problem is defined. A partial ordering over an optimization problem is then introduced: all input elements of an optimization problem are classified according to their "structure" (based on the number of approximate solutions of different measure) and then the classes of elements are partially ordered according to the richness of their structures. In this way structure preserving reductions among NP-complete problems can be introduced and some conditions for a reduction to preserve the structure of a combinatorial problem are given.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
Bibliography
S.COOK: The complexity of theorems proving procedures. Proc 3rd ACM Symposium Theory of Computing (1971).
M.R.GAREY, D.S.JOHNSON: The complexity of near-optimal graph coloring. Journal of ACM (1976), 23–1.
J.HARTMANIS, L.BERMAN: On isomorphisms and density of NP and other complete sets. Proc 8th ACM Symposium Theory of Computing (1976).
D.JOHNSON: Approximation algorithms for combinatorial problems. JCSS (1974), 9.
R.M. KARP: Reducibility among combinatorial problems. In "Complexity of computer computations", R.E. Miller and J.W. Thatcher, Eds. Plenum Press, New York (1972).
S.SAHNI: Algorithms for scheduling independent tasks. Journal of ACM (1976), 23–1.
S.SAHNI, T.GONZALES: P-Complete problems and approximate solutions. Proc IEEE 15th annual Symposium on Switching and Automata Theory (1974).
J.SIMON: On some central problems in computational complexity. Cornell University Department of Computer Science TR 75-224 (1975).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1977 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ausiello, G., D'Atri, A., Protasi, M. (1977). On the structure of combinatorial problems and structure preserving reductions. In: Salomaa, A., Steinby, M. (eds) Automata, Languages and Programming. ICALP 1977. Lecture Notes in Computer Science, vol 52. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-08342-1_4
Download citation
DOI: https://doi.org/10.1007/3-540-08342-1_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-08342-9
Online ISBN: 978-3-540-37305-6
eBook Packages: Springer Book Archive