Skip to main content

All Questions

Filter by
Sorted by
Tagged with
5 votes
0 answers
581 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 ...
David Harris's user avatar
  • 3,475
3 votes
4 answers
4k views

Existence of nonnegative solutions to an underdetermined system of linear equations

Similar questions have been asked elsewhere, but I think this is sufficiently different to warrant a new post. I have a particular matrix $A$ and would like to know when the system $Ax = 0$ has at ...
bandini's user avatar
  • 491
6 votes
3 answers
11k 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 ...
Fumiyo Eda's user avatar
4 votes
4 answers
703 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 ...
Nancy's user avatar
  • 41
3 votes
2 answers
4k views

Complexity of convex quadratically constrained quadratic programming (QCQP)

Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP)? Any references?
mintaka's user avatar
  • 145
0 votes
2 answers
1k 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 $0\vec{...
Henry Yuen's user avatar
  • 2,019
14 votes
0 answers
4k 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?
didest's user avatar
  • 1,015
2 votes
1 answer
1k 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 ...
Bas Timmermans's user avatar
1 vote
4 answers
978 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 ...
Bernard's user avatar
  • 111
1 vote
2 answers
1k 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}$ ...
Tony Bruguier's user avatar
4 votes
1 answer
2k 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 ...
Bram Cohen's user avatar
1 vote
1 answer
9k 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.
Jorge Guzman's user avatar
2 votes
0 answers
281 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 ...
Ben's user avatar
  • 567
2 votes
2 answers
640 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 ...
Tristan's user avatar
  • 121
0 votes
1 answer
1k 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 ...
SoftMemes's user avatar
  • 135
6 votes
5 answers
720 views

Convex optimization over vector space of varying dimension

In all instances of convex optimization I know of, the dimension of the vector space is defined beforehand. Is there any work on convex optimization over a vector space of varying dimension? For ...
LowerBounds's user avatar
5 votes
2 answers
3k 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 ...
David S-D's user avatar
  • 373
4 votes
1 answer
275 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 ...
Chris Caragianis's user avatar
3 votes
1 answer
886 views

Is the max of two supermodular functions supermodular?

A function $f: \mathbb{R} \times \mathbb{R} \to \mathbb{R}$ is supermodular if for every $x'>x$ and $y'>y$, $$f(x',y') + f(x,y) > f(x',y) + f(x,y').$$ Suppose $f$ and $g$ are supermodular, ...
sbmmth's user avatar
  • 31
5 votes
2 answers
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
3 answers
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 ...
Unwanted Letters's user avatar
9 votes
1 answer
6k views

Proving that a binary matrix is totally unimodular

I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that ...
AaronDefazio's user avatar
10 votes
3 answers
6k views

Solving a system of linear inequalities -- what is the dimension of the solution set?

It is well known how to solve a system of linear equations $A{\bf x} = {\bf b}$, but how do we solve a system of linear inequalities $A{\bf x} \leq {\bf b}$? For the applications I have in mind the ...
Matthew Kahle's user avatar
6 votes
2 answers
8k views

Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations

Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
Adam Clarridge's user avatar
4 votes
1 answer
866 views

When is a triangular matrix totally unimodular?

I have a {0,1}, invertible, triangular matrix, that I would like to show is totally unimodular. Are there any known results on the total unimodularity of classes of triangular matrices?
Michael Biro's user avatar
  • 1,182
5 votes
1 answer
271 views

Feasibility of linear programs

It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?
Vinayak Pathak's user avatar
2 votes
0 answers
5k views

A system of linear equations with linear constraints

Mathematical problem. Suppose we have $2n$ indeterminates $x_1,\dots,x_n$ and $y_1,\dots,y_n$ (which are denoted by $q$ with indices and called abundances below) and $m$ subsets $P_1,\dots,P_m$ of $\...
Florian Breitwieser's user avatar
4 votes
0 answers
790 views

Is it possible to use linear programming to solve this problem?

I am trying to write software to minimize pricing for cell phone subscription services, ie: choose the optimum plan for each customer in a large group. Could someone comment on whether this is ...
user6546's user avatar
6 votes
3 answers
2k views

A simple infinite dimensional optimization problem

I'd be grateful for a reference for the following result, which I believe to be true, and should be well-known. Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
Guy Katriel's user avatar
29 votes
6 answers
8k views

How to find a closest integer point to the intersection of two lines?

Here's a question that originates from StackOverflow. Given are two lines on a plane, specified by equations ($a x + b y = c$) with integer coefficients. The lines aren't parallel and they don't ...
P Shved's user avatar
  • 391
1 vote
0 answers
1k views

Covariance matrix formula interpretation - what am I missing?

I'm reading a paper that outlines the calculation of a covariance matrix like the following: $C=\displaystyle\sum^{N_b}_{i=1}\vec{x}_i\vec{x}_i^T$ What is the order of this matrix? My interpretation ...
fbrereto's user avatar
  • 111
0 votes
2 answers
4k views

Linear programming piecewise linear objective

I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this: max $\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}$ $s.t. $ $|\...
AFJ's user avatar
  • 3
10 votes
1 answer
2k views

Sum of difference moduli vs. sum of modulus differences

This is a failed attempt of mine at creating a contest problem; the failure is in the fact that I wasn't able to solve it myself. Let $x_1$, $x_2$, ..., $x_n$ be $n$ reals. For any integer $k$, ...
darij grinberg's user avatar
18 votes
3 answers
3k views

Deciding membership in a convex hull

Given points $u, v_1, \dots,v_n \in \mathbb{R}^m$, decide if $u$ is contained in the convex hull of $v_1, \dots, v_n$. This can be done efficiently by linear programming (time polynomial in $n,m$) in ...
Mitch's user avatar
  • 667

1
21 22 23 24
25