344 reputation
14
bio website
location
age
visits member for 2 years, 5 months
seen Feb 10 at 22:53

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