# Questions tagged [linear-programming]

Mathematical and computational method for finding the best outcome in a given mathematical model where the list of requirements is represented as linear relationships.

207 questions
Filter by
Sorted by
Tagged with
43 views

### Greedy rounding technique

I have an assignment problem-like structure with a bunch of additional constraints formulated as an integer linear program. By relaxing the integral constraint I ended up in a relaxed LP problem for ...
67 views

1 vote
96 views

### Max-flow while restricting flow on subsets of edges to be equal

Consider a max-flow network $G(V,E,c)$. Consider disjoint subsets of the arcs $R_1,…, R_k$. I want to find the maximum $s-t$ flow such that all the edges in the $R_i$ have equal flow. Obviously, this ...
77 views

### Parallel complexity of fixed dimension fixed constraints integer programming

Papadimitriou in https://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf shows ILP is fixed parameter tractable in number of constraints and Lenstra in https://people.csail.mit....
45 views

### What is the tightest lower bound known for the integrality gap of the Gilmore–Gomory LP for Bin Packing?

I know that it has been conjectured that the Gilmore–Gomory LP for 1-D BP (also known as configuration LP) has Modified Integer Roundup Property, i.e., Opt ≤ ⌈Opt_f⌉ + 1. However, I could not find the ...
112 views

### Separation oracle for breaking cycles in directed graph

I am working on a directed graph problem and am collaterally interested to know whether there is a separation oracle for the following set of linear constraints. We are given a directed graph $G$ ...
155 views

157 views

### linear programming with non-integer constraints

Suppose we have a linear progamming about vertex packing of a hypergraph (V,E), with size $n = \sum_{e \in E} |e|$. We introduce a variable $x_v$ for each vertex $v \in V$. The fractional version is ...
95 views

### Is it possible to approximate the solution of NP-Hard problems in polynomial time using linear programming? [closed]

Suppose we have a NP-Hard problem such as the k-col, which is meant to determine if a graph may be colored using at most ...
233 views

### Minimal number of hyperplanes needed to separate sets of points from one other set

Let $\mathbb{R}^d$ be our space. We have a single good set of points $g$, and a collection of bad sets of points $B$. We assume that for all $b \in B$ the convex hulls of $g$ and $b$ are disjoint. ...
1 vote
77 views

### Time complexity of alternation free quantified linear program with no free variables and only existential quantifications

We know $\exists x\in\mathbb R^n:Ax\leq b$ is standard linear program. I am mainly looking at following case of quantified linear program with no free variables with only existential quantifications ...
1 vote