Skip to main content

New answers tagged

2 votes

Poly Time Algorithm for (0/1) Basic Feasible Solution

I believe you are interested in problems of the form $\min_x c^\top x$ subject to $Ax \le b$ and $x\in \{0,1\}^n$. This problem is known to be NP-hard. This means, there is strong evidence to believe ...
Lisa E.'s user avatar
  • 538
3 votes
Accepted

Maximum distance between two points of a polyhedron

The maximum distance between points in the polytope is called diameter (terminology note: ^1), or inner 1-radii (times two) [2] of the polytope $P$. A closely related problem is the norm maximization ...
pcpthm's user avatar
  • 2,727

Top 50 recent answers are included