TransWikia.com

Where to find info on (polytime) approximability of various discrete optimization problems?

Theoretical Computer Science Asked on October 30, 2021

Where to find info on (polytime) approximability of various discrete optimization problems?

Sorry if this is stupid,but is there a site or reference that keeps up to date info on approximability of various optimization problems?

2 Answers

The compendium from Crescenzi is the most complete that I am aware of, despite being pretty old now. You can also watch this more recent (still twelve years old) survey:

Vangelis Paschos. An overview on polynomial approximation of NP-hard problems. https://hal.archives-ouvertes.fr/hal-00186549/document

Answered by Nicolas GZ on October 30, 2021

The following website seems to be no longer maintained, but it is still a useful resource because it covers many problems: http://www.csc.kth.se/~viggo/problemlist/

Answered by Hermann Gruber on October 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP