<p>As one of the steps in the article <a href="https://dl.acm.org/doi/abs/10.1145/1132516.1132522?casa_token=uPqDnlQeelIAAAAA:Et_b2AqlK4xOvqFJx615HxjIqFL9CkWgqQVNvNkFFUoy-H2umAKMgSsavLfjmohRSXVP2kAdisRJIg" rel="nofollow noreferrer">The Santa Claus problem</a> (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the <em>dual</em>):
<span class="math-container">\begin{align*}
&amp;\max \sum_{i=1}^m y_i - \sum_{j=1}^n z_j,\\
&amp;\text{s.t.} \quad \sum_{j\in C}z_j \geq y_i, \quad \quad \forall i,\forall C \in \mathcal{C}(i,T)\\
&amp; \quad \quad z_j \geq 0, \quad \quad \forall j.
\end{align*}</span></p>
<p>Where the variables are <span class="math-container">$y_i$</span> for <span class="math-container">$i = 1, \ldots, n$</span> and <span class="math-container">$z_j$</span> for <span class="math-container">$j = 1, \ldots m$</span>; and <span class="math-container">$\mathcal{C}(i,T)$</span> describes a set with exponential size (which contains all the valid configurations = sets-of-items, that give agent <span class="math-container">$i$</span> at least utility <span class="math-container">$T$</span>).</p>
<p>Although the number of constraints is exponential, they claim that the separation problem is a variant of knapsack, which allows them to solve the optimization problem (if I understand correctly) up to arbitrary precision using the ellipsoid method:
they explain how, for any <span class="math-container">$i$</span> and any <span class="math-container">$\mathcal{C}(i,T)$</span>, the value <span class="math-container">$\sum_{j \in C} z_j$</span> can be approximated to any wanted factor.</p>
<p>However, to my understanding, the approximate separation problem allows only an error that depends on the <em>constant</em> (rather than the variables).
That is, a constraint of the form <span class="math-container">$a\cdot x \leq b$</span> might only be approximately-maintained in the sense that
<span class="math-container">$$
a\cdot x \leq (1+\epsilon)b
$$</span>
for some <span class="math-container">$\epsilon &gt;0$</span>.</p>
<p>In their problem, the constant is 0 : each constraint (in standard form) is equivalent to
<span class="math-container">$$ y_i - \sum_{j\in C}z_j \leq 0$$</span></p>
<p>My question is - which variant of the ellipsoid method did they use that allowed this kind of error? Unfortunately, I didn't find any references in their article.</p>

