Fractional vertex cover number may not be feasible? Very confusing!

Question

For my project, I try to use minimum fractional vertex cover number (MFVC). (Please find below definition details) MFVC can be formulated as optimal solution of a linear program relaxation.

However I find that every linear program relaxation is either infeasible, unbounded, or has an optimum solution.

Does is mean that MFVC may not exist, or may not be a finite number, but MFVC is less or equal to minimum vertex cover number? Very confusing! :(

Many thanks!

---

Definitions:

K-uniform hypergraph:

Minimum fractional vertex cover number (MFVC): link (on page 8)

MFVC as linear programming relaxation:

The minimum fractionl vertex cover $\tau^* (G)$ in a k-uniform hypergraph $G=(V,E)$ is $\min \sum_{v\in V}w (v)$

such that $0 \le w(v) \le 1$,

and for each $e \in E$, we have $\sum_{v\in e} w(v) \ge 1$.

Answer 1

The linear program defining the minimum fractional vertex cover always has an optimal solution. The fact that some linear programs are infeasible or unbounded doesn’t mean that every linear program is infeasible or unbounded.

To give another example, sometimes you can’t divide by $x$. But if $x$ is a positive integer, then you can always divide by $x$. This in no way contradicts the fact that there exist $x$ that you can’t divide by - it just means that this complication doesn’t occur for positive integers.

To see that the minimum fractional vertex cover always exists, we have to show that the relaxation is feasible and bounded (from below). To see that it is feasible, notice that if you assign $w(v) = 1$ for all $v$, then you get a feasible solution. To see that it is bounded from below, notice that $w(v) \geq 0$ guarantees that the objective functions is always non-negative.