Сложность расширения
В выпуклой геометрии и многогранной комбинаторике сложность расширения многогранника выпуклого - наименьшее количество граней среди выпуклых многогранников. которые имеют как проекция. В этом контексте называется расширенной формулировкой ; оно может иметь гораздо более высокое измерение, чем . [1] [2] [3]
Сложность расширения зависит от точной формы , а не только по его комбинаторной структуре. Например, правильные многоугольники с стороны имеют сложность расширения (выражено с использованием обозначения «большое О» ), [4] [5] но какой-то другой выпуклый -угольники имеют сложность расширения, по меньшей мере пропорциональную . [5]
Если многогранник, описывающий возможные решения задачи комбинаторной оптимизации , имеет низкую сложность расширения, его потенциально можно использовать для разработки эффективных алгоритмов решения проблемы с использованием линейного программирования в его расширенной формулировке. По этой причине исследователи изучили сложность расширения возникающих таким образом многогранников. [6] Например, известно, что совпадающий многогранник имеет экспоненциальную сложность расширения. [7] С другой стороны, многогранник независимости правильных матроидов имеет полиномиальную сложность расширения. [8]
Понятие сложности расширения также было обобщено с линейного программирования на полуопределенное программирование путем рассмотрения проекций спектрэдров вместо проекций многогранников. [9] [10]
Ссылки
[ редактировать ]- ^ Балас, Эгон (2005), «Проекция, подъем и расширенная формулировка в целочисленной и комбинаторной оптимизации», Annals of Operations Research , 140 : 125–161, doi : 10.1007/s10479-005-3969-1 , MR 2194735 , S2CID 18252683
- ^ Кайбел, Волкер (2011), «Расширенные формулировки в комбинаторной оптимизации», Optima , 85 : 2–7, arXiv : 1104.1023
- ^ Конфорти, Микеле; Корнюжоль, Жерар ; Замбелли, Джакомо (2013), «Расширенные формулировки в комбинаторной оптимизации», Annals of Operations Research , 204 : 97–143, CiteSeerX 10.1.1.483.9715 , doi : 10.1007/s10479-012-1269-0 , MR 3039264 , S2CID 2542 36751
- ^ Бен-Тал, Аарон; Немировский, Аркадий (2001), «О многогранных аппроксимациях конуса второго порядка», Математика исследования операций , 26 (2): 193–205, doi : 10.1287/moor.26.2.193.10561 , MR 1895823
- ^ Перейти обратно: а б Фиорини, Самуэль; Ротвосс, Томас; Тивари, Ханс Радж (2012), «Расширенные формулировки для многоугольников», Дискретная и вычислительная геометрия , 48 (3): 658–668, arXiv : 1107.0371 , doi : 10.1007/s00454-012-9421-9 , MR 2957636 , S2CID 25403 2514
- ^ Авис, Дэвид ; Тивари, Ханс Радж (2015), «О сложности расширения комбинаторных многогранников», Mathematical Programming , 153 (1, Ser. B): 95–115, arXiv : 1302.2340 , doi : 10.1007/s10107-014-0764-2 , МР 3395543 , S2CID 254143169
- ^ Ротвос, Томас (2017), «Соответствующий многогранник имеет экспоненциальную сложность расширения», Journal of the ACM , 64 (6): A41:1–A41:19, arXiv : 1311.2369 , doi : 10.1145/3127497 , MR 3713797 , S2CID 47045361
- ^ Априле, Мануэль; Фиорини, Сэмюэл (июль 2021 г.), «Обычные матроиды имеют полиномиальную сложность расширения», Mathematics of Operations Research , 47 : 540–559, arXiv : 1909.08539 , doi : 10.1287/moor.2021.1137 , S2CID 202660764
- ^ Бриет, Джоп; Дадуш, Дэниел; Покутта, Себастьян (2015), «О существовании многогранников 0/1 с высокой полуопределенной сложностью расширения» , Mathematical Programming , 153 (1, Сер. B): 179–199, arXiv : 1305.3268 , doi : 10.1007/s10107-014 -0785-x , MR 3395546 , S2CID 254144689
- ^ Ли, Джеймс Р.; Рагхавендра, Прасад; Стойрер, Дэвид (2015), «Нижние границы размера полуопределенных релаксаций программирования», в Серведио, Рокко А.; Рубинфельд, Ронитт (ред.), Труды сорок седьмого ежегодного симпозиума ACM по теории вычислений, STOC 2015, Портленд, Орегон, США, 14–17 июня 2015 г. , Ассоциация вычислительной техники, стр. 567–576, arXiv : 1411.6317 , doi : 10.1145/2746539.2746599 , S2CID 14438019