Алгоритмические задачи на выпуклых множествах

Многие задачи математического программирования можно сформулировать как задачи о выпуклых множествах или выпуклых телах . Шесть видов проблем особенно важны: ^[1]^{: Раздел 2} оптимизация , нарушение , обоснованность , разделение , членство и пустота . Каждая из этих задач имеет сильный (точный) вариант и слабый (приблизительный) вариант.

Во всех описаниях задач K обозначает компактное и выпуклое множество в R ^н.

Сильные варианты

Сильные варианты проблем: ^[1]^: 47

Задача сильной оптимизации (SOPT) : задан вектор c в R ^н, найдите вектор y из K такой, что c ^Ту ≥ с ^Тx для всех x в K или утверждать, что K пуст.
Проблема сильного нарушения (SVIOL) : задан вектор c в R. ^н и число t , решите, является ли c ^Тx ≤ t для всех x в K или найдите y в K такой, что c ^Ту > т .
Проблема сильной достоверности (SVAL) : задан вектор c в R ^н и число t , решите, является ли c ^Тx ≤ t всех x в K. для
Сильная проблема непустоты (SNEMPT) : решите, пусто ли , и если нет, найдите точку в K. K
Проблема сильного разделения (SSEP) : задан вектор y в R ^н, решить, входит ли y в K , а если нет, то найти гиперплоскость , отделяющую y от K , то есть найти вектор c в R ^н такой, что с ^Ту > с ^Тx всех x в K. для
Сильная проблема принадлежности (SMEM) : задан вектор y в R. ^н, решите, находится ли y в K .

С проблемами о выпуклых множествах тесно связана следующая задача о выпуклой функции f : R ^н → Р :

Сильная неограниченная минимизация выпуклой функции (SUCFM) : найдите вектор y в R ^н такой, что f( y ) ≤ f( x ) для всех x в R ^н .

Тривиальные последствия

Из определений ясно, что алгоритмы некоторых задач можно использовать для решения других задач за оракул-полиномиальное время:

Алгоритм SOPT может решить SVIOL, проверяя, является ли c ^Ту > т;
Алгоритм SVIOL тривиально решает SVAL.
Алгоритм SVIOL может решить SNEMPT, приняв c =0 и t =-1.
Алгоритм SSEP тривиально решает SMEM.

Примеры

Разрешимость проблемы решающим образом зависит от природы K и способа его представления. Например:

Если K представлен набором некоторых m линейных неравенств, то SSEP (и, следовательно, SMEM) тривиален: задан вектор y в R ^н, мы просто проверяем, удовлетворяет ли он всем неравенствам, а если нет, возвращаем нарушенное неравенство в качестве разделяющей гиперплоскости. SOPT можно решить с помощью линейного программирования , но это не так тривиально.
Если K представлен как выпуклая оболочка некоторых m точек, то SOPT (и, следовательно, SVIOL, SVAL и SNEMPT) легко решить, вычислив цель по всем вершинам. SMEM требует проверить, существует ли вектор, представляющий собой выпуклую комбинацию вершин, что требует линейного программирования. SSEP также требует сертификат в случае отсутствия решения.
Если K представлен как надграфик некоторой вычислимой выпуклой функции , то SMEM тривиален; если субградиент можно вычислить, то SSEP тоже легко.

Слабые варианты

Каждая из вышеперечисленных задач имеет слабый вариант, в котором ответ дается лишь приближенно. Для определения аппроксимации определим следующие операции над выпуклыми множествами: ^[1]^: 6

S( K , ε ) — это шар радиуса ε вокруг K , определяемый как {x в R ^н : |ху| ≤ ε для некоторого y из K }. Неформально, точка в S( K , ε ) находится либо в K либо «почти» в K. ,
S( K , -ε ) — внутренний ε-шар кольца K , определяемый как {x в K : каждый y с |xy| ≤ ε принадлежит K }. Неформально, точка в S( K , -ε «глубоко внутри» K. )

