Title: On the Complexity of Approximating Colored-Graph Problems Extended Abstract
Abstract: In this paper we prove explicit lower bounds on the approximability of some graph problems restricted to instances which are already colored with a constant number of colors. As far as we know, this is the first time these problems are explicitily defined and analyzed. This allows us to drastically improve the previously known inapproximability results which were mainly a consequence of the analysis of bounded-degree graph problems. Moreover, we apply one of these results to obtain new lower bounds on the approximabiluty of the minimum delay schedule problem on store-and-forward networks of bounded diameter. Finally, we propose a generalization of our analysis of the complexity of approximating colored-graph problems to the complexity of approximating approximated optimization problems.
Publication Year: 1999
Publication Date: 1999-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 8
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot