Tagged Questions

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

learn more… | top users | synonyms

-1
votes
0answers
18 views

Solve LP-problem in standard form where the right-hand side vector depend on real variable

Suppose we have a LP-problem in standard form $\min c^T x \\ s.t. \ A x = b \,, \ x\ge 0$ where $b$ is an $1 \times 2$-matrix. Suppose we have an optimal basis $B$ corresponding to $b$ and suppose ...
0
votes
0answers
133 views

Problems which are solvable using Linear Programming

Can anyone share a link to a good survey/book about the different problem types for which we have a linear programming based solution for, as well as the related techniques?
0
votes
0answers
39 views

LP solver for sparse, PSD and strictly diagonally dominant matrix

I have a linear problem with a sparse, psd and strictly diagonally dominant matrix. Can you please point me to some known best solvers (in terms of runtime, or easy to be practically optimized for ...
0
votes
0answers
92 views

Fastest Algorithms for Determining the Nullity of a Matrix

How exactly does one go about determining the Nullity of a Matrix quicker than simply running Gaussian Elimination on the matrix itself? To be perfectly honest I can't think of a method that doesn't ...
-1
votes
1answer
44 views

Combinatorial algorithm for load balancing

I have a problem that can be solved with linear programming, but I'm hoping there's a combinatorial algorithm for this (even approximation is fine). This is basically a load balancing problem using ...
4
votes
2answers
348 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 ...
6
votes
1answer
192 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 ...
2
votes
1answer
164 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 ...
5
votes
0answers
163 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 ...
2
votes
1answer
164 views

Complexity of linear programming

It is known that Linear Programming (LP) is P-complete. I am interested in approximation algorithms for LP. There are numerous inapproximability results for NP optimization problems, e.g. it is ...
1
vote
0answers
81 views

Definition of convex optimization problem by Stephen Boyd and Lieven Vandenberghe

Boyd and Vandenberghe say that a convex optimization problem is one of the form: minimize $f_0(x)$ subject to $$f_i(x)\le 0, i=1,\ldots m$$ $$a_i^\top x=b_i, i=1,\ldots p$$ ...
0
votes
0answers
55 views

Polynomial ILP formulation of a maximum over polynomial ILP problems?

I have an optimization problem $P$ which I've polynomially reduced to three equivalent formulations: A maximum-weight maximum-cardinality bipartite matching A maximum-cost maximum-flow network An ...
3
votes
1answer
157 views

What is known about this binary representation polytope?

Consider the following set. $S_n =\{ (x,y) ~|~x \in \mathbb{Z}_+~\wedge~ y \in \{0,1\}^n ~\wedge~x=\sum_{i=0}^{n-1} 2^i y_i \}$ $S_n$ is a collection of pairs $(x,y)$, where $x$ is an integer ...
1
vote
0answers
84 views

Optimization as LP on the convex hull of its solution space

I have heard claims that for a certain class of optimization problems, one can re-write the problem as a linear-programming problem on the convex hull of the solution space of the original problem ...
-1
votes
1answer
195 views

equivalent way(s) of expressing P=?NP problem in linear programming?

the paper "In defense of the Simplex Algorithm's worst-case behavior" Disser/Skutella [1] was recently cited on this tcs.se site by saeed on another interesting question. the paper introduces the idea ...
2
votes
1answer
129 views

Proof-techniques for the hardness of optimization problems (esp. Polynomial time)

I've given an optimization problem for which I want to show that it is solvable in polynomial time. Now, I have two questions: Can this be done by formulating a mixed-integer linear program such ...
23
votes
3answers
664 views

Optimization problems with good characterization, but no polynomial-time algorithm

Consider optimization problems of the following form. Let $f(x)$ be a polynomial-time computable function that maps a string $x$ into a rational number. The optimization problem is this: what is the ...
1
vote
1answer
109 views

Feasibility of equations with max constraints

Relating to a question I posted here, I have formulated the following question: Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$. How to check the following ...
12
votes
1answer
238 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 ...
2
votes
2answers
253 views

A variant of linear programming

Consider this "variant" of linear programming: Notation: $\max\{ x_1, \cdots, x_n \}$ denotes the maximal number among $x_1, \cdots, x_n$; minimize $\sum a_i x_i$ such that $\max\{x_i\mid ...
2
votes
1answer
100 views

Testing feasibility of special linear programs

We have a linear program in the standard form $Ax=b,x\geq 0$ with $A(i,j)\in\{-1,0,1\}\:\forall\,i,j$ and $b(i)\in\{0,1\}\:\forall\,i$. $A$ is not full rank. Is the time complexity of testing the ...
24
votes
1answer
503 views

Is cubic complexity still the state of the art for LP?

According to D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994, a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ ...
3
votes
2answers
294 views

Polynomial algorithm for correlated equilibrium

I searched through the web for a polynomial algorithm for correlated equilibrium. I found a lot of papers by C.H. Papadimitriou that proposes a solution using the ellipsoid algorithm. Is there a ...
8
votes
0answers
127 views

Approximating a convex polyhedron, with fewer inequalities

I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words, ...
7
votes
2answers
265 views

what can be solved with semidefinite programming that can't be solved with linear programs?

I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programs can't? I ...
20
votes
1answer
384 views

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Precisely what the title says, I'm looking to find a polynomial time algorithm that given some set of matrices, will find if their span contains a permutation matrix. If any one knows if this ...
2
votes
1answer
192 views

Approximate Maximum Weight Matching

I am looking for an approximated (or randomized) maximum weight matching algorithm. Do you have any suggestion for me? In my problem, I have a bipartite graph with N abound 1000 (#vertices on each ...
1
vote
2answers
228 views

Applications of duality

We have recently covered linear programming and I am comfortable with the weak and strong duality theorems. However, I don't understand what the applications of duality are that are specific to TCS. ...
2
votes
0answers
97 views

Batch membership testing for convex polyhedron specified in vertex representation

I have a convex shape defined by a set of vertices (the so-called vertex representation of a convex polyhedron). I also have a large set of points and I would like to test which are contained in the ...
3
votes
0answers
227 views

Linear programming optimization problems using parallel algorithms

I'm looking for methods and algorithms for solving linear programming algorithms, characterized by up to 20 variables but up to thousands of constraints in a parallel way. There are several approaches ...
3
votes
1answer
175 views

Efficient flow problem for a complex integer program

I have a bunch of marbles each with some weight (they can also have negative weights). I want to pick the nodes such that the weight is maximized. The only rule is that if I pick X1 and X2 I have to ...
2
votes
1answer
213 views

Linear programming, a non standard handling of absolute value

This is really a basic (undergrad) question in LP but still i would like to clarify it for myself to be sure. I have a minimization problem from the sort $\min \sum_i |x_i|$ s.t $Ax \le b$. I've seen ...
0
votes
1answer
455 views

Difference between Multiple Knapsack problem and Multidimensional Knapsack Problem

What is the difference between Multiple Knapsack problem and Multidimensional Knapsack Problem? (http://en.wikipedia.org/wiki/List_of_knapsack_problems#Multiple_constraints) According to the ...
6
votes
1answer
137 views

Research about geometry negotiation in widget layout

It's very common to view GUI layout as an optimization problem. I've uncovered a lot of research around linear constraint systems, but a lot of real world layouts can not be represented linearly. For ...
2
votes
0answers
76 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. ...
3
votes
2answers
209 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? ...
1
vote
0answers
127 views

What does “no integrality gap” implies?

I'm currently working on a linear time heuristic for the rectangle decomposition of binary matrix. This problem has a polynomial time solution, which in our case it too slow for large scale ...
0
votes
1answer
250 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 ...
1
vote
1answer
96 views

Expressing a set of 0-1 strings by Extended Formulation

Extended Formulation of a polytope $P \subseteq \mathbb{R}$ is a system of linear constraints which satisfies the following condition: $x \in P \iff \exists y\in \mathbb{R}^{d} \mbox{ such that } Ax ...
1
vote
1answer
81 views

Can Lenstra's algorihtm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?

It is well-known that Lenstra's famous algorithm (presented in the paper ``integer programming with a fixed number of variables'') can solve an ILP problem in O^*(f(k)) time where k is the number of ...
4
votes
0answers
171 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 ...
5
votes
1answer
220 views

Test set and benchmarks for linear programming

I am searching for test instances and benchmarks for linear programming, in particular, when solved by a simplex method and implemented with floating-point arithmetic. This includes test suites, to ...
3
votes
0answers
120 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 ...
4
votes
2answers
883 views

Hamiltonian Cycle as an integer linear programming problem

I'm trying to do reduce Hamiltonian Cycle to integer linear programming. Here's my idea: Create variables $e_{ij}$ for every edge $(i,j)$ in the graph. Require each $$e_{ij}\in \{0,1\}$$. Create ...
8
votes
2answers
790 views

Integer programming with a fixed number of variables

The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of ...
4
votes
1answer
345 views

LP Approximation: Primal relaxation + rounding vs. Dual relaxation. Why is the latter better?

Given any Integer Linear Program (ILP) there are 2 ways to approximate it: Write down ILP, convert to LP by relaxing the integer constraints and round the solution Write down the ILP, convert to LP ...
9
votes
2answers
887 views

An intuitive/informal proof for LP Duality?

What would be a good informal/intuitive proof for 'hitting the point home' about LP duality? How best to show that the minimized objective function is indeed the minimum with an intuitive way of ...
12
votes
1answer
246 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. ...
14
votes
1answer
325 views

Is it enough for linear program constraints to be satisfied in expectation?

In the paper Randomized Primal-Dual analysis of RANKING for Online Bipartite Matching, while proving that the RANKING algorithm is $\left(1 - \frac{1}{e}\right)$-competitive, the authors show that the ...
13
votes
2answers
775 views

0-1 Linear Programming: computing the Optimal Formulation

Consider the $n$ dimensional space $\{0,1\}^n$, and let $c$ be a linear constraint of the form $a_1x_1 + a_2x_2 + a_3x_3 +\ ...\ + a_{n-1}x_{n-1} + a_nx_n \geq k$, where $a_i \in \mathbb{R}$, $x_i \in ...