Используя эти понятия, слабыми вариантами являются: ^[1]^: 50

Задача слабой оптимизации (WOPT) : задан вектор c в Q ^н и рациональное ε >0, либо -
- найдите вектор y в S ( K,ε ) такой, что c ^Тy + ε ≥ c ^Тx для всех x в S ( K,-ε ), или -
- утверждаем, что S ( K,-ε ) пусто.
Проблема слабого нарушения (WVIOL) : задан вектор c в Q ^н, рациональное число t и рациональное ε >0, либо -
- утверждать, что c ^Тx ≤ t + ε для всех x в S ( K,-ε ), или -
- найдите y в S ( K,ε ) такой, что c ^Ту > т - е .
Проблема слабой достоверности (WVAL) : задан вектор c в Q ^н, рациональное число t и рациональное ε >0, либо -
- утверждать, что c ^Тx ≤ t + ε для всех x в S ( K,-ε ), или -
- утверждать, что c ^Тy ≥ t-ε для некоторого y из S ( K,ε ) .
Слабая проблема непустоты (WNEMPT) : при рациональном ε > 0 либо -
- утверждать, что S(K,-ε) пусто, или —
- найдите точку y в S(K,ε) .
Проблема слабого разделения (WSEP) : задан вектор y в Q ^н и рациональное ε >0, либо -
- утверждать, что y в S ( K,ε ), или -
- найти вектор c в Q ^н (при || c || _∞ =1) такой, что c ^Ту + е > с ^Тx для всех x в S(K,-ε) .
Проблема слабой принадлежности (WMEM) : задан вектор y в Q ^н, и рациональное ε >0, либо -
- утверждать, что y в S ( K,ε ), или -
- утверждать, что y не принадлежит S ( K,-ε ). С проблемами о выпуклых множествах тесно связана следующая задача о выпуклом компакте K и выпуклой функции f : R ^н → R, заданный приблизительным значением оракула:
Минимизация выпуклой функции со слабыми ограничениями (WCCFM) : учитывая рациональное ε > 0, найдите вектор в S ( K,ε ) такой, что f( y ) ≤ f( x ) + ε для всех x в S(K,-ε) .

Тривиальные последствия

Аналогично сильным вариантам алгоритмы некоторых задач можно использовать для решения других задач за полиномиальное время оракула:

Оракул для WOPT может решить WVIOL, проверив, является ли c ^Ту + е > т ;
Оракул для WVIOL тривиально решает WVAL.
Оракул для WVIOL может решить WNEMPT, приняв c = 0 и t = -1.
Для решения WMEM можно использовать оракул для WSEP.

Более сильные слабые варианты

Некоторые из этих слабых вариантов можно немного усилить. ^[1]^{: Рем.2.1.5(а)} Например, WVAL с входными данными c , t ' = t + ε /2 и ε ' = ε /2 выполняет одно из следующих действий:

утверждать, что c ^Тx ≤ t + ε для всех x в S ( K,-ε /2), или -
утверждать, что c ^Тy ≥ t для некоторого y из S ( K,ε /2) .

Последствия слабых вариантов

Помимо этих тривиальных импликаций, существуют весьма нетривиальные импликации, доказательство которых основано на методе эллипсоидов . следствий требуют дополнительной информации о выпуклом теле K. Некоторые из этих В частности, помимо количества измерений n может потребоваться следующая информация: ^[1]^: 53

Описанный радиус R, который представляет собой радиус шара с центром в начале координат, содержащего K . Набор ( K ; n , R ) называется описанным выпуклым множеством .
Вписанный радиус r , который является радиусом шара, содержащегося в K, в случае, если K непусто. Это r обеспечивает нижнюю границу объема K. также Набор ( K ; n , R ,r) называется хорошо ограниченным выпуклым множеством .
Внутренняя точка a ₀ , которая является точкой, в которой шар радиуса r вокруг a ₀ содержится в K . Набор ( K ; n , R , r , a ₀ ) называется центрированным выпуклым множеством .

