Дробно-линейные задачи об упаковке и покрытии

Постановка задачи

В данной статье приводится обзор быстрых алгоритмов, дающих приближенные решения для задач, которые могут быть сформулированы в виде задач линейного программирования (LP) и, следовательно, могут быть решено точно, хотя это потребует большего времени выполнения. Общий формат семейства таких задач имеет следующий вид. Дано множество из m неравенств с n переменными и оракул, который выдает решение подходящей задачи оптимизации над выпуклым множеством [math]\displaystyle{ P \in \mathbb{R}^n }[/math]. Найти решение [math]\displaystyle{ x \in P \; }[/math], удовлетворяющее неравенствам, или определить, что такого решения x не существует. Принципиальная идея алгоритма заключается в следующем. Алгоритм всегда начинает работу с недопустимого решения x и использует оракул оптимизации для поиска направления, в котором степень нарушения неравенств может быть уменьшена; это выполняется при помощи расчета вектора y, представляющего собой решение двойственной задачи относительно x. После этого x аккуратно изменяется в этом направлении, и процесс повторяется до тех пор, пока x не становится «приближенно» допустимым. Далее будут рассмотрены конкретные задачи и соответствующие им оракулы оптимизации, а также определены другие нотации используемой «аппроксимации».

• Дробно-линейная задача об упаковке и ее оракул определяются следующим образом.

PACKING (упаковка): Даны матрица A размера [math]\displaystyle{ m \times n }[/math], b > 0 и выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math], такое, что [math]\displaystyle{ Ax \ge 0 \; \forall x \in P }[/math]. Существует ли такое [math]\displaystyle{ x \in P \; }[/math], что [math]\displaystyle{ Ax \le b \; }[/math]?

PACK_ORACLE (оракул упаковки): Даны m-мерный вектор [math]\displaystyle{ y \ge 0 \; }[/math] и вышеописанное множество P. Вернуть [math]\displaystyle{ \bar{x} := arg \; min \{ y^T Ax : x \in P \} }[/math].

• Ослабленная дробно-линейная задача об упаковке и ее оракул определяются следующим образом.

RELAXED PACKING (упаковка с ослабленными ограничениями): Даны [math]\displaystyle{ \varepsilon \gt 0 \; }[/math], матрица A размера [math]\displaystyle{ m \times n }[/math], b > 0 и выпуклые множества [math]\displaystyle{ P, \hat{P} \in \mathbb{R}^n }[/math], такие, что [math]\displaystyle{ P \subseteq \hat{P} }[/math] и [math]\displaystyle{ Ax \ge 0 \; \forall x \in P }[/math]. Найти такое [math]\displaystyle{ x \in \hat{P} }[/math], что [math]\displaystyle{ Ax \le (1 + \varepsilon)b \; }[/math], или показать, что [math]\displaystyle{ \nexists x \in P }[/math], такого, что [math]\displaystyle{ Ax \le b \; }[/math].

REL_PACK_ORACLE (оракул упаковки с ослабленными ограничениями): Даны m-мерный вектор [math]\displaystyle{ y \ge 0 \; }[/math] и вышеописанные множества [math]\displaystyle{ P, \hat{P} }[/math]. Вернуть [math]\displaystyle{ \bar{x} \in \hat{P} }[/math], такое, что [math]\displaystyle{ y^T A \bar{x} \le min \{y^T Ax : x \in P \} }[/math].

• Дробно-линейная задача о покрытии и ее оракул определяются следующим образом.

COVERING (покрытие): Даны матрица A размера [math]\displaystyle{ m \times n }[/math], b > 0 и выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math], такое, что [math]\displaystyle{ Ax \ge 0 \; \forall x \in P }[/math]. Существует ли такое [math]\displaystyle{ x \in P \; }[/math], что [math]\displaystyle{ Ax \le b \; }[/math]?

COVER _PACK_ORACLE (оракул покрытия): Даны m-мерный вектор [math]\displaystyle{ y \ge 0 \; }[/math] и вышеописанное множество P. Вернуть [math]\displaystyle{ \bar{x} := arg \; max \{ y^T Ax : x \in P \} }[/math]

• Задача об одновременных упаковке и покрытии и ее оракул определяются следующим образом.

SIMULTANEOUS PACKING AND COVERING (одновременные упаковка и покрытие): Даны матрицы [math]\displaystyle{ \hat{A} }[/math] и [math]\displaystyle{ A \; }[/math] размера [math]\displaystyle{ \hat{m} \times n }[/math] и [math]\displaystyle{ (m - \hat{m}) \times n }[/math], соответственно, [math]\displaystyle{ b \gt 0 \; }[/math] и [math]\displaystyle{ \hat{b} \gt 0 \; }[/math], а также выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math], такое, что [math]\displaystyle{ Ax \ge 0, \hat{A}x \ge 0 \; \forall x \in P }[/math]. Существует ли такое [math]\displaystyle{ x \in P \; }[/math], что [math]\displaystyle{ Ax \le b \; }[/math] и [math]\displaystyle{ \hat{A}x \ge \hat{b} }[/math]?

SIM_ORACLE (оракул упаковки и покрытия): Даны вышеописанное множество P, константа v и решение двойственной задачи [math]\displaystyle{ (y, \hat{y}) }[/math]. Вернуть [math]\displaystyle{ \bar{x} \in P }[/math], такое, что [math]\displaystyle{ A \bar{x} \le vb }[/math] и выполняется соотношение

[math]\displaystyle{ 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]\displaystyle{ Ax \le vb \} }[/math], где [math]\displaystyle{ I(v,x) := \{i : \hat{a}_i x \le v b_i \} }[/math].

• Общая задача и ее оракул определяются следующим образом.

GENERAL (общая задача): Даны матрица A размера [math]\displaystyle{ m \times n }[/math], произвольный вектор b и выпуклое множество [math]\displaystyle{ P \in \mathbb{R}^n }[/math]. Существует ли такое [math]\displaystyle{ x \in P \; }[/math], что [math]\displaystyle{ Ax \le b \; }[/math]?

GEN _ORACLE (оракул общей задачи): Даны m-мерный вектор [math]\displaystyle{ y \ge 0 \; }[/math] и вышеописанное множество P. Вернуть [math]\displaystyle{ \bar{x} := arg \; min \{ y^T Ax : x \in P \} }[/math].

Определения и нотация

Для параметра ошибки [math]\displaystyle{ \varepsilon \gt x0 \; }[/math] точка [math]\displaystyle{ x \in P \; }[/math] является [math]\displaystyle{ \varepsilon \; }[/math]-приближенным решением для дробно-линейной задачи упаковки (или покрытия), если [math]\displaystyle{ Ax \le (1 + \varepsilon) \; b }[/math] (или [math]\displaystyle{ Ax \ge (1 - \varepsilon) \; b }[/math], соответственно). С другой стороны, если [math]\displaystyle{ x \in P \; }[/math] удовлетворяет условию [math]\displaystyle{ Ax \le b \; }[/math] (или [math]\displaystyle{ Ax \ge b) \; }[/math], то x является точным решением. Для общей задачи GENERAL, параметра ошибки [math]\displaystyle{ \varepsilon \gt 0 \; }[/math] и положительного вектора отклонения d значение [math]\displaystyle{ x \in P \; }[/math] является [math]\displaystyle{ \varepsilon \; }[/math]-приближенным решением, если [math]\displaystyle{ Ax \le b + \varepsilon \; d }[/math], и точным решением, если [math]\displaystyle{ Ax \le b \; }[/math]. [math]\displaystyle{ \varepsilon \; }[/math]-ослабленная разрешающая процедура для этих задач либо находит [math]\displaystyle{ \varepsilon \; }[/math]-приближенное решение, либо обоснованно сообщает о том, что точного решения не существует. В общем случае в задаче минимизации (максимизации) алгоритм [math]\displaystyle{ (1 + \varepsilon) \; }[/math]-аппроксимации ([math]\displaystyle{ (1 - \varepsilon) \; }[/math]-аппроксимации) возвращает значение, не более чем в [math]\displaystyle{ (1 + \varepsilon) \; }[/math] (не менее чем в [math]\displaystyle{ (1 - \varepsilon) \;) }[/math] раз, соответственно) отличающееся от оптимального.

Время выполнения разработанных алгоритмов полиномиально зависит от [math]\displaystyle{ \varepsilon^{-1} \; }[/math] для любого параметра ошибки [math]\displaystyle{ \varepsilon \gt 0 \; }[/math], а также от ширины [math]\displaystyle{ \rho \; }[/math] выпуклого множества P, относящегося к множеству неравенств [math]\displaystyle{ Ax \le b \; }[/math] или [math]\displaystyle{ Ax \ge b \; }[/math], определяющему решаемую задачу. Более точно ширина [math]\displaystyle{ \rho \; }[/math] определяется следующим образом для каждой из рассматриваемых задач:

