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?
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP