Tag Info

New answers tagged linear-programming

Proof of $LP$ is in $coNP$ without showing it is in $P$?

Note: all vector inequalities in this reply are to be interpreted pointwise. Given a linear feasibility problem, you can always rewrite it in the following canonical form: given a matrix $A \in \mathbb{R}^{m \times n}$ and vector $b \in \mathbb{R}^m$, does there exist an $x \geq \vec{0}$ such that $Ax \leq b$? Farkas' lemma states that when a system of ...

cc.complexity-theory linear-programming

answered Sep 22 at 9:42

Yonatan N

1,52513 silver badges20 bronze badges

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Theorem 1. The given problem is NP-hard, by reduction from MAX-CUT. Proof. Call the given problem Positive Discrepancy Cut (PDC). Define weighted PDC to be the generalization where the input is a graph $G=(V,E)$ with polynomially bounded (possibly negative) integer edge weights, and the goal is to determine whether there is a positive-weight cut. To prove ...

ds.algorithms graph-theory graph-algorithms linear-programming enumeration

answered Sep 9 at 17:20

Neal Young

6,49924 silver badges47 bronze badges

Stack Exchange Network

current community

your communities

more stack exchange communities

Tag Info

New answers tagged linear-programming

Proof of $LP$ is in $coNP$ without showing it is in $P$?

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Tag Info

New answers tagged linear-programming

Proof of $LP$ is in $coNP$ without showing it is in $P$?

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

Related Tags