4430
правок
Дробно-линейные задачи об упаковке и покрытии: различия между версиями
Материал из WEGA
Дробно-линейные задачи об упаковке и покрытии (посмотреть исходный код)
Версия от 13:29, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 30 промежуточных версий этого же участника) | |||
| Строка 1: | Строка 1: | ||
== Постановка задачи == | == Постановка задачи == | ||
В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (LP) и, следовательно, могут быть решено точно, хотя это потребует большего времени выполнения. Общий формат семейства таких задач имеет следующий вид. Дано множество из m неравенств с n переменными и оракул, который выдает решение подходящей задачи оптимизации над выпуклым множеством <math>P \in \mathbb{R}^n</math>. Найти решение <math>x \in P \;</math>, удовлетворяющее неравенствам, или | В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (LP) и, следовательно, могут быть решено точно, хотя это потребует большего времени выполнения. Общий формат семейства таких задач имеет следующий вид. Дано множество из m неравенств с n переменными и оракул, который выдает решение подходящей задачи оптимизации над выпуклым множеством <math>P \in \mathbb{R}^n</math>. Найти решение <math>x \in P \;</math>, удовлетворяющее неравенствам, или определить, что такого решения x не существует. Принципиальная идея алгоритма заключается в следующем. Алгоритм всегда начинает работу с недопустимого решения x и использует оракул оптимизации для поиска направления, в котором степень нарушения неравенств может быть уменьшена; это выполняется при помощи расчета вектора y, представляющего собой ''решение двойственной задачи относительно x''. После этого x аккуратно изменяется в этом направлении, и процесс повторяется до тех пор, пока x не становится «приближенно» допустимым. Далее будут рассмотрены конкретные задачи и соответствующие им оракулы оптимизации, а также определены другие нотации используемой «аппроксимации». | ||
• '''Дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | • '''Дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | ||
PACKING (упаковка): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0 | PACKING (упаковка): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0 \; \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math>? | ||
PACK_ORACLE (оракул упаковки): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; min \{ y^T Ax : x \in P \}</math>. | PACK_ORACLE (оракул упаковки): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; min \{ y^T Ax : x \in P \}</math>. | ||
| Строка 12: | Строка 12: | ||
• '''Ослабленная дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | • '''Ослабленная дробно-линейная задача об упаковке''' и ее оракул определяются следующим образом. | ||
RELAXED PACKING (упаковка с ослабленными ограничениями): Даны <math>\varepsilon > 0 \;</math>, матрица A размера <math>m \times n</math>, b > 0 и выпуклые множества <math>P | RELAXED PACKING (упаковка с ослабленными ограничениями): Даны <math>\varepsilon > 0 \;</math>, матрица A размера <math>m \times n</math>, b > 0 и выпуклые множества <math>P, \hat{P} \in \mathbb{R}^n</math>, такие, что <math>P \subseteq \hat{P}</math> и <math>Ax \ge 0 \; \forall x \in P</math>. Найти такое <math>x \in \hat{P}</math>, что <math>Ax \le (1 + \varepsilon)b \;</math>, или показать, что <math>\nexists x \in P</math>, такого, что <math>Ax \le b \;</math>. | ||
REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанные множества <math>P, \hat{P}</math>. Вернуть <math>\bar{x} \in \hat{P}</math>, такое, что <math>y^T | REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанные множества <math>P, \hat{P}</math>. Вернуть <math>\bar{x} \in \hat{P}</math>, такое, что <math>y^T A \bar{x} \le min \{y^T Ax : x \in P \}</math>. | ||
• '''Дробно-линейная задача о покрытии''' и ее оракул определяются следующим образом. | • '''Дробно-линейная задача о покрытии''' и ее оракул определяются следующим образом. | ||
COVERING (покрытие): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0 | COVERING (покрытие): Даны матрица A размера <math>m \times n</math>, b > 0 и выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0 \; \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math>? | ||
COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; max \{ y^T Ax : x \in P \}</math> | COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор <math>y \ge 0 \;</math> и вышеописанное множество P. Вернуть <math>\bar{x} := arg \; max \{ y^T Ax : x \in P \}</math> | ||
| Строка 27: | Строка 27: | ||
• '''Задача об одновременных упаковке и покрытии''' и ее оракул определяются следующим образом. | • '''Задача об одновременных упаковке и покрытии''' и ее оракул определяются следующим образом. | ||
SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы <math>\hat{A}</math> и <math>A \;</math> размера <math>\hat{m} \times n</math> и <math>(m - \hat{m}) \times n</math>, соответственно, <math>b > 0 \;</math> и <math>\hat{b} > 0 \;</math>, а также выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \hat{A}x \ge 0 | SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы <math>\hat{A}</math> и <math>A \;</math> размера <math>\hat{m} \times n</math> и <math>(m - \hat{m}) \times n</math>, соответственно, <math>b > 0 \;</math> и <math>\hat{b} > 0 \;</math>, а также выпуклое множество <math>P \in \mathbb{R}^n</math>, такое, что <math>Ax \ge 0, \hat{A}x \ge 0 \; \forall x \in P</math>. Существует ли такое <math>x \in P \;</math>, что <math>Ax \le b \;</math> и <math>\hat{A}x \ge \hat{b}</math>? | ||
SIM_ORACLE (оракул упаковки и покрытия): Даны вышеописанное множество P, константа v и решение двойственной задачи <math>(y, \hat{y})</math>. Вернуть <math>\bar{x} \in P</math>, такое, что <math>A \bar{x} \le vb</math> и выполняется соотношение | |||
<math>y^T A \bar{x} - \sum_{i \in I(v, \bar{x})} \hat{y}_i \hat{a}_i \bar{x} = min \{ y^T Ax - \sum_{i \in I(v, x)} \hat{y}_i \hat{a}_i x</math> : x является вершиной P, такой, что <math>Ax \le vb \}</math>, где <math>I(v,x) := \{i : \hat{a}_i x \le v b_i \}</math>. | <math>y^T A \bar{x} - \sum_{i \in I(v, \bar{x})} \hat{y}_i \hat{a}_i \bar{x} = min \{ y^T Ax - \sum_{i \in I(v, x)} \hat{y}_i \hat{a}_i x</math> : x является вершиной P, такой, что <math>Ax \le vb \}</math>, где <math>I(v,x) := \{i : \hat{a}_i x \le v b_i \}</math>. | ||
| Строка 42: | Строка 43: | ||
'''Определения и нотация''' | '''Определения и нотация''' | ||
Для параметра ошибки | |||
Для параметра ошибки <math>\varepsilon > x0 \;</math> точка <math>x \in P \;</math> является <math>\varepsilon \;</math>-''приближенным решением'' для дробно-линейной задачи упаковки (или покрытия), если <math>Ax \le (1 + \varepsilon) \; b</math> (или <math>Ax \ge (1 - \varepsilon) \; b</math>, соответственно). С другой стороны, если <math>x \in P \;</math> удовлетворяет условию <math>Ax \le b \;</math> (или <math>Ax \ge b) \;</math>, то x ''является точным решением''. Для общей задачи GENERAL, параметра ошибки <math>\varepsilon > 0 \;</math> и положительного вектора отклонения d значение <math>x \in P \;</math> является <math>\varepsilon \;</math>-''приближенным решением'', если <math>Ax \le b + \varepsilon \; d</math>, и ''точным решением'', если <math>Ax \le b \;</math>. <math>\varepsilon \;</math>-''ослабленная разрешающая процедура'' для этих задач либо находит <math>\varepsilon \;</math>-приближенное решение, либо обоснованно сообщает о том, что точного решения не существует. В общем случае в задаче минимизации (максимизации) ''алгоритм'' <math>(1 + \varepsilon) \;</math>-''аппроксимации'' (<math>(1 - \varepsilon) \;</math>-аппроксимации) возвращает значение, не более чем в <math>(1 + \varepsilon) \;</math> (не менее чем в <math>(1 - \varepsilon) \;)</math> раз, соответственно) отличающееся от оптимального. | |||
Время выполнения разработанных алгоритмов полиномиально зависит от | Время выполнения разработанных алгоритмов полиномиально зависит от <math>\varepsilon^{-1} \;</math> для любого параметра ошибки <math>\varepsilon > 0 \;</math>, а также от ''ширины'' <math>\rho \;</math> выпуклого множества P, относящегося к множеству неравенств <math>Ax \le b \;</math> или <math>Ax \ge b \;</math>, определяющему решаемую задачу. Более точно ширина <math>\rho \;</math> определяется следующим образом для каждой из рассматриваемых задач: | ||
• PACKING | • PACKING: <math>\rho := max_i \; max_{x \in P} \frac{a_i x}{b_i}</math> | ||
• RELAXED PACKING | • RELAXED PACKING: <math>\hat{\rho} := max_i \; max_{x \in \hat{P}} \frac{a_i x}{b_i}</math> | ||
• COVERING | • COVERING: <math>\rho := max_i \; max_{x \in P} \frac{a_i x}{b_i}</math> | ||
• SIMULTANEOUS PACKING AND COVERING | • SIMULTANEOUS PACKING AND COVERING: <math>\rho := max_{x \in P} \; max \{ max_i \frac{a_i x}{b_i}, max_i \frac{\hat{a}_i x}{\hat{b}_i} \}</math> | ||
• GENERAL | • GENERAL: <math>\rho := max_i \; max_{x \in P} \frac{|a_i x - b_i|}{d_i} + 1</math>, где d – вышеупомянутый вектор отклонения. | ||
== Основные результаты == | == Основные результаты == | ||
Многие из нижеприведенных результатов были представлены в работе [7], в которой рассматривалась модель вычислений с точной арифметикой на вещественных числах и возведением в степень, выполнявшимся за один шаг. Однако, как отмечали авторы [7], эти алгоритмы могут быть преобразованы для выполнения на RAM-модели с использованием приближенной операции возведения в степень, версии оракула, выдающего ''почти'' оптимальное решение, и ограничения на количество используемых чисел, полиномиальное относительно длины входных данных и аналогичное количеству чисел, используемых в точных алгоритмах линейного программирования. Однако они оставляют открытым вопрос построения <math>\varepsilon \;</math>-приближенных решений, использующих полилогарифмическую точность для общего случая рассматривавшихся ими задач (что можно сделать, например, в задаче управления несколькими товарными потоками [4]). | |||
'''Теорема 1. Для <math>0 < \varepsilon \le 1 \;</math> существует детерминированная <math>\varepsilon \;</math>-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, использующая <math>O(\varepsilon^{-2} \rho \; log(m \varepsilon^{-1}))</math> вызовов оракула PACK_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.''' | |||
Для случая, когда P записывается в виде произведения политопов меньшей размерности, т. е. <math>P = P^1 \times ... \times P^k</math>, где каждый политоп <math>P^l \;</math> имеет ширину <math>\rho^l \;</math> (очевидно, что <math>\rho \le \sum_l \rho^l</math>), и имеется отдельный оракул PACK_ORACLE для каждого <math>P^l, A^l \;</math>, тогда рандомизация может использоваться для потенциального ускорения работы алгоритма. Обозначив за PACK_ORACLE<math>_l</math> оракул для <math>P^l, A^l \;</math>, получаем следующий результат: | |||
'''Теорема 2. Для <math>0 < \varepsilon \le 1 \;</math> существует рандомизированная <math>\varepsilon \;</math>-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, предположительно использующая <math>O(\varepsilon^{-2} (\sum_l \rho^l) \; log(m \varepsilon^{-1}) + k \; log(\rho \varepsilon^{-1}))</math> вызовов оракула PACK_ORACLE<math>_l</math> для некоторого <math>l \in \{ 1, ..., k \}</math> (возможно, <math>l \;</math> различно для каждого вызова) плюс время, необходимое для вычисления <math>\sum_l A^l x^l \;</math> для текущего компонента итерации <math>x = (x^1, x^2, ... x^k) \;</math> между последовательными вызовами.''' | |||
Теорема 2 также выполняется для задачи RELAXED PACKING, если заменить <math>\rho \;</math> на <math>\hat{\rho}</math>, а PACK_ORACLE – на REL_PACK_ORACLE. | |||
Фактически нам необходима только ''приближенная'' версия PACK_ORACLE. Пусть <math>C_{\mathcal{P}}(y) \;</math> – минимальная стоимость <math>y^T Ax \;</math>, достигаемая алгоритмом PACK_ORACLE для заданного y. | |||
'''Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора <math>y \ge 0 \;</math> находит точку <math>\bar{x} \in P</math>, такую, что <math>y^T A \bar{x} \le (1 + \varepsilon/2) C_{\mathcal{P}}(y) + (\varepsilon / 2) \lambda y^T b</math>, где <math>\lambda</math> – такое минимальное число, что неравенство <math>Ax \le \lambda b</math> удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны.''' | |||
Теорема 3 говорит о том, что даже если не существует эффективной реализации оракула, как, например, в случае, когда оракул решает NP-полную задачу, достаточно будет полностью полиномиальной аппроксимационной схемы. | |||
Схожие результаты можно доказать для дробно-линейной задачи о покрытии (COVER_ORACLE<math>_l</math> определяется аналогично PACK_ORACLE<math>_l</math>): | |||
'''Теорема 4. Для <math>0 < \varepsilon < 1 \;</math> существует детерминированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, использующая <math>O(m + \rho \; log^2 \; m + \varepsilon^{-2} \rho \; log(m \varepsilon^{-1}))</math> вызовов оракула COVER_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.''' | |||
'''Теорема 5. Для <math>0 < \varepsilon < 1</math> существует рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, предположительно использующая <math>O(mk + (\sum_l \rho^l)log^2 m + k \; log \varepsilon^{-1} + \varepsilon^{-2} (\sum_l \rho^l) log(m \varepsilon^{-1}))</math> вызовов оракула COVER_ORACLE<math>_l</math> для некоторого <math>l \in \{ 1, ..., k \}</math> (возможно, <math>l</math> различно для каждого вызова) плюс время, необходимое для вычисления <math>\sum_l A^l x^l</math> для текущего компонента итерации <math>x = (x^1, x^2, ..., x^k)</math> между последовательными вызовами.''' | |||
Обозначим за <math>C_C(y)</math> максимальную стоимость <math>y^T Ax</math>, достигаемую алгоритмом COVER_ORACLE для заданного y. | |||
'''Теорема 6. Заменим COVER_ORACLE на оракула, который для заданного вектора <math>y \ge 0</math> находит точку <math>\bar{x} \in P</math>, такую, что <math>y^T \bar{x} \ge (1 - \varepsilon/2) C_C(y) - (\varepsilon/2) \lambda y^T b</math>, где <math>\lambda</math> – такое максимальное число, что неравенство <math>Ax \ge \lambda b</math> удовлетворяется на текущей итерации x. Тогда теоремы 4 и 5 по-прежнему верны.''' | |||
Для задачи об одновременных упаковке и покрытии верно следующее: | |||
'''Теорема 7. Для <math>0 < \varepsilon \le 1</math> существуют рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура для дробно-линейной задачи об одновременных упаковке и покрытии, предположительно использующая <math>O(m^2 (log^2 \rho) \varepsilon^{-2} \; log(\varepsilon^{-1} m \; log \; \rho))</math> вызовов оракула SIM_ORACLE, и детерминированная версия, использующая на <math>log \; \rho</math> вызовов больше, плюс время, необходимое для вычисления <math>\hat{A}x</math> для текущего компонента итерации x между последовательными вызовами.''' | |||
Для общей задачи GENERAL верно следующее: | |||
'''Теорема 8. Для <math>0 < \varepsilon < 1</math> существует детерминированная <math>\varepsilon</math>-ослабленная разрешающая процедура для общей задачи, использующая <math>O(\varepsilon^{-2} \rho^2 \; log(m \; \rho \; \varepsilon^{-1}))</math> вызовов оракула GEN_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.''' | |||
Время выполнения этих алгоритмов пропорционально ширине <math>\rho</math>; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т. е. <math>P = P^1 \times \cdot \cdot \cdot \times P^k</math>, и неравенств <math>\sum_l A^l x^l \le b</math>, тогда существуют рандомизированная <math>\varepsilon</math>-ослабленная разрешающая процедура, предположительно использующая <math>O(\varepsilon^{-2} k \; log(m \; \varepsilon^{-1}) + k \; log \; k)</math> вызовов подпрограммы, вычисляющей точку с минимальной стоимостью в <math>\hat{P}^l = \{ x^l \in P^l: A^l x^l \le b \}, l = 1, ..., k</math>, и детерминированная версия процедуры, использующая <math>O(\varepsilon^{-2} \; k^2 \; log(m \; \varepsilon^{-1}))</math> таких вызовов плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма. | |||
== Применение == | |||
Представленные выше результаты могут использоваться для получения быстрой аппроксимации для линейных программ, даже если эти программы могут быть решены точно при помощи LP-алгоритмов. Многие аппроксимационные алгоритмы основаны на округлении решения таких программ, так что при необходимости можно решить нужные задачи приближенно (в этом случае общий коэффициент аппроксимации поглощает коэффициент аппроксимации LP-решения), зато более эффективно. Упоминаемые здесь два примера подобного подхода были приведены в работе [7]. | |||
Теоремы 1 и 2 можно применить для улучшения времени выполнения алгоритма Ленстры, Шмойса и Тардош [5] для планирования несвязанных параллельных машин без вытеснения <math>(R||C_{max})</math>. Пусть N заданий нужно спланировать для M машин, чтобы каждое задание i было включено в план ровно для одной машины j с временем обработки <math>p_{ij}</math>, так, чтобы совокупное время обработки по всем машинам было минимальным. Тогда для любого фиксированного r > 1 существует детерминированный алгоритм (1 + r)-аппроксимации, выполняющийся за время <math>O(M^2N \; log^2 N \; log \; M)</math>, и рандомизированная версия, выполняющаяся за ожидаемое время <math>O(M N \; log \; M \; log \; N)</math>. Для версии задачи с вытеснением существуют аппроксимационные схемы с полиномиальным временем выполнения, требующие <math>O(M N^2 log^2 N)</math> времени и <math>O(M N \; log \; N \; log \; M)</math> ожидаемого времени для детерминированного и рандомизированного случая, соответственно. | |||
Для [[Метрическая задача коммивояжера|метрической задачи коммивояжера]] для N вершин хорошо известна граница Хельда-Карпа [2], которую можно представить как оптимум линейной программы над ''политопом с удалением подциклов''. Используя рандомизированный алгоритм нахождения минимального разреза Каргера и Штейна [3], можно получить рандомизированную аппроксимационную схему, вычисляющую границу Хельда-Карпа за ожидаемое время <math>O(N^4 \; log^6 N)</math>. | |||
== Открытые вопросы == | |||
Основным открытым вопросом является дальнейшее сокращение времени выполнения приближенных решений различных дробно-линейных задач. Одно потенциальное направление заключается в улучшении границ для конкретных задач, что было успешно проделано для задачи управления несколькими товарными потоками в серии статей, начатой работой Шарохи и Матулы [8]. Из той же отправной точки вышла серия результатов Григориадиса и Хачияна, независимо разработанных для [7], начиная с работы [1], в которой представлен алгоритм с числом вызовов, меньшим на коэффициент <math>log(m \varepsilon^{-1})/log \; m</math> по сравнению с теоремой 1. Значительные усилия были направлены на сокращение зависимости времени выполнения от ширины задачи или на уменьшение самой ширины (см, например, последовательные и параллельные алгоритмы для смешанной задачи упаковки и покрытия в [9]), так что это тоже может быть перспективным направлением для улучшения. | |||
Остается открытой задача из [7] по разработке аппроксимационных схем для модели RAM, использующих только ''полилогарифмические по длине входных данных'' точность и работу для общего случая рассматриваемых задач. | |||
== См. также == | |||
* [[Минимальный период обработки на несвязанных машинах]] | |||
== Литература == | |||
1. Grigoriadis, M.D., Khachiyan, L.G.: Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. Optim. 4,86-107 (1994) | |||
2. Held, M., Karp, R.M.: The traveling-salesman problem and minimum cost spanning trees. Oper. Res. 18,1138-1162 (1970) | |||
3. Karger, D.R., Stein, C.: An 6(n2) algorithm for minimum cut. In: Proceeding of 25th Annual ACM Symposium on Theory of Computing (STOC), 1993, pp. 757-765 | |||
4. Leighton, F.T., Makedon, F., Plotkin, S.A., Stein, C., Tardos, Ё., Tragoudas, S.: Fast approximation algorithms for multicommodity flow problems. J. Comp. Syst. Sci. 50(2), 228-243 (1995) | |||
5. Lenstra, J.K., Shmoys, D.B., Tardos, Ё.: Approximation algorithms for scheduling unrelated parallel machines. Math. Program. Ser. A 24, 259-272 (1990) | |||
6. Plotkin, S.A., Shmoys, D.B., Tardos, Ё.: Fast approximation algorithms for fractional packing and covering problems. In: Proceedings of 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1991, pp.495-504 | |||
7. Plotkin, S.A., Shmoys, D.B., Tardos, Ё.: Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2) 257-301 (1995). Preliminary version appeared in [6] | |||
8. Shahrokhi, F., Matula, D.W.: The maximum concurrent flow problem. J. ACM 37, 318-334(1990) | |||
9. Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: Proceedings of 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2001, pp.538-546 | |||
