Combinatorial Optimization

Combinatorial Optimization

Consider a bipartite graph (does not have to be complete) $G$ with vertex parts $A$ and $B$ of equal size, where each vertex has a preference order on its neighbors. Show that each of $A$ and $B$ can be partitioned into two parts such that one consists of vertices that is contained in all stable matchings and the other consists of vertices that is never contained in any stable matching.

by

Proof) By definition, a matching $M$ is not a stable matching iff there exists $(u,v) \in M^c \cap E$ such that $u>_v M(v)$ and $v>_u M(u)$. A matching $M$ is a stable matching iff for all $(u,v) \in M^c \cap E$, $M(u) > _v u $ or $M(u) >_u v$. Let define $M(v)$ for a … Read more

Show that the MINIMUM CUT PROBLEM is the dual program of the MAXIMUM FLOW PROBLEM

by

Show that the MINIMUM CUT PROBLEM is the dual program of the MAXIMUM FLOW PROBLEM Let $(G=(V,E), s,t,c)$ be a network. Let consider problem (4.1) maximize $\sum_{v: (s,v) \in E} f(s,v)$ with constraints $\sum_{u:(u,v) \in E} f(u,v) = \sum_{w : (v,w) \in E} f(v,w)$ for all $v \in V-\{s,t\}$, $f(u,v) \leq c(u,v)$ for all $(u,v) … Read more

Let $A$ be an $m \times n$ integer matrix. Prove that $A$ is totally unimodular if and only if for every $b \in \mathbb{Z}^n, P=\{x\in \mathbb{R}^n : Ax \leq b, x\geq 0\}$ is integer.

by

Let $A$ be an $m \times n$ integer matrix. Prove that $A$ is totally unimodular if and only if for every $b \in \mathbb{Z}^n, P=\{x\in \mathbb{R}^n : Ax \leq b, x\geq 0\}$ is integer. Lemma 3.1. Let $A$ be a square, non-singular matrix with integral entries. Then the (unique) solution of $Ax=b$ is integral for … Read more

Let $H$ be a hypergraph on a finite vertex set. Prove that $\nu^*(H)=\tau^*(H)$ where $\nu^*(H)$ is the fractional matching number and $\tau^*(H)$ is the fractional transversal number of $H$.

by

Let $H$ be a hypergraph on a finite vertex set. Prove that $\nu^*(H)=\tau^*(H)$ where $\nu^*(H)$ is the fractional matching number and $\tau^*(H)$ is the fractional transversal number of $H$. Let $H=(V,E)$ be a hypergraph where $V$ is a set of vertices and $E$ is a set of hyperedges. Let $A$ be an incidence matrix of … Read more