Gabor Retvari
Reputation
364
Next privilege 500 Rep.
Access review queues
 Nov 25 comment Determine if a polyhedron is a polytope "Doing this takes $O(m^n)$." Are you sure about this? Linear programs can be solved in time that is polynomial in $m$ and $n$ (see, e.g., the ellipsoid algorithm). Nov 16 answered How to prove in a graph $G$, its incidence matrix $A$ is totally unimodular if and only if $G$ is a bipartite graph? Nov 10 revised What are the interesting applications of hyperbolic geometry? added 1 characters in body Oct 22 awarded Yearling Sep 15 comment Linear Optimization Problem - Assign Objects to People I don't believe you'll get a linear program (LP) eventually anyways. But you might be better off trying with an integer linear program (ILP) first and see if it can be simplified to an LP afterwards. Regarding the ILP, try assigning a separate 0-1 variable $x_{ij}$ to each person $i$ and each object $j$ that takes the value $1$ if person $i$ receives object $j$ and zero otherwise. From there, all your constraints (whatever they end up to be) are easy to enforce. Aug 10 comment Background of choosing standard for of a linear program as type III inequalities? Exactly who "chooses $P$ in the form $Ax\le b,x\ge 0$"? I for one always use the standard form $\min c^T x: Ax=b, x\ge 0$ as this is the formulation on which I can show the procession of the simplex method to my students most naturally. By the way, I think what you refer to is the canonical form. Aug 3 awarded Critic May 31 awarded Editor May 31 revised A basis for the cut space C* of a graph corrected typo May 31 answered A basis for the cut space C* of a graph May 11 answered primal simplex procedure Mar 5 comment Is there a name for this bipartite graph problem? In graph theory terms, the problem is called the "Hitting set problem". Feb 18 answered Linear Program feasibility Dec 24 answered What are the interesting applications of hyperbolic geometry? Dec 19 comment Multicommodity flow in polynomial size My all time favorite is Bazaraa, Jarvis, Sherali: Linear Programming and Network Flows, an extremely readable textbook on network flow theory (although a bit laconic on multicommodity flows). Dec 14 answered Multicommodity flow in polynomial size Dec 12 comment Does the sparsest cut always have a solution? Are you the same person as this guy: Graph connectivity in sparsest cut? He's asking the same question. If not, I'd like to point you to this discussion and the lecture notes therein: The flow/cut gap theorem for multicommodity flow. Dec 11 answered Does the sparsest cut always have a solution? Dec 10 answered The flow/cut gap theorem for multicommodity flow Nov 26 awarded Supporter