# Questions tagged [linear-programming]

Optimization with a linear objective function, subject to linear equality and linear inequality constraints.

318 questions
Filter by
Sorted by
Tagged with
13 views

### Randomized Assignment Problem

Given $x_1,...,x_n,y_1,...,y_n\in \mathbb{R}^d$ find a permutation matrix $P\in\mathbb{S}_d$ that minimizes $\sum_{ij}P_{ij}|x_i-y_j|$. This is an assignment problem and can be solved in $O(n^3+n^2d)$ ...
33 views

### Algorithm to cut a sphere in half with a plane and maximize the number of points on the sphere surface on one side of the plane

Consider a sphere with a coordinate system like the earth. There are $N$ points on its surface at random positions. For all the infinite planes that cuts the sphere exactly in half (i.e. the sphere's ...
31 views

### In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular

In what cases is solving Binary Linear Program easy (i.e. P complexity)? The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to ...
58 views

38 views

### How to prove that the dual linear program of the max-flow linear program indeed is a min-cut linear program?

So the wikipedia page gives the following linear programs for max-flow, and the dual program : While it is quite straight forward to see that the max-flow linear program indeed computes a maximum ...
54 views

### Question about the CLRS Linear Programming chapter

I'm currently reading the CLRS Linear Programming chapter and there is something i don't understand. The goal is to prove that given a basic set of variables, the associated slack form is unique They ...
100 views

### Minimum vertex cover algorithm with linear programming

Consider the following algorithm: given a graph $G$ with $n$ vertices, set up a linear programming problem LP where there is a variable $x_i$ for each vertex $v_i$ of $G$, each variable can take value ...
183 views

### Odd cycle transversal and linear programming

Suppose we have a graph $G$ with $n$ vertices. Suppose LP is a linear programming problem where there is a variable for each vertex of $G$, each variable can take value $≥0$, for each odd cycle of $G$ ...
111 views

### How to calculate the dimension of a convex polyhedron?

A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension ...
26 views

### Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
30 views

### Ensuring integral result from integral linear program [closed]

An integral linear program is one that has a maximizer that is integral. Sometimes it's possible to prove that a particular LP has this property, for example by proving that it's constraint matrix is ...
44 views

### In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
45 views

### Converting If-else integer equation to Linear Programming

I have an if-then-else condition with three binary variables A, B and C: if A + B = 1 then C = 0 How do I express this as an integer linear program with equality ...
30 views

### more than one min cut in a net flow

I know the answer to the question, but I still can't understand. I have the max flow and I need to determine whether there is more than one min-cut. I know that I need to run BFS from s in the ...
31 views

### Looking for fast LP solver algorithm for my Special case

I am interested to know what is the fastest algorithm (complexity wise) known to us to solve the following linear program. Due to its simplicity, I hope for a very fast algorithm. Your help is greatly ...
17 views