CC BY-SA 4.0
2023-08-30T15:26:11.677Z
I'm not sure whether your formalization of a weak separation oracle is correct (that is, the one needed for ellipsoid).  Check e.g. https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture09.pdf .  The weak separation oracle may get by with a suitable *additive* error, rather than multiplicative.
Neal Young
CC BY-SA 4.0
2023-08-31T15:38:56.870Z
@NealYoung You are right. However, I saw some articles that managed to work with a multiplicative approximation of the LHS-variable-function of the "problematic" constraint in certain cases (mainly to approximate the optimal value of the dual). For example, karmakar and karp (https://ieeexplore.ieee.org/document/4568405) used an FPTAS for knapsack in the approximate separation for the dual to obtain an additive approximation to the primal (page 7) - but they also utilize the specific structure of the objective function.
eden hartman
CC BY-SA 4.0
2023-09-01T02:12:00.363Z
If you are using a multiplicative-weights update (i.e. Lagrangian relaxation) algorithm to approximately solve a packing and/or covering linear program, it's often possible and desirable to use an oracle that uses multiplicative error.  But in those cases all of the variables are non-negative and have positive sign in every constraint, which allows multiplicative error to work.  For these kinds of problems these algorithms can be a practical alternative to ellipsoid.
Neal Young
CC BY-SA 4.0
2023-09-01T11:58:16.530Z
@NealYoung Thank you! Are you familiar with any methods that can be used if some of the (non-negative) variables have negative sign in some of the constrants?
eden hartman
CC BY-SA 4.0
2023-09-01T13:55:29.947Z
Do you mean, other than ellipsoid?  Sort of.. you can also do additive error in some cases like that with MWU, but how it plays out (and whether it is even meaningful) tends to depend on the specific problem structure.
Neal Young
CC BY-SA 4.0
2023-09-02T15:31:04.837Z
@NealYoung Thank you!
eden hartman
CC BY-SA 4.0
2023-09-05T16:56:10.970Z
In the variant of the ellipsoid method that I know, if the approximate separation oracle does not find a violated constraint, it means that all constraints are satisfied approximately, that is, for every constraint of the form $a x\leq b$, it holds that $a x \leq (1+\epsilon)b$. But in the paper, if the approximate separation oracle does not find a violated constraint, it means that some constraints are not considered *at all* (the constraints for which the knapsack size is below the threshold), so they may not be satisfied even approximately; this is the confusing issue in that paper.
Erel Segal-Halevi
<optimization><linear-programming><gt.game-theory><oracles><convex-optimization>
Which variant of the ellipsoid method was used for the Santa Claus problem?
eden hartman
# Which variant of the ellipsoid method was used for the Santa Claus problem?

(Asked by: username_0 on 2023-08-29)

As one of the steps in the article [The Santa Claus problem](https://dl.acm.org/doi/abs/10.1145/1132516.1132522?casa_token=uPqDnlQeelIAAAAA:Et_b2AqlK4xOvqFJx615HxjIqFL9CkWgqQVNvNkFFUoy-H2umAKMgSsavLfjmohRSXVP2kAdisRJIg) (Bansal and Sviridenko, 2006) the following linear problem was considered (at the end of the second page, as the *dual*):
\begin{align\*}
&\max \sum\_{i=1}^m y\_i - \sum\_{j=1}^n z\_j,\\
&\text{s.t.} \quad \sum\_{j\in C}z\_j \geq y\_i, \quad \quad \forall i,\forall C \in \mathcal{C}(i,T)\\
& \quad \quad z\_j \geq 0, \quad \quad \forall j.
\end{align\*}

Where the variables are $y\_i$ for $i = 1, \ldots, n$ and $z\_j$ for $j = 1, \ldots m$; and $\mathcal{C}(i,T)$ describes a set with exponential size (which contains all the valid configurations = sets-of-items, that give agent $i$ at least utility $T$).

Although the number of constraints is exponential, they claim that the separation problem is a variant of knapsack, which allows them to solve the optimization problem (if I understand correctly) up to arbitrary precision using the ellipsoid method:
they explain how, for any $i$ and any $\mathcal{C}(i,T)$, the value $\sum\_{j \in C} z\_j$ can be approximated to any wanted factor.

However, to my understanding, the approximate separation problem allows only an error that depends on the *constant* (rather than the variables).
That is, a constraint of the form $a\cdot x \leq b$ might only be approximately-maintained in the sense that
$$
a\cdot x \leq (1+\epsilon)b
$$
for some $\epsilon >0$.

In their problem, the constant is 0 : each constraint (in standard form) is equivalent to
$$ y\_i - \sum\_{j\in C}z\_j \leq 0$$

My question is - which variant of the ellipsoid method did they use that allowed this kind of error? Unfortunately, I didn't find any references in their article.

**Tags:** optimization, linear-programming, gt.game-theory, oracles, convex-optimization

> **Comments:**
> **username_1**: I'm not sure whether your formalization of a weak separation oracle is correct (that is, the one needed for ellipsoid).  Check e.g. https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lecture09.pdf .  The weak separation oracle may get by with a suitable *additive* error, rather than multiplicative.  
> **username_0**: @NealYoung You are right. However, I saw some articles that managed to work with a multiplicative approximation of the LHS-variable-function of the "problematic" constraint in certain cases (mainly to approximate the optimal value of the dual). For example, karmakar and karp (https://ieeexplore.ieee.org/document/4568405) used an FPTAS for knapsack in the approximate separation for the dual to obtain an additive approximation to the primal (page 7) - but they also utilize the specific structure of the objective function.  
> **username_1**: If you are using a multiplicative-weights update (i.e. Lagrangian relaxation) algorithm to approximately solve a packing and/or covering linear program, it's often possible and desirable to use an oracle that uses multiplicative error.  But in those cases all of the variables are non-negative and have positive sign in every constraint, which allows multiplicative error to work.  For these kinds of problems these algorithms can be a practical alternative to ellipsoid.  
> **username_0**: @NealYoung Thank you! Are you familiar with any methods that can be used if some of the (non-negative) variables have negative sign in some of the constrants?  
> **username_1**: Do you mean, other than ellipsoid?  Sort of.. you can also do additive error in some cases like that with MWU, but how it plays out (and whether it is even meaningful) tends to depend on the specific problem structure.  
> **username_0**: @NealYoung Thank you!  
> **username_2**: In the variant of the ellipsoid method that I know, if the approximate separation oracle does not find a violated constraint, it means that all constraints are satisfied approximately, that is, for every constraint of the form $a x\leq b$, it holds that $a x \leq (1+\epsilon)b$. But in the paper, if the approximate separation oracle does not find a violated constraint, it means that some constraints are not considered *at all* (the constraints for which the knapsack size is below the threshold), so they may not be satisfied even approximately; this is the confusing issue in that paper.  

---

## 0 answers

