<p>Here is an approximate solution which is faster than LP (perhaps).
For simplicity, let's assume $U = \{1, 2, 3, ..., n\}$, $|S| = m$, $|S_i| = m_i$. Let $\mathbf{C}$ be a matrix where $C_{ji} = 1 \iff j \in S_i$. Let $\mathbf{h} = \mathbf{C} \mathbf{x}$ and your problem will be
$$
\min \parallel \mathbf{h} \parallel_{\infty} \\
\mathbf{1}^T \mathbf{x} \ge 1 \\
$$</p>

<p>Now we have $\parallel \mathbf{h} \parallel_{\infty} \le \parallel \mathbf{h} \parallel_p$ and will use the $p$-norm. To minimize $\parallel \mathbf{h} \parallel_p$ we could minimize $\parallel \mathbf{h} \parallel_p^p$.</p>

<p>Let $\lambda$ be the dual variable and from the lagrangian we get:</p>

<p>$$
L(\mathbf{x}, \lambda) = \sum_{j = 1}^{n} h_j^p + \lambda (1 - \mathbf{1}^T \mathbf{x} )
$$
and the gradient says
$$
\frac{\partial L}{\partial x_i} = p h_j^{p - 1} x_i c_{ji} -\lambda = 0.
$$</p>

<p>Solving this equation is hard. Two alternatives here:</p>

<ol>
<li>Coarse approximation: Lets assume the balancing takes place perfectly and all $h_j$ are roughly equal. Then, $x_i = c / m_i$ where we find $c$ such that $\sum_i x_i  = 1$.</li>
<li>Run a fixed point iteration: Assume some value for $\mathbf{h}$. Find $\mathbf{x}$ from above, then find $\mathbf{h}$ and so on until it converges. It might not converge for large values of $p$, but my guess is that it does for small ones.</li>
</ol>

CC BY-SA 3.0
2014-08-01T23:18:32.970Z
2014-08-01T23:18:32.970Z
Ehsan
<p>I have a problem that can be solved with linear programming, but I'm hoping there's a combinatorial algorithm for this (even approximation is fine).</p>

<p>This is basically a load balancing problem using concepts from the set cover problem. Let $U$ be the set of elements and $S$ be the set of sets whose union is $U$ (just like in set cover). Let $x_i$ be a weight associated with $s_i \in S$, where $i \ge 1$, so $x_0$ is not an actual weight. Then the LP I am solving is as follows:</p>

<p>$$
\min x_0 \\
\sum_{i:u \in s_i}x_i \le x_0 \quad \forall u \in U \\
\sum_{i \ge 1} x_i = 1 \\
x_i \ge 0
$$</p>

<p>Intuitively, I am trying to "weight" my sets such that no single element gets overloaded. I am minimizing the maximum weight of some element. The weight of an element is the sum of the weights of the sets that contain that element.</p>

CC BY-SA 3.0
2014-08-01T20:51:03.123Z
I guess an easy approximation solution is just to assign equal weight to all sets, but I'm hoping to do better than that...
rface
CC BY-SA 3.0
2014-08-01T23:39:01.180Z
If it helps, all sets $s_i$ happen to have the same size.
rface
CC BY-SA 4.0
2018-09-25T01:11:24.613Z
Check the section on "Maximum Fractional Bipartite Matching" in the answer to this question: https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388#14388 . Briefly, you have have a packing problem (packing sets under elements), which can be approximately solved by a greedy / Lagrangian-relaxation algorithm.  E.g., initialize each $x_i = 0$, maintain a weight on each element $u$ equal to $w_u(x) = (1+\epsilon)^{\sum_{i : u\in s_i} x_i}$, repeat: choose a set $s_i$ minimizing $\sum_{u\in s_i} w_u(x)$; increase $x_i$ by 1...
Neal Young
<approximation-algorithms><linear-programming><set-cover>
Combinatorial algorithm for load balancing
rface
# Combinatorial algorithm for load balancing

(Asked by: username_0 on 2014-08-01)

I have a problem that can be solved with linear programming, but I'm hoping there's a combinatorial algorithm for this (even approximation is fine).

This is basically a load balancing problem using concepts from the set cover problem. Let $U$ be the set of elements and $S$ be the set of sets whose union is $U$ (just like in set cover). Let $x\_i$ be a weight associated with $s\_i \in S$, where $i \ge 1$, so $x\_0$ is not an actual weight. Then the LP I am solving is as follows:

$$
\min x\_0 \\
\sum\_{i:u \in s\_i}x\_i \le x\_0 \quad \forall u \in U \\
\sum\_{i \ge 1} x\_i = 1 \\
x\_i \ge 0
$$

Intuitively, I am trying to "weight" my sets such that no single element gets overloaded. I am minimizing the maximum weight of some element. The weight of an element is the sum of the weights of the sets that contain that element.

**Tags:** approximation-algorithms, linear-programming, set-cover
> **Comments:**
> **username_0**: I guess an easy approximation solution is just to assign equal weight to all sets, but I'm hoping to do better than that...  
> **username_0**: If it helps, all sets $s_i$ happen to have the same size.  
> **username_1**: Check the section on "Maximum Fractional Bipartite Matching" in the answer to this question: https://cstheory.stackexchange.com/questions/4697/toy-examples-for-plotkin-shmoys-tardos-and-arora-kale-solvers/14388#14388 . Briefly, you have have a packing problem (packing sets under elements), which can be approximately solved by a greedy / Lagrangian-relaxation algorithm.  E.g., initialize each $x_i = 0$, maintain a weight on each element $u$ equal to $w_u(x) = (1+\epsilon)^{\sum_{i : u\in s_i} x_i}$, repeat: choose a set $s_i$ minimizing $\sum_{u\in s_i} w_u(x)$; increase $x_i$ by 1...  

---

## 1 answers

### Answer by username_2 on 2014-08-01. Score: 0

Here is an approximate solution which is faster than LP (perhaps).
For simplicity, let's assume $U = \{1, 2, 3, ..., n\}$, $|S| = m$, $|S\_i| = m\_i$. Let $\mathbf{C}$ be a matrix where $C\_{ji} = 1 \iff j \in S\_i$. Let $\mathbf{h} = \mathbf{C} \mathbf{x}$ and your problem will be
$$
\min \parallel \mathbf{h} \parallel\_{\infty} \\
\mathbf{1}^T \mathbf{x} \ge 1 \\
$$

Now we have $\parallel \mathbf{h} \parallel\_{\infty} \le \parallel \mathbf{h} \parallel\_p$ and will use the $p$-norm. To minimize $\parallel \mathbf{h} \parallel\_p$ we could minimize $\parallel \mathbf{h} \parallel\_p^p$.

Let $\lambda$ be the dual variable and from the lagrangian we get:

$$
L(\mathbf{x}, \lambda) = \sum\_{j = 1}^{n} h\_j^p + \lambda (1 - \mathbf{1}^T \mathbf{x} )
$$
and the gradient says
$$
\frac{\partial L}{\partial x\_i} = p h\_j^{p - 1} x\_i c\_{ji} -\lambda = 0.
$$

Solving this equation is hard. Two alternatives here:

1. Coarse approximation: Lets assume the balancing takes place perfectly and all $h\_j$ are roughly equal. Then, $x\_i = c / m\_i$ where we find $c$ such that $\sum\_i x\_i = 1$.
2. Run a fixed point iteration: Assume some value for $\mathbf{h}$. Find $\mathbf{x}$ from above, then find $\mathbf{h}$ and so on until it converges. It might not converge for large values of $p$, but my guess is that it does for small ones.


---

