Chris Gast
|
Verfasst am: 25. Nov 2005 09:43 Titel: 4 Farbensatz, Approximationsalgorithmen |
|
|
Hallo zusammen,
ich würde gerne zeigen, dass es keinen Approximationsalgorithmus für den 4 Farbensatz gibt mit Approximationsquotient <= 4/3. Ich vermute, dass man das am besten mit einer Reduktion auf ein anderes Problem machen kann, das auch in APX liegt. Kennt jemand einen Weblink zum Thema APX und Reduktionen und so? Wäre wirklich dankbar.
Viele Grüße, Christian |
|