All Questions
Tagged with ds.algorithms linear-programming
61 questions
2
votes
0
answers
143
views
Counterexample for the 1-optimal matching algorithm in Gabow's and Tarjan's paper on scaling algorithms for networks
Context
I am reading Faster scaling algorithms for network problems by Gabow and Tarjan where I am researching part 2: "Matching and extensions". However, I am a bit confused with the ...
- 21
0
votes
1
answer
258
views
Complexity of simplex method
What is the complexity of the simplex method in terms of Big O in the general case? I saw two variants: O(2^n) and O(2^(n+m)), where n is the number of variables and m is the number of constraints
- 1
2
votes
1
answer
280
views
Characterization of integral polyhedra
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$.
Equivalently, $P$ is integral if ...
- 649
6
votes
1
answer
93
views
Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$
Let $G=(V,E)$ be graph. Recall that a cut of $G$ is (or can uniquely be identified with) a pair $(A,B)$ of nonempty subsets of $V$ which partition it. Given a cut $(A,B)$, let $E(A,B) := \{(a,b) \in ...
- 291
3
votes
1
answer
247
views
How is SDP an extension of spectral algorithms?
In one of his lectures, Uri Feige described semidefinite programming (SDP) as
... an algorithmic technique that extends both linear programming and spectral algorithms.
I know the basic ...
- 630
4
votes
1
answer
156
views
Generalizations of linear programming
Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs.
Is there a survey/lecture notes describing ...
- 630
3
votes
1
answer
223
views
On complexity of linear programming with quadratic equality/inequality constraints?
Feasibility test in Linear programming is in $P$ and in convex quadratic programming is in $P$. What is the maximum $k$ such that $n$-variable $m=poly(n)$ linear constraint feasibility test with $k$ ...
- 13.3k
-3
votes
1
answer
127
views
What is wrong with this procedure to convert quadratic programming to convex quadratic programming?
Consider the feasibility quadratic program with constraint
$$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$
$$\vdots$$
$$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$
$$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
- 13.3k
8
votes
0
answers
370
views
What exactly did Lenstra prove on mixed integer linear program?
I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
- 13.3k
6
votes
1
answer
233
views
Cases of Linear programming known to be in $NC$?
Linear programming is $P$-complete.
However are there special situations where we know an $NC$ algorithm?
- 13.3k
3
votes
1
answer
674
views
List of Pivot rules for simplex methods
Any implementation of the simplex method depends on the choice of pivot rule, which determines how the corners of the search space polyhedron are traversed. Many different have been proposed ...
- 1,163
2
votes
0
answers
266
views
Inclusion of polytopes
Consider the following two system of linear (in)eqaulities:
$S = Ax \leq b;\; Cx = e$
$T = Dx \leq d;\; Gx = g$
How can I check if $S\cap \neg T=\emptyset$ where $\neg T$ is the complement of the ...
- 253
5
votes
0
answers
125
views
LPs with "sparse solutions"
Consider a graph optimization on a graph with n vertices and m edges that can be written as an LP (like say bipartite matching). By the duality with vertex cover, we know that there's a sparse dual ...
- 32.2k
4
votes
1
answer
118
views
Polytopes convex hull
Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I ...
- 253
2
votes
1
answer
268
views
H-representation of convex hull
Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows:
$P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ ...
- 253
3
votes
0
answers
156
views
Exactly solvable but non-trivial integrality gap
Are there interesting polynomial time solvable problems that we know of for which the natural convex relaxation has a non-trivial integrality gap?
Note: Maximum matching doesn't qualify because I ...
- 7,030
0
votes
2
answers
238
views
Logic with Linear Programming
Can first-order logic be modeled/simulated as linear programming or integer programming?
What about other forms of logic (say second order)?
Update: am actually not a theory person, but more on the ...
- 749
13
votes
2
answers
32k
views
Intuitively, why is the complementary slackness condition true?
What's an intuitive proof that shows that the conditions of complementary slackness are indeed true:
If $x^*_j > 0$ then the $j$-th constraint in the dual is binding.
If the $j$-th constraint in ...
- 5,385
10
votes
1
answer
1k
views
Why is complementary slackness important?
Complementary slackness (CS) is commonly taught when talking about duality. It establishes a nice relation between the primal and the dual constraint/variables from a mathematical viewpoint.
The two ...
- 5,385
2
votes
1
answer
252
views
Literature for Generalized Load Balancing
i am looking for literature on this kind of problem.
$$
\begin{align}
\min_x \max_k &\quad \sum_{i,j} x_{ij}c_{ijk}\\
\text{subject to}&\\
&\sum_j x_{ij}=1,&& \forall i\in\mathcal ...
- 21
5
votes
0
answers
372
views
Practical algorithm for testing whether an edge is Delaunay
I have a set of vertices $V\subset\mathbb R^3$ and a set of edges $S=\{(a,b)|a,b \in V\}$. I want to know whether an edge in the set $S$ is Delaunay against the vertices in $V$.
My assumed ...
- 151
18
votes
1
answer
2k
views
Equivalence of feasibility checking and optimization for linear systems
One way to show that checking the feasibility of a linear system of inequalities is as hard as linear programming is via the reduction given by the ellipsoid method. An even easier way is to guess the ...
- 32.2k
2
votes
0
answers
81
views
General covering approximation
Consider the following integer program (general covering):
$\min c \cdot x$ subject to
$Ax \ge b$,
where all entries in $A, b, c$ are nonnegative and $x$ is required
to be nonnegative and integral.
...
- 233
3
votes
2
answers
538
views
Generalization of independent set
I know the definition of the independent set problem in graph theory. An independent set cannot contain any two adjacent vertices.
How about if you allow no more than $k$ pairs of adjacent vertices? ...
- 299
1
vote
1
answer
325
views
Approximation algorithm for graph problem
In the process of trying to create an approximation algorithm for the following problem.
Let $G = (V,E)$ be a graph, $c_e, c_{iv} \ge 0$, for $e \in E$, $i \in L$, and $v \in V$, where $L$ is a ...
- 233
4
votes
0
answers
1k
views
How to determine proper rounding in linear programming relaxations?
Recall that in the vertex cover problem we are given an undirected graph ${G=(V,E)}$ and we want to find a minimum-size set of vertices ${S}$ that “touches” all the edges of the graph, that is, such ...
- 141
3
votes
0
answers
134
views
Linear programming - How to allow cycles with weight at most s?
Consider a graph $G=(V,E)$ with nonnegative weight function on the edges $w$.
How would you express in LP that you want to allow cycles in $G$ with total weight at most $s$ ?
I've found this while ...
- 131
13
votes
1
answer
928
views
Numerical stability of Simplex method
The simplex algorithm is often treated either within real arithmetic, or in the discrete world with exact computations. However, it seems to be implemented most often with floating-point arithmetic.
...
- 1,163
3
votes
1
answer
15k
views
Difference between weak duality and strong duality?
For an optimization problem $(P)$ and its dual $(D)$, I have read about two concepts: Weak Duality, and strong Duality. What I don't understand is how they are different:
Weak duality:
If $\bar{x}$ ...
- 147
8
votes
1
answer
412
views
Motivation for Developing Shortest Path Simplex Algorithms
I'm reading Efficient Shortest Path Simplex Algorithms by Donald Goldfarb, Jianxiu Hao and Shen-Roan Kai who considered "the specialization of the primal simplex algorithm to the problem of finding a ...
- 183
-5
votes
1
answer
320
views
Solving a system of linear inequations
Consider the following system of inequalities:
$Ax=b$;
$x\geq 0$;
A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. a) How feasibility of this system can ...
- 253
14
votes
1
answer
1k
views
Does zero integrality gap imply zero duality gap for certain problems?
We know that if the gap between the values of an integer program and its dual (the "duality gap") is zero, then the linear programming relaxations of the integer program and the dual of the relaxation,...
- 779
9
votes
1
answer
643
views
Efficiently solve a system of strict linear inequalities with all coefficients equal to 1 without using a general LP solver?
Per the title, other than using a general purpose LP solver, is there an approach for solving systems of inequalities over variables $x_i, \ldots, x_k$ where inequalities have the form $\sum_{i \in I} ...
- 747
0
votes
1
answer
3k
views
Linear Programming with Modulo Linear Constraints
Given $G = (V,E)$ I can formulate a relaxation of graph $K$-coloring as:
find feasible point s.t.
$\min \sum_{ij}v_{ij}$
for all $(i,j)$ in $E$
$z_{ij} \le (c_i - c_j) \bmod k$ (i)
$z_{ij} \le (...
- 745
5
votes
0
answers
253
views
On the optimal solution of the CKR formulation for MULTIWAY CUT
Currently the best approximation algorithm for the MULTIWAY CUT problem is obtained via the linear program based on geometrical embedding by CKR [1]. Let $U_i$ be those vertices in $V-T$ which is ...
- 2,569
9
votes
2
answers
692
views
Midpoint solutions to linear programs
There is a linear program for which I want not merely a solution but a solution that's as central as possible on the face of the polytope that assumes the minimal value.
A priori, we expect the ...
- 1,226
7
votes
1
answer
245
views
Assignment problem with sum replaced by max
In the assignment problem, one tries to find $f$ such that the cost function
$$
\sum_{a\in A} C(a,f(a))
$$
is minimized. Here $f$ is a bijection between sets $A$ and $B$ of equal finite cardinality,...
- 73
2
votes
1
answer
205
views
Is there a way to solve or approximate the concave program with separable objective?
I would like to solve the following problem:
"minimize $\sum_{i=1}^k \sqrt{x_i}$ subject to some polytope constaints."
Is there a polynomial time algorithm to solve or approximate it?
Thanks.
Jian.
- 769
2
votes
1
answer
2k
views
Solve a simple system of linear inequalities in natural numbers
I want to find a solution to a system of linear inequalities of the following form
\begin{aligned}
a_1 + b &\ge a_2 \\\
\vdots \\\
a_4 + c &\ge a_1
\end{aligned}
where $a_i \in \mathbb N \...
- 37
11
votes
3
answers
518
views
Linear programming solution in one pass with ordered variables
I have a family of linear programming problems: maximise $c' x$ subject to $A x\le b$, $x\ge0$. The elements of $A$, $b$, and $c$ are nonnegative integers, $c$ strictly positive. ($x$ should also ...
- 251
10
votes
1
answer
502
views
Finding a cutting plane that splits a polyhedron evenly
Say we have a polyhedron in standard form:
\begin{equation*}
\begin{array}{rl}
\mathbf{A}\mathbf{x} = \mathbf{b} \\\\
\mathbf{x} \ge 0
\end{array}
\end{equation*}
Are there any known methods for ...
6
votes
2
answers
381
views
Inferring an LP cost vector from its solution
Say I have the following linear programming formulation in standard form:
\begin{equation*}
\begin{array}{rl}
\mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}} & \mathbf{c}^...
3
votes
1
answer
185
views
Combinatorial algorithm for optimization over semimetric polytope
This question is motivated by the Leighton-Rao relaxation for SPARSEST-CUT.
Suppose one wants to find a non-trivial semimetric over an $n$-point space that minimizes a certain linear functional. More ...
- 1,569
4
votes
1
answer
271
views
Algorithm to transform an arbitrary MIP problem into the corresponding formulation for PSO
Is there an algorithm to transform an arbitrary Mixed Integer Programming problem into the corresponding formulation for Particle Swarm Optimization? I have found some information related to the use ...
- 2,216
3
votes
1
answer
2k
views
Max-cut via linear programming or sdp
I am looking for a linear programming formulation for the max-cut problem. My interest is to know about the primal - dual algorithm for max-cut. It would be nice if someone can tell me that what is ...
- 725
31
votes
2
answers
1k
views
What classes of mathematical programs can be solved exactly or approximately, in polynomial time?
I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The ...
- 516
-1
votes
1
answer
383
views
linear programming (is this doable?) [closed]
I have the LP formulation at the link below for the following problem:
my lp formulation
Minimize:
$\sum_{i=1}^{N_1} \sum_{j=1}^{N_2} x_{ij}$
Subject to:
$\sum_{i=m}^{m+a-1} \sum_{j=n}^{n+b-1} x_{...
- 1
14
votes
5
answers
2k
views
Best book on Simplex Method implementation?
I'm interested in implementing SM for LP task, however I've heard about possible pitfalls: Cormen's book says that it is possible to have input data which will make naive implementation to behave in ...
- 551
1
vote
2
answers
904
views
Known sparse integer programming problems
I am studying the properties of sparse integer programming problems, Would like to know if there are any interesting known problems of that type ?
I would define sparse problems as problems that have ...
- 113
4
votes
2
answers
2k
views
Detecting infeasibility of System of Linear Inequalities
Infeasibility of a system of linear inequalities can be detected by using artificial variables and then using an algorithm like the simplex algorithm (or ellipsoid/interior point methods) to find a ...
- 1,311