---
# System prepended metadata

title: Untitled

---

Obj: minimize $\sum_{i,r} (r + \lambda) x_{i,r}$

S.t.:

($\alpha_i$) [covering] For all $i$, $\sum_{j,r:d(i,j) \le r} x_{j,r} \ge 1$

($\beta_{i,r}$) [Min $\#$ of balls] For all $i,r$, $\sum_{(j,r'):B(j,r')\subseteq B(i,r)}x_{j,r'}(\lambda+r')\le y_{i,r}(\lambda+r)$

($\gamma_{i,r,j,r'}$) [max] For all $i,r$, $j, r'$ such that $B(j,r')\subseteq B(i,r)$, $y_{i,r} \ge x_{j,r'}$

$~$

$~$

$~$

Reshuffling:

Obj: minimize $\sum_{i,r} (r + \lambda) x_{i,r}$

S.t.:

($\alpha_i$) [covering] For all $i$, $1 \le \sum_{j,r:d(i,j) \le r} x_{j,r}$

($\beta_{i,r}$) [Min $\#$ of balls] For all $i,r$, $0 \le -\sum_{(j,r'):B(j,r')\subseteq B(i,r)}x_{j,r'}(\lambda+r') + y_{i,r}(\lambda+r)$

($\gamma_{i,r,j,r'}$) [max] For all $i,r$, $j, r'$ such that $B(j,r')\subseteq B(i,r)$, $0 \le y_{i,r} - x_{j,r'}$
$~$
$~$
$~$
$~$
DUAL:
Obj: maximize $\sum_{i} \alpha_i$
S.t.:
($x_{i,r}$) For all $i,r$, $\sum_{i'~:~d(i',i) \le r} \alpha_{i'} - \sum_{i', r' ~:~ B(i,r) \subseteq B(i',r')} \left((\lambda +r)\beta_{i',r'} + \gamma_{i,r,i',r'} \right) \le \lambda + r$

($y_{i,r}$) For all $i,r$, $(\lambda+r)\beta_{i,r}+\sum_{i',r'~:~B(i',r')\subseteq B(i,r)}\gamma_{i,r,i',r'} \le 0$


V: I agree but something is incorrect, the last constraint forces the beta and gamma to be 0.





***Second attempt***

Obj: minimize $\sum_{i,r} (r + \lambda) (x_{i,r}+\delta\cdot y_{i,r})$

S.t.:

($\alpha_i$) [covering] For all $i$, $\sum_{j,r:d(i,j) \le r} x_{j,r} \ge 1$

($\beta_{i,r}$) [Min $\#$ of balls] For all $i,r$, $\sum_{(j,r'):B(j,r')\subseteq B(i,r)}x_{j,r'}(\lambda+r')\le y_{i,r}(\lambda+r)$

($\gamma_{i,r,j,r'}$) [max] For all $i,r$, $j, r'$ such that $B(j,r')\subseteq B(i,r)$, $y_{i,r} \ge x_{j,r'}$

Reshuffling:

Obj: minimize $\sum_{i,r} (r + \lambda) (x_{i,r}+\delta\cdot y_{i,r})$

S.t.:

($\alpha_i$) [covering] For all $i$, $1 \le \sum_{j,r:d(i,j) \le r} x_{j,r}$

($\beta_{i,r}$) [Min $\#$ of balls] For all $i,r$, $0 \le -\sum_{(j,r'):B(j,r')\subseteq B(i,r)}x_{j,r'}(\lambda+r') + y_{i,r}(\lambda+r)$

($\gamma_{i,r,j,r'}$) [max] For all $i,r$, $j, r'$ such that $B(j,r')\subseteq B(i,r)$, $0 \le y_{i,r} - x_{j,r'}$
$~$
$~$
$~$
$~$
DUAL:
Obj: maximize $\sum_{i} \alpha_i$
S.t.:
($x_{i,r}$) For all $i,r$, $\sum_{i'~:~d(i',i) \le r} \alpha_{i'} - \sum_{i', r' ~:~ B(i,r) \subseteq B(i',r')} \left((\lambda +r)\beta_{i',r'} + \gamma_{i,r,i',r'} \right) \le \lambda + r$

($y_{i,r}$) For all $i,r$, $(\lambda+r)\beta_{i,r}+\sum_{i',r'~:~B(i',r')\subseteq B(i,r)}\gamma_{i,r,i',r'} \le \delta$