Следующее можно сделать за полиномиальное время оракула: ^[1]^{: Раздел 4}

Оракул для WSEP с описанным радиусом R может решить WVIOL. Этот алгоритм использует метод эллипсоида центрального сечения . Другой вариант — использовать другой метод, использующий симплексы вместо эллипсоидов. ^[2]
Оракул для WVIOL с описанным радиусом R может решать WOPT с помощью двоичного поиска .
Оракул для WSEP с описанным радиусом R может решить WOPT. Это следует по транзитивности из импликаций WSEP→WVIOL и WVIOL→WOPT, но существует также прямой алгоритм WSEP→WOPT, использующий технику скользящей целевой функции . ^[3]
Оракул для WMEM с R и r и 0 _. может решить WVIOL Это доказали Юдин и Немировский в 1976 г. ^[4] используя метод мелкого эллипсоида .
Оракул для WMEM с , r и 0 может _R решить WOPT. Это следует из транзитивности следствий WMEM→WVIOL и WVIOL→WOPT.
Оракул для WMEM с , r и 0 может _R решить WSEP. Это следует из транзитивности следствий WMEM→WVIOL и WVIOL→WSEP. Интересно, что для обоих шагов требуется метод эллипсоида, а прямой алгоритм WMEM→WSEP неизвестен.
Оракул для WOPT может решить WCCFM. ^[1]^: 56
- Оракул приблизительного значения для выпуклой функции можно использовать для построения оракула WMEM. Объединение этого с импликациями WMEM→WVIOL и WVIOL→WOPT и WOPT→WCCFM означает, что WCCFM на центрированном выпуклом теле ( K ; n , R , r , a ₀ ), заданном оракулом WMEM, может быть решено за полиномиальное время. ^[1]^: 113
Оракул для WOPT с помощью r можно использовать для нахождения r' и a ₀ таких, что S( a ₀ ,r') содержится в K .

Следующие импликации используют полярный набор K , определяемый как $K^{*}:=\{y\in \mathbb {R} ^{n}:y^{T}x\leq 1{\text{ for all }}x\in K\}$ . Обратите внимание, что K **= K .

Оракул для WVAL на 0-центрированном выпуклом теле (K; n,R,r,0) может решить WMEM на K *.
Оракул для WVIOL на 0-центрированном выпуклом теле (K; n,R,r,0) может решить WSEP на K *.
Оракул для WOPT может решить WSEP без какой-либо дополнительной информации. В доказательстве используются аргументы полярности.
Оракул для WVAL с описанным радиусом R может решить WSEP. В доказательстве используются аргументы полярности.

Необходимость дополнительной информации

Некоторые из вышеперечисленных выводов, очевидно, не работают без дополнительной информации. ^[1]^{: Раздел 4.5}

Оракул для WMEM или даже для SMEM с R и r , но без , ₀ не может решить WVIOL за политайм, даже для n =1 и r =1, c =1 и ε =1. Доказательство . Обратите внимание, что при данных параметрах мы знаем о K то, что K содержится в интервале [- R , R ] и содержит некоторый интервал длины 2 r =2. Предположим, что оракул SMEM отвечает «нет» на первые в R запросы членства ; это допустимая последовательность ответов, поскольку по принципу «ячейки» существует интервал длиной 2, который не содержит ни одной запрашиваемой точки. Следовательно, любому алгоритму, решающему WOPT, требуется больше, чем запросов , поэтому он экспоненциально зависит от длины кодирования R. R
Аналогично, алгоритм WMEM с R и r , но без 0 _{, не} может решить WOPT.
Оракул для WVAL с r и 0 _, но без R не может решить WVIOL.
Оракул для WVIOL с r и 0 _, но без R не может решить WOPT и WMEM.
Оракул для WMEM с r и 0 _R , но без не может решить WSEP.
Оракул для WSEP с r и 0 _, но без R , не может решить WVAL.
Оракул для WSEP с r может использоваться для получения 0 _не и, следовательно, не может использоваться для решения WOPT.
Оракул для WVIOL с r не может использоваться для получения 0 _{и, следовательно ,} не может использоваться для решения WOPT.
Оракул для WSEP с R не может использоваться для получения r.

