All Questions
985 questions
3
votes
1
answer
275
views
Uniqueness of l1 minimization
Let $A \in \mathbb{R}^{m \times n}$.
Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to
$\...
- 3,209
2
votes
1
answer
213
views
Intersection of sphere with triangle containing moving vertices
First off, apologies if I cannot properly articulate my question in the most formal way. However, I believe my question should be simple enough to grasp anyhow.
In $\mathbb{R}^3$, I would like to ...
- 121
1
vote
0
answers
177
views
Prove that these linear programming problems are bounded by $O(k^{1/2})$ [closed]
The expanded partial sums of the Möbius inverse of the Harmonic numbers have two out of three properties in common with this set of linear programming problems:
$$\begin{array}{ll} \text{minimize} &...
- 1,183
1
vote
0
answers
68
views
Projection of a polytope along 4 orthogonal axes
Consider the following problem:
Given an $\mathcal{H}$-polytope $P$ in $\mathbb{R}^d$ and $4$ orthogonal vectors $v_1, ..., v_4 \in \mathbb{R}^d$, compute the projection of $P$ to the subspace ...
- 11
5
votes
1
answer
183
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...
CommunityBot
- 1
3
votes
2
answers
331
views
Program to solve Optimization Problem
I have an optimization problem, this problem has linear constraints and nonlinear constraints. I solved the linear part by MATLAB but the nonlinear constraints I could not solve it. I downloaded ...
- 1,517
0
votes
0
answers
232
views
What do square roots as minimums have to do with Harmonic numbers?
In an earlier question where I conjectured (and GH from MO confirmed) that the von Mangoldt function is the limit at s=1 of a certain Dirichlet series:
$$\Lambda(m)=\lim_{s\to 1+}\zeta(s)\sum_{d\mid ...
- 1,183
5
votes
1
answer
424
views
What is the LP gap of vertex cover in planar graphs?
What is the LP gap of vertex cover in planar graphs?
The LP I refer to is min $\sum_{e \in E } c_e x_e \ \ $ subject to $ \ \ x_v + x_u \geq 1 \ \ \ \forall uv \in E $
$ c_e \geq 0 $ are ...
- 26
3
votes
0
answers
178
views
Uniqueness of projection under spectral norm
I am considering
$$
\min_{M\in \mathcal{M}} \|X - M\|:=x \neq 0,
$$
where $X$, $M$ are $m\times n$ matrices, $\|\cdot\|$ is spectral norm and $\mathcal{M}$ is a matrix subspace. I wonder to what ...
- 131
1
vote
0
answers
36
views
Linear programming with a convergent coefficient
The following linear programming problem
$x_n = \arg\min c_n'x \mbox{ subject to } Ax<b$
has a changing coefficient $c_n$. We have that $c_n\rightarrow c_*$. What happens to the solution $x_n$? ...
- 19
2
votes
1
answer
243
views
Does quantifier elimination help here?
Suppose we have a quantified linear program
$$\exists z_1,\dots,z_{poly(n)}\in\mathbb R$$
$$\exists u_1,\dots,u_n\in\mathcal P\cap\mathbb R^m$$
$$\forall v_1,\dots,v_n\in\mathcal P\cap\mathbb R^m$$
$$...
- 1,826
3
votes
1
answer
291
views
How to find the vertices of the set $\{v_i\in \mathbb{R}:a_1\ge v_1\ge v_2\ge \cdots\ge v_n\ge 0,\ q_2\le \sum_{i=1}^n p_iv_i\le q_1\}$
I am given a set of inequalities $v_1\ge v_2\ge \cdots\ge v_n\ge 0$, $q_2\le \sum_{i=1}^n p_iv_i\le q_1$, with $\{p_i\}_{i=1}^n,\ q_1,q_2$ positive reals, and only one bound for the coordinates: $v_1\...
- 128k
3
votes
1
answer
152
views
A question about polytopes related to linear programming
Given linear functions $f_1({\bf x}),\dots,f_n({\bf x})$ on ${\bf R}^m$, let $K = \{(a_1,\dots,a_n) \in {\bf R}^n:$ the $n$ halfspaces $\{{\bf x}: f_i({\bf x}) \leq a_i\} $ have nonempty intersection$\...
- 24.2k
1
vote
0
answers
126
views
Mixed integer formulation of union of polytopes?
Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
- 1,826
4
votes
3
answers
2k
views
Hyperrectangle partition of set of overlapping hyperrectangles
I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. ...
- 111
1
vote
0
answers
48
views
Efficient scissors congruence between efficiently describable convex polytopes and simplex?
Is there a convex polytope in $\mathbb R^n$ describable by only $O(poly(\log n))$ half-plane inequalities with positive volume (so at least $n+1$ vertices) such that the standard simplex has a ...
- 1,826
1
vote
0
answers
65
views
Covering a simplex efficiently by efficiently describable polytopes?
Take a standard simplex or cube in $\mathbb R^n$.
Is there a way to cover it with $O(poly(\log n))$ convex polytopes each describable by only $O(poly(\log n))$ half-plane inequalities?
If not what ...
- 1,826
1
vote
0
answers
64
views
Polytopes that can be efficiently described and efficiently covered by cubes or simplices?
Is there a bounded convex polytope $\mathcal P\subseteq\mathbb R^n$ with $m$ vertices, whose vertex vectors span $\mathbb R^n$ (so $m$ is $\Omega(n)$) and just $O(poly(\log n))$ half-plane ...
- 1,826
2
votes
1
answer
440
views
Build reversed No-Fit-Polygon
I need some robust algorithm to optimally fit one non-convex polygon into another. The destination one can contain holes.
Recently I found scholarly articles on this subject:
One of them describes ...
- 151k
3
votes
1
answer
588
views
How to partition a graph into N groups with M elements nearest?
This problem probably already here but I could not find the right words to find it.
I have a list with 1700 points (geographic coordinates) and a need to separate into 17 groups with 100 nearest. I ...
- 4,713
0
votes
1
answer
39
views
Gluing simplices through a common point/ realisation of a convex simplicial polytope
Given $m≥d+1$
a positive integer, is it always possible to find m d-dimensional simplices $\Delta_i=\mathrm{Conv}(M,V_{i,1},…,V_{i,d})$ such that
1) they all share the common vertex M
2) the ...
- 14k
10
votes
1
answer
565
views
The intersection of two $l_1$ balls
Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ with respect to the $l_1$ norm that have different radii and different centers. Is there an upper bound for the number of vertices that $B_1\cap B_2$...
- 4,653
1
vote
1
answer
126
views
Quantifier elimination and where is this quantified convex program in the polynomial hierarchy?
I have a quantified convex program of the form that I need to solve
$$\exists(x_{1,1},\dots,x_{1,n})\in\mathbb R^n\quad\forall(x_{2,1},\dots,x_{2,n})\in\mathbb R^n$$
$$\vdots$$
$$\exists(x_{2t-1,1},\...
- 14k
2
votes
1
answer
270
views
Algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane
I am trying to find an algorithm to compute the convex hull of a set of $m$ possibly intersecting convex polygons in the plane, with a total of $n$ vertices. Let $h$ denote the number of vertices on ...
7
votes
1
answer
3k
views
Any reference to an algorithm for finding the largest empty circle on a sphere (with great-circle distance)?
Given a set $S$ of 2D points in the plane, there are known algorithms for finding the largest empty circle ($LEC$) of the set of points.
The $LEC$ problem is stated in this way: find a $LEC$ whose ...
- 151k
7
votes
2
answers
909
views
Formula for volume of a convex polytope
So I've been searching around the internet for some answers to this, but I currently have a set of linear constraints: $Ax = b, Cx \le d$ for matrices $A \in \mathbb{R}^{n \times m}$, $b\in \mathbb{R}^...
- 984
1
vote
1
answer
95
views
Uniformly sampling the solution space for points where the free termini of two rays, anchored at 3-space points, can intersect
I have two rays, one of length $L_1$ and one of length $L_2$. I anchor these rays, each at one end, on the 3-space points $p_1$ and $p_2$. Assuming that the Euclidean distance between $p_1$ and $p_2$...
- 4,713
6
votes
4
answers
752
views
Algorithm for k-medians in a convex polygon
Are there any known approximation algorithms or exact solution schemes for the k-medians problem in a convex polygon? That is, placing a collection of points $p_1,\dots,p_k \subset \mathbb{R}^2$ in a ...
- 4,713
1
vote
0
answers
179
views
Boundary surfaces in a 3d Voronoi tessellation with obstacles
Let $x_1,\dots,x_n$ be a set of points in $\mathbb{R}^3$ and let $\mathcal{O}_1 ,\dots, \mathcal{O}_m$ denote a set of polyhedral obstacles. What is the name for the surfaces that describe the ...
- 4,713
2
votes
1
answer
110
views
A questions concerning Laguerre/Voronoi tessellations
Fix $n>1$ distinguished points $x_1,\ldots, x_n\in \mathbb R^d$, the Voronoi tessellations are the subsets $V_1,\ldots V_n\subset\mathbb R^d$ defined by
$$V_k~~ := ~~ \big\{x\in\mathbb R^d:\quad |...
- 6,337
5
votes
0
answers
350
views
Are nearby points in an algebraic curve necessarily connected?
I would like a result of the following form:
For every algebraic curve $C$ in $\mathbb{R}\mathbf{P}^{n-1}$, there exists an
explicit and easy-to-compute $\epsilon=\epsilon(C)>0$ such that ...
- 7,633
1
vote
0
answers
24
views
Simple monotonicity property for coordinate descent and linear objective functions
Let $S \subset \mathbb{R}^n$ satisfy $0\leq x_1\leq\dots\leq x_n$ for all $\mathbf{x}\in S$, among other (possibly nonconvex) constraints, and suppose in addition that $\sum_{i=1}^n x_i \geq 1$ for ...
- 4,049
0
votes
0
answers
89
views
Why there isn't lexicographically smallest solution to a bounded linear program?
I am learning computational geometry when I run into this confusion. "A bounded 2D linear program may not have a lexicographically smallest solution", as the book says. I wonder why? I think we can ...
- 1
1
vote
0
answers
37
views
Fast certficate of negativity for objective value of mixed-integer linear program
Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP)
$$
\begin{split}
f^* = &\max \; ...
- 6,853
2
votes
1
answer
270
views
What optimization problems have solutions with few nonzeros?
Consider the following optimization problem, with $n$ variables and $m$ linear constraints:
\begin{align}
\text{maximize} && c_1 x_1 + \cdots + c_n x_n &
\\
\text{subject to} && a_{...
- 14k
4
votes
2
answers
145
views
Complexity of Determining the Edges of Planar Convex Hulls
Question:
can the set of edges that resemble the convex hull ($CH$ for short) of $n$ points in the euclidean plane be determined in $O(n)$ time?
I know that the time complexity of determining the $CH$...
CommunityBot
- 1
3
votes
0
answers
61
views
Biggest Cartesian Product Included in a Real Plane Curve
Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as ...
- 351
13
votes
3
answers
834
views
Famous theorems that are special cases of linear programming (or convex) duality
The max flow-min cut theorem is one of the most famous theorems of discrete optimization, although it is very straightforward to prove using duality theory from linear programming. Are there any ...
- 109k
7
votes
1
answer
374
views
Sampling uniformly from the vertices of a polytope
I'm looking for a reference on how to sample uniformly (and preferably efficiently, elegantly, etc.) from the vertices of a polytope. I gather that enumerating vertices is hard. I also note the MO ...
- 15.4k
4
votes
2
answers
480
views
Complexity of Random Delaunay Triangulation in 3D
My question:
Is the number of cells in a three-dimensional Poisson-Delaunay triangulation with $n$ vertices $\mathcal O(n)$ with probability one?
which is equivalent to the question
Is the ...
- 18.6k
1
vote
1
answer
330
views
How good is the LP relaxation?
Consider the optimization problem
\begin{align}
\max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i
\end{align}where $c,b\in\mathbb{R}_{+}^n$ and $A\in\mathbb{R}_{+}^{n\times n}$...
5
votes
1
answer
234
views
Generalizations of the "Curious Tiger" Polygon
I actually don't know, whether the polygon I describe here already has name, but let me explain the problem, that is solved by the polygon, with a little story:
Imagine a flat terrain with bushes of ...
CommunityBot
- 1
6
votes
5
answers
4k
views
Formulas for equidistant curves
I'm trying to draw on the computer a curve that keeps always the same distance(given as parameter) from a given curve. I know the formula for the given curve. I tried moving perpendicular to the first ...
- 101
2
votes
0
answers
61
views
Efficient algorithm to prove that a polynomial ideal contains 1
I have the following problem:
Suppose to have an ideal $I\triangleleft k[x_1,...,x_n]$ defined by generators. There exists an efficient algorithm (perhaps more efficient than calculating the Groebner ...
- 297
0
votes
2
answers
102
views
Does Max Flow produce uniform results? [closed]
I am interested in using Max Flow algorithm. I want to simulate transfer of quantity. Anyway, I am unsure of some thing.
Does Max Flow algorithm produce uniformly distributed max flow?
I have ...
- 400
1
vote
3
answers
138
views
Literature request: Function that depends on a linear optimization problem [closed]
my question is about functions of the following form:
$$ f(t) = \max_{\mathbf{x}}~ \mathbf{c^T x} ~ {\rm s.t. \mathbf{Ax} +t \cdot \mathbf{a} \leq \mathbf{b}}, $$
where $\mathbf{x},\mathbf{b}, $ ...
- 1,991
3
votes
1
answer
553
views
Calculate the discrete set of points B which are in the convex hull of the set of points A
This problem is likely best described with the following picture:
Given the discrete set of points $A$ (shown in blue), I wish to calculate the discrete set of points that are contained within the ...
- 4,713
1
vote
1
answer
520
views
computing the boundary of a union of polytopes
Let $P_1,\dots ,P_m\subset \mathbb{R}^n$ be $m<\infty$ convex polytopes in $\mathbb{R}^n$, and $U:=\bigcup_{j} P_j$ their set-theoretic union. What algorithms are known for computing the boundary $\...
- 151k
7
votes
0
answers
122
views
Does the problem of recognizing 3DORG-graphs have polynomial complexity?
A 2DORG is the intersection graph of a finite family of rays directed $\to$ or $\uparrow$ in the plane. Such graphs can be recognized effectively (Felsner et al.). A 3DORG is the intersection graph of ...
- 4,535
2
votes
1
answer
349
views
Several convex polytopes in a simplex; fix an extreme point for each; how many can be supported by a function monotonic on all line segments?
Sorry the title may be unclear. I do not know how to give it a good title.....
Let $\Delta$ be a probability simplex of $R^N$; i.e. set of all points $x$ such that $x\geq0$ and $\sum_{k=1}^Nx^k\leq1$....
CommunityBot
- 1