Jump to content

Сложность расширения

В выпуклой геометрии и многогранной комбинаторике сложность расширения многогранника выпуклого - наименьшее количество граней среди выпуклых многогранников. которые имеют как проекция. В этом контексте называется расширенной формулировкой ; оно может иметь гораздо более высокое измерение, чем . [1] [2] [3]

Сложность расширения зависит от точной формы , а не только по его комбинаторной структуре. Например, правильные многоугольники с стороны имеют сложность расширения (выражено с использованием обозначения «большое О» ), [4] [5] но какой-то другой выпуклый -угольники имеют сложность расширения, по меньшей мере пропорциональную . [5]

Если многогранник, описывающий возможные решения задачи комбинаторной оптимизации , имеет низкую сложность расширения, его потенциально можно использовать для разработки эффективных алгоритмов решения проблемы с использованием линейного программирования в его расширенной формулировке. По этой причине исследователи изучили сложность расширения возникающих таким образом многогранников. [6] Например, известно, что совпадающий многогранник имеет экспоненциальную сложность расширения. [7] С другой стороны, многогранник независимости правильных матроидов имеет полиномиальную сложность расширения. [8]

Понятие сложности расширения также было обобщено с линейного программирования на полуопределенное программирование путем рассмотрения проекций спектрэдров вместо проекций многогранников. [9] [10]

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


Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 4c3b7174340d241b0770692b917acb76__1715606340
URL1:https://arc.ask3.ru/arc/aa/4c/76/4c3b7174340d241b0770692b917acb76.html
Заголовок, (Title) документа по адресу, URL1:
Extension complexity - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)