Геометрические задачи о выпуклых телах

Используя приведенные выше основные задачи, можно решить ряд геометрических задач, связанных с выпуклыми телами. В частности, можно найти приближенный эллипсоид Джона за полиномиальное время оракула: ^[1]^{: Раздел 4.6}

Учитывая хорошо ограниченное выпуклое тело (K; n, R, r), описываемое оракулом WSEP, можно найти эллипсоид E( A , a ) такой, что $E\left({\frac {1}{n(n+1)^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$ . Алгоритм использует метод мелкого эллипсоида . Заметим, что по теореме Лоунера-Джона существует эллипсоид, удовлетворяющий более сильному соотношению $E\left({\frac {1}{n^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$ , но эта теорема не дает политаймового алгоритма.
Учитывая хорошо ограниченное центрально-симметричное выпуклое тело (K; n, R, r), описываемое оракулом WSEP, можно найти эллипсоид E( A , a ) такой, что $E\left({\frac {1}{n(n+1)}}A,a\right)\subseteq K\subseteq E(A,a)$ . Обратите внимание, что теорема Джордана доказывает, что существует эллипсоид, удовлетворяющий более сильному соотношению $E\left({\frac {1}{n}}A,a\right)\subseteq K\subseteq E(A,a)$ , но эта теорема не дает политаймового алгоритма.
Учитывая хорошо ограниченное выпуклое тело (K; n, R, r), заданное как множество решений системы линейных неравенств, можно найти эллипсоид E( A , a ) такой, что $E\left({\frac {1}{(n+1)^{2}}}A,a\right)\subseteq K\subseteq E(A,a)$ .
Учитывая хорошо ограниченное центрально-симметричное выпуклое тело (K; n, R, r), заданное как множество решений системы линейных неравенств, можно найти эллипсоид E( A , 0 ) такой, что $E\left({\frac {1}{n+1}}A,0\right)\subseteq K\subseteq E(A,0)$ .

Эти результаты означают, что любую норму можно аппроксимировать эллипсоидальной нормой . В частности, предположим, что норма N задается слабым оракулом нормы : для каждого вектора x в Q ^н и для каждого рационального ε >0 он возвращает такое рациональное число r , что |N( x )- r |< ε . Предположим, мы также знаем константу c ₁ , которая дает нижнюю границу отношения N( x ) к евклидовой норме: $c_{1}\|x\|\leq N(x)$ Тогда мы можем вычислить за полиномиальное время оракула линейное T R преобразование ^н такой, что для всех x в R ^н, $\|Tx\|\leq N(x)\leq {\sqrt {n(n+1)}}\|Tx\|$ .

возможно приблизительно определить диаметр и ширину K : Также

Учитывая хорошо ограниченное выпуклое тело ( K ; n , R , r ), описанное оракулом WSEP, его диаметр можно аппроксимировать, найдя две точки x , y в K и шар радиуса R*, содержащий K , такой, что $R^{*}\leq {\frac {1}{2}}{\sqrt {n}}\|x-y\|$ .
Учитывая хорошо ограниченное выпуклое тело ( K ; n , R , r ), описанное оракулом WSEP, его ширину можно аппроксимировать, найдя две параллельные гиперплоскости c ^Тх=d ₁ и с ^Тx=d ₂ , лежащие по обе стороны от K , и шар радиуса r*, содержащийся в K , такой, что $r^{*}={\frac {d_{2}-d_{1}}{2(n+1){\sqrt {n}}\|c\|}}$

Некоторые проблемы, еще не решенные (по состоянию на 1993 год), заключаются в том, можно ли в политайме вычислить объем, центр тяжести или площадь поверхности выпуклого тела, заданные оракулом разделения.

Задачи о комбинациях выпуклых множеств

Некоторые бинарные операции над выпуклыми множествами сохраняют алгоритмические свойства различных задач. В частности, даны два выпуклых множества K и L : ^[1]^{: Раздел 4.7}

Для суммы K+L WOPT можно решить за политайм с использованием оракулов WOPT для K и L. То же самое справедливо для WVIOL, WSEP и WVAL. Однако то же самое справедливо и для WMEM, если только K и L не являются центрированными выпуклыми телами.
Для объединения conv(K u L) результаты для суммы одинаковы: WOPT, WVIOL, WSEP и WVAL (но не WMEM) можно решить за политайм, используя соответствующие оракулы для K и L.
Для пересечения K ח L может быть невозможно вычислить внутренний радиус за политайм, поэтому нам нужно знать внутренний радиус заранее. Обладая этими знаниями, все пять задач (WMEM, WOPT, WVIOL, WSEP и WVAL) можно решить в политайм, используя соответствующие оракулы для K и L.
Учитывая оракулы WSEP для K и L и рациональное число r > 0, можно за полиномиальное время оракула вернуть либо (a) утверждение о том, что пересечение K ח L содержит шар радиуса r , либо (b) a вектор c размером 1 и число d, такое что c ^Тx ≤ d для всех x из S(K,-ε) и c ^Тx ≥ d для всех x из S(L,-ε), где ε=9nr ³(R _K /r _K + _RL /r _L ). То есть: либо в пересечении есть шар, либо существует гиперплоскость, почти отделяющая K от L.

От слабых к сильным оракулам

В некоторых случаях оракул для слабой задачи можно использовать для решения соответствующей сильной задачи.

Общие выпуклые множества

Алгоритм для WMEM, учитывая описанный радиус R , вписанный радиус r и внутреннюю точку a ₀ , может решить следующую немного более сильную проблему принадлежности (все еще слабее, чем SMEM): учитывая вектор y в Q ^ни рациональное ε >0 либо утверждать, что y входит в S ( K,ε ), либо утверждать, что y не входит в K. Доказательство элементарно и использует один вызов оракула WMEM. ^[1]^: 108

Многогранники

Предположим теперь, что K — многогранник . Затем множество оракулов для слабых задач можно использовать для решения соответствующих сильных задач за полиномиальное время оракула. Сокращения требуют верхней границы сложности представления ( сложности граней или сложности вершин ) многогранника: ^[1]^{: Сек. 6.3}

Оракул для WNEMPT, для полномерного многогранника P с ограничением сложности его представления, может решить SNEMPT.
Оракул для WOPT для ограниченного полномерного многогранника P с ограничением сложности его представления может решать SOPT.
Оракул для WVIOL, для ограниченного полномерного многогранника P с ограничением сложности его представления, может решить SVIOL.
Оракул для WVAL для ограниченного полномерного многогранника P с ограничением сложности его представления может решить SVAL.
Оракул для WSEP для ограниченного полномерного многогранника P с ограничением сложности его представления может решить SSEP.
Оракул для WMEM для ограниченного полномерного многогранника P с ограниченной сложностью его представления с учетом внутренней точки в P может решать SMEM.

В доказательствах используются результаты по одновременной диофантовой аппроксимации .

Необходимость дополнительной информации

Насколько важна дополнительная информация для вышеуказанных сокращений? ^[1]^: 173

Предположение о P полномерности является существенным: если P не полномерен, то внутренний шар S( K , -ε ) пуст. Следовательно, любой оракул для решения слабой задачи не может отличить P от пустого множества.
Предположение об ограниченности P можно ослабить: можно определить варианты слабых задач для неограниченных многогранников и доказать редукции, аналогичные приведенным выше результатам.
Для импликации WMEM→SMEM предположение о том, что внутренняя точка P, задана является существенным. Доказательство : Предположим, у нас есть многогранник P с известной сложностью вершин 2 n , и мы хотим решить, находится ли 0 P. в Если мы спросим у оракула WMEM менее 2 ^н запросы, то оракул всегда может ответить «нет», и возможно, что существует единичный куб H с вершинами, коэффициенты которых находятся в {0,+1,-1}, который содержит ноль в качестве вершины, но не содержит любую из запрошенных точек. Таким образом, возможно, что P = H и ответ «да», но также возможно, что P является выпуклой оболочкой всех ненулевых вершин H и ответ «нет». Следовательно, ни один политайм-алгоритм не может решить SMEM.

Последствия сильных вариантов

Используя предыдущие результаты, можно доказать следствия между сильными вариантами. Следующее можно сделать за полиномиальное время оракула для хорошо описанного многогранника - многогранника, для которого верхняя граница сложности представления : известна ^[1]^{: Раздел 6.4}

Оракул для SSEP может решить SNEMPT, ^[1]^{: Thm.6.4.1}
Для решения двух других можно использовать оракул для каждого SSEP, SVIOL, SOPT. ^[1]^{: Thm.6.4.9}
В частном случае, когда P является конусом, SVIOL для P совпадает с SSEP для его полярного конуса P *; следовательно, оракул SSEP для P дает алгоритм SSEP для P *.
Если мы заранее знаем, что P непусто, то оракул SSEP можно заменить немного более слабым оракулом разделения: задан вектор y из Q ^н, если y не находится в P, он находит гиперплоскость , которая отделяет y от P (= вектор c в R ^н такой, что с ^Ту > с ^Тx для всех x в P ), но если y находится в P , он все равно может вернуть гиперплоскость — вектор c в R ^н такой, что с ^Ту ≥ с ^Тx всех x в P. для

Таким образом, SSEP, SVIOL и SOPT эквивалентны полиномиальному времени. Из этой эквивалентности, в частности, следует линейное доказательство Хачиана того, что программирование можно решить за полиномиальное время: ^[1]^{: Thm.6.4.12} поскольку, когда многогранник задается явными линейными неравенствами, реализовать оракул SSEP тривиально. Более того, базовое оптимальное двойное решение также можно найти в политайме. ^[1]^{: Thm.6.5.14}

Обратите внимание, что приведенные выше теоремы не требуют предположения полномерности или нижней границы объема.

Другие сокращения не могут быть произведены без дополнительной информации:

Если P не является полномерным, то SMEM не сможет решить SSEP, SVIOL или SOPT.
Если P неограничен, то SVAL не может решить SSEP, SVIOL или SOPT.

Расширение до плохо описанных выпуклых множеств.

Джайн ^[5] распространяет одну из приведенных выше теорем на выпуклые множества, которые не являются многогранниками и недостаточно описаны. Ему требуется лишь гарантия того, что выпуклое множество содержит хотя бы одну точку (не обязательно вершину) с ограниченной длиной представления. Он доказывает, что при этом предположении SNEMPT можно решить (можно найти точку в выпуклом множестве) за политайм. ^[5]^{: Thm.12} Более того, длина представления найденной точки не более чем в P( n ) раз превышает заданную границу, где P — некоторая полиномиальная функция. ^[5]^{: Thm.13}

Геометрические задачи о многогранниках

Используя приведенные выше основные проблемы, можно решить несколько геометрических задач, связанных с непустыми многогранниками и многогранниками с ограничением сложности представления, за оракул-полиномиальное время, учитывая оракул для SSEP, SVIOL или SOPT: ^[1]^{: Раздел 6.5}

Найдите вершину P .
Учитывая вектор c , найдите вершину P , которая максимизирует c ^Тх .
Учитывая векторы c ₁ , c ₂ , найдите вершину P , которая максимизирует c ₁^Тx , и при этом максимизирует c ₂^Тx ( лексикографическая максимизация ).
Найдите оболочку аффинную P . ^[6] также подразумевает нахождение размерности P и точки внутри относительной внутренней части P. Это
Решите, являются ли какие-либо два заданных вектора вершинами P , и если да, то являются ли они смежными.
Дана точка из P , запишите ее как выпуклую комбинацию не более чем n вершин P (алгоритмическая версия теоремы Каратеодори ).

См. также

Оракул разделения разделения некоторого выпуклого множества K. — алгоритм решения задачи (слабого или сильного )

Ссылки

^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с ^т ^в Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419
^ Ямницкий, Борис; Левин, Леонид А. (1982). «Старый алгоритм линейного программирования работает за полиномиальное время» . 23-й ежегодный симпозиум по основам информатики (SFCS, 1982) . стр. 327–328. дои : 10.1109/SFCS.1982.63 . Проверено 29 января 2024 г.
^ Бланд, Роберт Г.; Гольдфарб, Дональд; Тодд, Майкл Дж. (декабрь 1981 г.). «Особенная статья — Метод эллипсоида: исследование» . Исследование операций . 29 (6): 1039–1091. дои : 10.1287/опре.29.6.1039 . ISSN 0030-364X .
^ Юдин и Немировский, 1976, https://elibrary.ru/item.asp?id=38308898 (на русском языке).
^ Перейти обратно: ^а ^б ^с Джайн, Камаль (2007). «Полиномиальный алгоритм времени для расчета рыночного равновесия Стрелы – Дебре для линейных коммунальных услуг» . SIAM Journal по вычислительной технике . 37 (1): 303–318. дои : 10.1137/S0097539705447384 . ISSN 0097-5397 .
^ Эдмондс, Дж.; Пуллибланк, WR; Ловас, Л. (1 сентября 1982 г.). «Кирпичное разложение и ранг соответствия графов» . Комбинаторика . 2 (3): 247–274. дои : 10.1007/BF02579233 . ISSN 1439-6912 . S2CID 37135635 .

[:0-1] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к ^л ^м ^н ^тот ^п ^д ^р ^с ^т ^в Гретшель, Мартин ; Ловас, Ласло ; Шрийвер, Александр (1993), Геометрические алгоритмы и комбинаторная оптимизация , Алгоритмы и комбинаторика, том. 2 (2-е изд.), Springer-Verlag, Берлин, номер номера : 10.1007/978-3-642-78240-4 , ISBN. 978-3-642-78242-8 , МР 1261419

[2] Ямницкий, Борис; Левин, Леонид А. (1982). «Старый алгоритм линейного программирования работает за полиномиальное время» . 23-й ежегодный симпозиум по основам информатики (SFCS, 1982) . стр. 327–328. дои : 10.1109/SFCS.1982.63 . Проверено 29 января 2024 г.

[3] Бланд, Роберт Г.; Гольдфарб, Дональд; Тодд, Майкл Дж. (декабрь 1981 г.). «Особенная статья — Метод эллипсоида: исследование» . Исследование операций . 29 (6): 1039–1091. дои : 10.1287/опре.29.6.1039 . ISSN 0030-364X .

[4] Юдин и Немировский, 1976, https://elibrary.ru/item.asp?id=38308898 (на русском языке).

[:1-5] Перейти обратно: ^а ^б ^с Джайн, Камаль (2007). «Полиномиальный алгоритм времени для расчета рыночного равновесия Стрелы – Дебре для линейных коммунальных услуг» . SIAM Journal по вычислительной технике . 37 (1): 303–318. дои : 10.1137/S0097539705447384 . ISSN 0097-5397 .

[6] Эдмондс, Дж.; Пуллибланк, WR; Ловас, Л. (1 сентября 1982 г.). «Кирпичное разложение и ранг соответствия графов» . Комбинаторика . 2 (3): 247–274. дои : 10.1007/BF02579233 . ISSN 1439-6912 . S2CID 37135635 .

[1]

[2]

[3]

[4]

[5]

[6]