The tag has no wiki summary.

learn more… | top users | synonyms (1)

1
vote
1answer
185 views

Conditions for differentiability of minima and minimizers of linear functionals?

Let $B$ be a (real) Banach space and $C$ be a compact convex subset of $B$. For every continuous linear functional $F$ on $B$, define $V(F)=min_{c\epsilon C} F(c)$ and $S(F)= { \lbrace c \epsilon C ...
3
votes
1answer
398 views

Solving for Hamiltonian path with constraints on allowable routes through vertices

Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...
0
votes
1answer
362 views

Minimum distance between two data sets

Suppose we have two sets of data, $X$ and $Y$, each of which contains $10$ positive numbers. Now let us order the data sets $X=\left\{ x_{1},\cdots,x_{10}\right\}$, $x_{1}\ge\cdots\ge x_{10}>0$ and ...
1
vote
0answers
717 views

How to solve simple bilinear equations under extra linear constraints

Hello, This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy: $\lambda_i^T ...
1
vote
1answer
585 views

Can one efficiently optimize over the inverse of matrix?

Hello, I have the following problem: Find a non-negative matrix $L$ (i.e. $L_{i,j} \geq 0$ for all $i,j$), $L \neq I$ so that $A(I-L)^{-1}y \geq 0$ (the inequality must hold for each component), ...
0
votes
0answers
111 views

sparsest cut always has solution

Hi! How to prove that sparsest cut always has an optimal solution which is the cut for some vertex-subset. Looks like it's should be a kind of fundamental theorem for sparsest cut. But I didn't ...
1
vote
1answer
229 views

Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding: Algorithm 14.1 (Set cover via LP-rounding) Find an optimal solution to the LP-relaxation. Pick all sets ...
1
vote
1answer
98 views

Are there intuitive/classically algorithmic analogues to Semidefinite programs on networks?

Many network optimization algorithms, including shortest path, push-relabel, augmenting path, etc, actually have an interpretation in terms of linear programming. A famous application of semidefinite ...
1
vote
1answer
382 views

Need help to find an efficient algorithm for the following problem!

Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$. Given $A_{n\times n}$ is the covariance matrix of $x$. $u$ is a given n-dimensional vector of real ...
0
votes
1answer
239 views

Lovasz theta function - uses

Lovasz theta function bounds the Shannon capacity of graphs. What are some other uses of the function - especially in asymptotic coding theory and optimization problems?
3
votes
1answer
277 views

Partially optimal solutions in integer linear programming

Linear programs with a totally unimodular system matrix are known to have an optimal integer point. They are therefore solvable via relaxing the integer constraints to intervals. An other interesting ...
4
votes
3answers
559 views

Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi, I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
2
votes
0answers
405 views

Guessing game with guess cost

This is a question about Problem 328 on the website Project Euler. A description of the problem is provided in the previous link. I was wondering if there has been any research done on this question. ...
10
votes
1answer
537 views

Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason. Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$. I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...
2
votes
0answers
236 views

Linear complementarity problem: principal pivoting algorithm

I'm trying to implement the "Dantzig; van de Panne and Whinston" principal pivoting algorithm for solving symmetric positive semi-definite LCPs from "The Linear Complementarity Problem" book ...
3
votes
1answer
319 views

Mathematical Programming with other Algebras than Linear

Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization. What analogies are there for ...
1
vote
2answers
1k views

Linear programming - uniqueness of optimal solution

Is it possible to build such an objective function for a given set of constraints, so that there will be only one optimal solution? My general problem is to get any vertex of a polytope formed by a ...
6
votes
3answers
2k views

Random Sampling a linearly constrained region in n-dimensions…

Hi, So here is my problem: Given a nonlinear, discontinous, cost function $f(x_1,x_2,..,x_N)$ along with linear constraints $x_n \ge 0, \forall n$ $x_n \le c_n$ and $\sum_{n=1}^N x_n = 1$ find an ...
2
votes
0answers
168 views

Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as $$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right), $$ where all $c_{ij}<0$ (so that ...
3
votes
2answers
3k views

Linear program to maximize the minimum absolute value of linear functions ?

I'd like to compute $\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$. where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$. Can this be solved with a linear ...
2
votes
5answers
920 views

Circumference of convex shapes

Here is a puzzle I found in "Mitteilungen der DMV" (roughly "Letters of the German Society of Mathematicians") issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
5
votes
0answers
183 views

A polytope associated with the Hadamard Transform

In an investigation of whether or not a subset $V$ of "Hamming Space" $M_n = \mathbb{F}_2^n$ is a tile (i.e. whether $M_n$ can be written as a disjoint partition of translates of $V$) in ...
3
votes
0answers
542 views

Infinite Linear Programming

I'm trying to prove optimality for a continuous linear program. That is, I have a linear program with an uncountable number of variables and constraints. I'm not sure how to demonstrate feasibility ...
1
vote
1answer
3k views

Detection of Redundant Constraints

Suppose I pose the following query to a constraint logic programming system: ?- Y <= 6 - X, Y <= (- 4) + 4 * X, Y <= 4 + X / 3. Are there systems that would recognize the last inequality as ...
4
votes
2answers
437 views

Continuous Transportation Problem

Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the ...
2
votes
2answers
232 views

Maximization of a matrix product by iterative methods

This might not be very difficult, but I think I may have gotten a little confused. Suppose we are given a matrix A, and would like to find the vector x of modulus 1 which maximises the product xt A x ...
2
votes
1answer
933 views

solving multiple linear programming problems with the same set of constraints

Hi, I need to solve a set of linear programs of the form: Problem $i$: $\quad \max c_i \cdot x$ s.t. $ A x \leq b$. The $c_i$'s are different vectors so each problem has a different objective ...
11
votes
2answers
1k views

The cone of positive semidefinite matrices is self-dual? (reference needed)

I'm seeking a reference for the following fact. The cone of positive semidefinite matrices is self-dual (a.k.a. self-polar). This result is relatively easy to prove, has been known for a long ...
1
vote
1answer
171 views

Model for shipping widgets in an optimal way

I am a programmer and have the following requirement. We are trying to figure out the optimal way to ship widgets. Below is the scenario: We need to ship 1,000,000 widgets We have two different ...
4
votes
2answers
446 views

Set Cover:Greedy vs LP

Hi Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches? thanks
2
votes
1answer
272 views

existence of l1 embedding using LP feasibility

hello Let (A, d) be an n-point metric space for $t \geq 1$,the task it to find an integer $m$ and an embedding $f : A \rightarrow R^m$ s.t. $\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq ...
1
vote
1answer
487 views

Split sum into equal terms

Given a sum of $l$ integers $r_1+...+r_k+...+r_l$ and an integer $t$. Find indices $1 < p_1 <...< p_h <...< p_{t-1} < l$ such that in sum ...
2
votes
4answers
406 views

Efficient algorithm for finding the minima of a piecewise linear function

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by $f(x) = \max_i ( a_i + b_i x )$ We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two ...
2
votes
0answers
275 views

When is polytope compatible with network flow?

A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
3
votes
3answers
3k views

Maximum flow with negative capacities?

I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient ...
4
votes
4answers
570 views

efficient way to compute the inversion of the following matrix

Hi, there I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special ...
0
votes
2answers
705 views

Degenerate case of linear programming duality?

Let's say we have a maximization linear program that looks like this: maximize $\vec{c}\vec{x}$, subject to $\matrix{A}\vec{x} \leq 0$, $\vec{x} \geq 0$. If we take the dual, we have "minimize ...
13
votes
0answers
2k views

Minimum tiling of a rectangle by squares

Given the $n\times m$ rectangle, I want to compute the minimum number of integer-sided squares needed to tile it (possibly of different sizes). Is there an efficient way to calculate this?
1
vote
1answer
466 views

Linear Programming Cost Function [closed]

I need to add the following to my LP problem: If the amount of workers hired in period $t$ ($H_t$) is higher than 25, the hiring cost is only 1 instead of 1.2. Example: if 30 workers are hired in ...
1
vote
4answers
726 views

Maximum average value within a rectangular bounding box

The goal is to expedite detection using the sliding window approach. In other words, an object classifier is known and I need to find where the possible locations of this object are in an image. This ...
1
vote
2answers
892 views

Inequality-constrained linear-regression, what is the covariance of the estimator?

If you do a linear regression: $||Ax - e ||^2$, where e is iid Gaussian, mean 0 and variance 1, then your answer is $x_{hat} = (A' A)^{-1} (A' * e)$ and the covariance of $x_{hat}$ is $(A' A)^{-1}$ ...
4
votes
1answer
1k views

How to find which subset of bitfields xor to another bitfield?

I have a somewhat coding-oriented problem. I have a bunch of bitfields and would like to calculate what subset of them to xor together to achieve a certain other bitfield, or if there isn't a way to ...
1
vote
1answer
2k views

what is the difference between the revised simplex method andthe full tableu?

No to sound naive but they look like they include the same steps to me, one's just the algorithmical representation of the other. Thanks in advance.
2
votes
0answers
265 views

Recovering a piecewise affine function

Lets say I have an piecewise affine convex function $f(x_1,x_2)$, on which the following operations are possible: Computing $f(x_1,x_2)$. Computing a subgradient to $f$ at $(x_1,x_2)$ Computing all ...
2
votes
2answers
474 views

Sorting a binary matrix diagonal in polynomial time while preserving rows

Is there a polynomial time solution to sort an arbitrary binary square matrix in polynomial time by rows so that the diagonal contains a 1 if any row contains a 1 in that column? For example given ...
0
votes
1answer
870 views

For Ax = b, x and b unknown vectors, how do I solve the x that maximizes min(b_i)?

Given a matrix $A$, each element $A_{i,j} \geq 0$, find the vector $\vec x$ that maximizes the minimum element in $\vec b$ ($\vec b = A \vec x$). Note that this is not a linear equation system as I ...
2
votes
2answers
898 views

Continuous Linear Programming: Estimating a Solution

I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the ...
4
votes
1answer
234 views

Symmetry of the integer gap

Are there results that bound the asymmetry of the duality gap of an integer program? That is to say, if the difference between the LP solution and the IP (primal) solution is $a$, is there a function ...
4
votes
2answers
1k views

Applications of minmax theorem(s)

Intro We suppose $X$ and $Y$ are nonempty sets and f: $X\times Y \rightarrow \mathbb{R}$. A minimax theorem is a theorem that asserts that, under certain conditions, $$ \inf_Y \sup_X f = \sup_X ...
1
vote
3answers
2k views

How to solve Linear Programming problem with tighter Integer Programming constraints

I want to learn a bit about Linear Programming. After some research, I decided to solve the Cutting Stock problem as an example to learn. After doing some more research, I feel like I finally ...