• PACKING: [math]\displaystyle{ \rho := max_i \; max_{x \in P} \frac{a_i x}{b_i} }[/math]

• RELAXED PACKING: [math]\displaystyle{ \hat{\rho} := max_i \; max_{x \in \hat{P}} \frac{a_i x}{b_i} }[/math]

• COVERING: [math]\displaystyle{ \rho := max_i \; max_{x \in P} \frac{a_i x}{b_i} }[/math]

• SIMULTANEOUS PACKING AND COVERING: [math]\displaystyle{ \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: [math]\displaystyle{ \rho := max_i \; max_{x \in P} \frac{|a_i x - b_i|}{d_i} + 1 }[/math], где d – вышеупомянутый вектор отклонения.

Основные результаты

Многие из нижеприведенных результатов были представлены в работе [7], в которой рассматривалась модель вычислений с точной арифметикой на вещественных числах и возведением в степень, выполнявшимся за один шаг. Однако, как отмечали авторы [7], эти алгоритмы могут быть преобразованы для выполнения на RAM-модели с использованием приближенной операции возведения в степень, версии оракула, выдающего почти оптимальное решение, и ограничения на количество используемых чисел, полиномиальное относительно длины входных данных и аналогичное количеству чисел, используемых в точных алгоритмах линейного программирования. Однако они оставляют открытым вопрос построения [math]\displaystyle{ \varepsilon \; }[/math]-приближенных решений, использующих полилогарифмическую точность для общего случая рассматривавшихся ими задач (что можно сделать, например, в задаче управления несколькими товарными потоками [4]).

Теорема 1. Для [math]\displaystyle{ 0 \lt \varepsilon \le 1 \; }[/math] существует детерминированная [math]\displaystyle{ \varepsilon \; }[/math]-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, использующая [math]\displaystyle{ O(\varepsilon^{-2} \rho \; log(m \varepsilon^{-1})) }[/math] вызовов оракула PACK_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.

Для случая, когда P записывается в виде произведения политопов меньшей размерности, т. е. [math]\displaystyle{ P = P^1 \times ... \times P^k }[/math], где каждый политоп [math]\displaystyle{ P^l \; }[/math] имеет ширину [math]\displaystyle{ \rho^l \; }[/math] (очевидно, что [math]\displaystyle{ \rho \le \sum_l \rho^l }[/math]), и имеется отдельный оракул PACK_ORACLE для каждого [math]\displaystyle{ P^l, A^l \; }[/math], тогда рандомизация может использоваться для потенциального ускорения работы алгоритма. Обозначив за PACK_ORACLE[math]\displaystyle{ _l }[/math] оракул для [math]\displaystyle{ P^l, A^l \; }[/math], получаем следующий результат:

Теорема 2. Для [math]\displaystyle{ 0 \lt \varepsilon \le 1 \; }[/math] существует рандомизированная [math]\displaystyle{ \varepsilon \; }[/math]-ослабленная разрешающая процедура для дробно-линейной задачи упаковки, предположительно использующая [math]\displaystyle{ O(\varepsilon^{-2} (\sum_l \rho^l) \; log(m \varepsilon^{-1}) + k \; log(\rho \varepsilon^{-1})) }[/math] вызовов оракула PACK_ORACLE[math]\displaystyle{ _l }[/math] для некоторого [math]\displaystyle{ l \in \{ 1, ..., k \} }[/math] (возможно, [math]\displaystyle{ l \; }[/math] различно для каждого вызова) плюс время, необходимое для вычисления [math]\displaystyle{ \sum_l A^l x^l \; }[/math] для текущего компонента итерации [math]\displaystyle{ x = (x^1, x^2, ... x^k) \; }[/math] между последовательными вызовами.

Теорема 2 также выполняется для задачи RELAXED PACKING, если заменить [math]\displaystyle{ \rho \; }[/math] на [math]\displaystyle{ \hat{\rho} }[/math], а PACK_ORACLE – на REL_PACK_ORACLE.

Фактически нам необходима только приближенная версия PACK_ORACLE. Пусть [math]\displaystyle{ C_{\mathcal{P}}(y) \; }[/math] – минимальная стоимость [math]\displaystyle{ y^T Ax \; }[/math], достигаемая алгоритмом PACK_ORACLE для заданного y.

Теорема 3. Заменим PACK_ORACLE на оракула, который для заданного вектора [math]\displaystyle{ y \ge 0 \; }[/math] находит точку [math]\displaystyle{ \bar{x} \in P }[/math], такую, что [math]\displaystyle{ y^T A \bar{x} \le (1 + \varepsilon/2) C_{\mathcal{P}}(y) + (\varepsilon / 2) \lambda y^T b }[/math], где [math]\displaystyle{ \lambda }[/math] – такое минимальное число, что неравенство [math]\displaystyle{ Ax \le \lambda b }[/math] удовлетворяется на текущей итерации x. Тогда теоремы 1 и 2 по-прежнему верны.

Теорема 3 говорит о том, что даже если не существует эффективной реализации оракула, как, например, в случае, когда оракул решает NP-полную задачу, достаточно будет полностью полиномиальной аппроксимационной схемы.

Схожие результаты можно доказать для дробно-линейной задачи о покрытии (COVER_ORACLE[math]\displaystyle{ _l }[/math] определяется аналогично PACK_ORACLE[math]\displaystyle{ _l }[/math]):

Теорема 4. Для [math]\displaystyle{ 0 \lt \varepsilon \lt 1 \; }[/math] существует детерминированная [math]\displaystyle{ \varepsilon }[/math]-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, использующая [math]\displaystyle{ O(m + \rho \; log^2 \; m + \varepsilon^{-2} \rho \; log(m \varepsilon^{-1})) }[/math] вызовов оракула COVER_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.

Теорема 5. Для [math]\displaystyle{ 0 \lt \varepsilon \lt 1 }[/math] существует рандомизированная [math]\displaystyle{ \varepsilon }[/math]-ослабленная разрешающая процедура для дробно-линейной задачи о покрытии, предположительно использующая [math]\displaystyle{ 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]\displaystyle{ _l }[/math] для некоторого [math]\displaystyle{ l \in \{ 1, ..., k \} }[/math] (возможно, [math]\displaystyle{ l }[/math] различно для каждого вызова) плюс время, необходимое для вычисления [math]\displaystyle{ \sum_l A^l x^l }[/math] для текущего компонента итерации [math]\displaystyle{ x = (x^1, x^2, ..., x^k) }[/math] между последовательными вызовами.

Обозначим за [math]\displaystyle{ C_C(y) }[/math] максимальную стоимость [math]\displaystyle{ y^T Ax }[/math], достигаемую алгоритмом COVER_ORACLE для заданного y.

Теорема 6. Заменим COVER_ORACLE на оракула, который для заданного вектора [math]\displaystyle{ y \ge 0 }[/math] находит точку [math]\displaystyle{ \bar{x} \in P }[/math], такую, что [math]\displaystyle{ y^T \bar{x} \ge (1 - \varepsilon/2) C_C(y) - (\varepsilon/2) \lambda y^T b }[/math], где [math]\displaystyle{ \lambda }[/math] – такое максимальное число, что неравенство [math]\displaystyle{ Ax \ge \lambda b }[/math] удовлетворяется на текущей итерации x. Тогда теоремы 4 и 5 по-прежнему верны.

Для задачи об одновременных упаковке и покрытии верно следующее:

Теорема 7. Для [math]\displaystyle{ 0 \lt \varepsilon \le 1 }[/math] существуют рандомизированная [math]\displaystyle{ \varepsilon }[/math]-ослабленная разрешающая процедура для дробно-линейной задачи об одновременных упаковке и покрытии, предположительно использующая [math]\displaystyle{ O(m^2 (log^2 \rho) \varepsilon^{-2} \; log(\varepsilon^{-1} m \; log \; \rho)) }[/math] вызовов оракула SIM_ORACLE, и детерминированная версия, использующая на [math]\displaystyle{ log \; \rho }[/math] вызовов больше, плюс время, необходимое для вычисления [math]\displaystyle{ \hat{A}x }[/math] для текущего компонента итерации x между последовательными вызовами.

Для общей задачи GENERAL верно следующее:

Теорема 8. Для [math]\displaystyle{ 0 \lt \varepsilon \lt 1 }[/math] существует детерминированная [math]\displaystyle{ \varepsilon }[/math]-ослабленная разрешающая процедура для общей задачи, использующая [math]\displaystyle{ O(\varepsilon^{-2} \rho^2 \; log(m \; \rho \; \varepsilon^{-1})) }[/math] вызовов оракула GEN_ORACLE плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами.

Время выполнения этих алгоритмов пропорционально ширине [math]\displaystyle{ \rho }[/math]; авторами статьи были разработаны техники уменьшения ширины для множества специальных случаев рассматриваемых задач. В качестве результата, полученного при помощи этих техник, можно привести следующий пример. Если задача об упаковке определяется при помощи выпуклого множества, являющегося произведением k выпуклых множеств меньших размерностей, т. е. [math]\displaystyle{ P = P^1 \times \cdot \cdot \cdot \times P^k }[/math], и неравенств [math]\displaystyle{ \sum_l A^l x^l \le b }[/math], тогда существуют рандомизированная [math]\displaystyle{ \varepsilon }[/math]-ослабленная разрешающая процедура, предположительно использующая [math]\displaystyle{ O(\varepsilon^{-2} k \; log(m \; \varepsilon^{-1}) + k \; log \; k) }[/math] вызовов подпрограммы, вычисляющей точку с минимальной стоимостью в [math]\displaystyle{ \hat{P}^l = \{ x^l \in P^l: A^l x^l \le b \}, l = 1, ..., k }[/math], и детерминированная версия процедуры, использующая [math]\displaystyle{ O(\varepsilon^{-2} \; k^2 \; log(m \; \varepsilon^{-1})) }[/math] таких вызовов плюс время, необходимое для вычисления Ax для текущего компонента итерации x между последовательными вызовами. Этот результат может быть применен к задаче управления несколькими товарными потоками, при этом указанная подпрограмма должна выполнять вычисление потоков минимальной стоимости с одним источником, а не вычисление кратчайших путей, которое требуется для исходного алгоритма.

Применение

Представленные выше результаты могут использоваться для получения быстрой аппроксимации для линейных программ, даже если эти программы могут быть решены точно при помощи LP-алгоритмов. Многие аппроксимационные алгоритмы основаны на округлении решения таких программ, так что при необходимости можно решить нужные задачи приближенно (в этом случае общий коэффициент аппроксимации поглощает коэффициент аппроксимации LP-решения), зато более эффективно. Упоминаемые здесь два примера подобного подхода были приведены в работе [7].

Теоремы 1 и 2 можно применить для улучшения времени выполнения алгоритма Ленстры, Шмойса и Тардош [5] для планирования несвязанных параллельных машин без вытеснения [math]\displaystyle{ (R||C_{max}) }[/math]. Пусть N заданий нужно спланировать для M машин, чтобы каждое задание i было включено в план ровно для одной машины j с временем обработки [math]\displaystyle{ p_{ij} }[/math], так, чтобы совокупное время обработки по всем машинам было минимальным. Тогда для любого фиксированного r > 1 существует детерминированный алгоритм (1 + r)-аппроксимации, выполняющийся за время [math]\displaystyle{ O(M^2N \; log^2 N \; log \; M) }[/math], и рандомизированная версия, выполняющаяся за ожидаемое время [math]\displaystyle{ O(M N \; log \; M \; log \; N) }[/math]. Для версии задачи с вытеснением существуют аппроксимационные схемы с полиномиальным временем выполнения, требующие [math]\displaystyle{ O(M N^2 log^2 N) }[/math] времени и [math]\displaystyle{ O(M N \; log \; N \; log \; M) }[/math] ожидаемого времени для детерминированного и рандомизированного случая, соответственно.

Для метрической задачи коммивояжера для N вершин хорошо известна граница Хельда-Карпа [2], которую можно представить как оптимум линейной программы над политопом с удалением подциклов. Используя рандомизированный алгоритм нахождения минимального разреза Каргера и Штейна [3], можно получить рандомизированную аппроксимационную схему, вычисляющую границу Хельда-Карпа за ожидаемое время [math]\displaystyle{ O(N^4 \; log^6 N) }[/math].

Открытые вопросы

Основным открытым вопросом является дальнейшее сокращение времени выполнения приближенных решений различных дробно-линейных задач. Одно потенциальное направление заключается в улучшении границ для конкретных задач, что было успешно проделано для задачи управления несколькими товарными потоками в серии статей, начатой работой Шарохи и Матулы [8]. Из той же отправной точки вышла серия результатов Григориадиса и Хачияна, независимо разработанных для [7], начиная с работы [1], в которой представлен алгоритм с числом вызовов, меньшим на коэффициент [math]\displaystyle{ 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