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

0
votes
0answers
33 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
84 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
40 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
203 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
185 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
157 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
162 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
162 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
78 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
47 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
154 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
82 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
177 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
128 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 ...
21
votes
3answers
629 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
106 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
224 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
250 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
98 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
0answers
396 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
282 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
122 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
250 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
380 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
168 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
220 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
95 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
202 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
201 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
379 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
133 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
75 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
191 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
248 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
94 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
76 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
162 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
185 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
119 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
802 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
693 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
336 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
698 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
239 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
311 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
739 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 ...
4
votes
0answers
107 views

LP-type vs. Approximation

I'm interested in an computational geometry problem that's sensibly expressed as an infinite dimensional 0-1 integer program. I'm not worried about finding an actual minimum for the objective ...
11
votes
1answer
373 views

Solving semidefinite programs in polynomial time

We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial ...