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
vote
0answers
57 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 ...
-3
votes
0answers
26 views

Existence of Integer solution for a set of linear equations [migrated]

Can anyone give a proof sketch of the following claim: If a system of homogeneous linear equations with integer coefficients has a positive real solution, then it also has a positive integer solution? ...
-1
votes
1answer
154 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
120 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
591 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
100 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 ...
11
votes
1answer
207 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
244 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
94 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 ...
15
votes
0answers
246 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
275 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 ...
9
votes
0answers
112 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
230 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
367 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
145 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
202 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
94 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
159 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
169 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
187 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
305 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
126 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
69 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
189 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
123 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
243 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
92 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
74 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
139 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
156 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
115 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 ...
3
votes
2answers
674 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
593 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
319 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 ...
8
votes
2answers
561 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 ...
7
votes
0answers
143 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
303 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
697 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
102 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 ...
10
votes
1answer
333 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 ...
1
vote
1answer
455 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}$ ...
8
votes
1answer
255 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 ...
5
votes
2answers
455 views

How/Why are linear systems so crucial to computer science?

I've begun to get involved with Mathematical Optimization quite recently and am loving it. It seems a lot of optimization problems can be easily expressed and solved as linear programs (e.g. network ...
2
votes
2answers
541 views

Compute Nash Equilibrium for 2-player games

I want to compute a mixed strategy that will be the Nash Equilibrium of the game. I have used my knowledge in order to create the system for the mixed strategy. I concluded on a system with 3 ...
4
votes
0answers
516 views

Can the Hungarian method be used with real edge weights?

I had a problem where I need to apply bipartite weighted matching on a graph where the edge weights are real (positive and negative). I have looked at several implementations of the Hungarian method ...
-5
votes
1answer
234 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 ...
14
votes
1answer
405 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 ...
0
votes
1answer
468 views

Computational complexity and reductions to linear programming

My question is rather general, but I have not been able to find a satisfactory answer for quite a long time, and I wonder if there has been a research concerning these issues. I have come over a ...
8
votes
2answers
312 views

Hardest optimization problems in NC

When learning optimization problems, we usually consider linear programming (or more generally: convex optimization) as the simplest example. It is solvable in polynomial time, and has relatively easy ...
8
votes
1answer
449 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} ...