Что в настоящее время известно о приближаемости проблемы рода? Предварительный поиск говорит мне , что постоянное приближение фактора тривиально для достаточно плотных графов, и -приближение алгоритм было исключено. Является ли эта информация актуальной или известны более точные границы?
11
Я хотел бы добавить к исчерпывающему ответу JɛE, что, насколько мне известно, нет нижних границ для коэффициента аппроксимации для этой задачи. Насколько нам известно, может существовать алгоритм аппроксимации, который всегда дает приближение с постоянным множителем (даже если род очень мал).
источник