New answers tagged linear-programming
2
I think this can be solved in polynomial time by finding a minimum-cost maximum flow in the graph, where you set the capacity of each edge to $1$ and the cost of each edge $e$ to $-l(e)$, and add a source node $s_0$ with an edge $s_0 \to s$ of capacity 2 and cost 0. (You might need to add a "demand" that the edge $s_0 \to s$ has exactly 2 units of ...
1
Optimization Function: minimize $\sum_{e \in E} l(e) \cdot x_{1}(e) + \sum_{e \in E} l(e) \cdot x_{2}(e)$
Constraints: $$\sum_{(u,v) \in C} x_{1}(u,v) \geq 1 \quad \textrm{for every $(s,t)$ cut $C$ in the graph}$$
$$\sum_{(u,v) \in C} x_{2}(u,v) \geq 1 \quad \textrm{for every $(s,t)$ cut $C$ in the graph}$$
$$x_{1}(u,v) + x_{2}(u,v) \leq 1 \quad \textrm{for ...
1
The second inequality of the answer of Salah doesn't hold if $B=C$. I think the correct answer is the following two inequalities:
$$
B \geq C + 1 - M (1-A)
$$
$$
B \leq C + M A
$$
where $M$ is an upperbound on $|B-C| + 1$.
The first inequality restricts $A$ to $0$ if $B \leq C$.
For example, if $B=0$ and $C=0$, then
$$
0 \geq 0 + 1 - M(1-A) \rightarrow A = ...
0
I can not believe that below is a "fresh result" in mathematical programming ... But my rather intensive search over literature did not bring reference to any similar assertion... I will appreciate any hint to relevant references!
Recently, I understood how to represent any boolean function $f(x)$ as a system of linear inequalities in the following ...
1
Let $A = \{ i : x_i \geq 1/k \}$. By construction, $|A| \leq k \sum_i x_i \leq k \mathrm{OPT}$. The set $A$ is a set cover, since if $S_j = \{i_1,\ldots,i_\ell\}$ (where $\ell \leq k$) then $x_{i_1} + \cdots + x_{i_\ell} \geq 1$, and so $\max(x_{i_1},\ldots,x_{i_\ell}) \geq 1/\ell \geq 1/k$.
2
You can start by modeling the LP problem as in the bipartite case. Then you optimize.
If the solution found has fractional values, then, there is an odd cycle with fractional values in the subgraph induced by the solution, and you have to add the corresponding "blossom inequality constraint" to your LP model "to break" the odd cycle.
...
4
$\frac 1n$ is not a lower bound.
For example, let $n=10$.
Consider 3 set of equations (you can get equalities by considering both $a^\top v \le 1$ and $a^\top v \ge 1$):
\begin{align}
v_1 + v_2 + v_3 \qquad = 1\\
\qquad v_2 + v_3 + v_4 = 1\\
v_1 \qquad + v_3 + v_4 = 1\\
v_1 + v_2 \qquad + v_4 = 1\\
\end{align}
It's easy to check that $v_1=v_2=v_3=v_4=\frac ...
0
The claim that "increasing any single $d_u$ never forces us to decrease some other $d_v$" can be seen from the constraint $d_v \leq d_u + l_{uv}$. Here, increasing $d_u$ will not cause a violation in this particular constraint, while increasing $d_v$ would require $d_u$ to increase (not decrease) in order to keep the constraint true.
Now for the &...
1
Case 1, increase the weight. Consider a path on at least three vertices with capacity 1 for every edge. Max-flow is 1, min-cut is 1. Increase one of the edges' weight, and the max-flow will still be 1, hence the claim is false.
Case 2, let $C$ be a minimum cut with cost $w(C)$. Decrease the weight of one of the edges in $C$ to get a new minimum cost $w'(...
Top 50 recent answers are included
