Από το τεύχος 43 του περιοδικού Δελτίο της Ελληνικής Μαθηματικής Εταιρίας

It is known that polynomial approximation theory, developed as the main tool for investigating {|bf NP}-complete problems, can also motivate numerous questions addressed to the heart of complexity theory. The aim of the present paper is to describe a general thought process for the study of the relative hardness between determining solutions and computing (approximately or exactly) optimal solution-values of combinatorial optimization problems. In the particular case of the maximum independent set, this thought process leads us to define classes of independent set problems, the approximability of which is particularly interesting.

Στοιχεία Άρθρου

Περιοδικό	Δελτίο της Ελληνικής Μαθηματικής Εταιρίας
Αρ. Τεύχους	Τεύχος 43
Περίοδος	2000
Συγγραφέας	Vangelis Th. Paschos
Αρ. Αρθρου	2
Σελίδες	37-54
Γλώσσα	-
Λέξεις Κλειδιά	relative hardness, constructive-non-constructive approximation

Studying graph - stability to apprehend relative hardness of constructive-non-constructive approximation