Timeline for A linear optimization problem on a graph
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2013 at 0:22 | comment | added | fedja | The life is not that simple. Take the full graph with $n$ vertices and put $f=1, w=\frac 1{2n}$ on it. Now add one isolated vertex and put $f=2, w=\frac 12-\frac 1{2n}$ on that vertex. When $n$ is large, you get about $\frac 32$ though your simple configurations cannot yield more than $1$ here. | |
| Oct 13, 2013 at 19:56 | comment | added | Pietro Majer | The other implication, the one you want, consists in the problem: Given $w\in W$ with say $0 < w_1 < 1/2$, find $u\in\mathbb{R}^n$ such that $w\pm u\in W$. This may be difficult, due to the complicated combinatorics of the family of the independent sets. | |
| Oct 13, 2013 at 19:44 | comment | added | Pietro Majer | Let $W$ be the convex polytope set of all admissible distribution of weights (that is, $w=(w_1,\dots,w_n)$ satisfying the constraints). Your question may be reformulated as: the extremal points of $W$ are exactly those of type (i) or (ii), and the zero distribution. Equivalently, $w\in W$ should be extremal iff for all $i$ there holds $w_i\in\{ 0, 1/2\}$ (the "if" part being clearly true). | |
| Oct 13, 2013 at 11:23 | comment | added | TOM | Yes, by an empty graph I mean that there are no edges. And yes, there can be many global maximums, just take $f=1$ for all $v$. That is not the point. The point is to find the simple possible among all - and I believe that the global maximum is always attained by one of the construction I described. | |
| Oct 13, 2013 at 11:20 | comment | added | joro | By "empty graph" do you mean graph with no edges but having vertices? Other constructions for global maximum are possible I believe. | |
| Oct 13, 2013 at 8:45 | history | asked | TOM | CC BY-SA 3.0 |