All Questions
740 questions
9
votes
1
answer
2k
views
Uniform sampling from general simplex with a twist
This is part of a question I had asked elsewhere, and then some of the links redirected me to CS stack exchange.
Given $0\leq a_1\leq\dots\leq a_D\leq1$ (all strictly positive), I want to draw points ...
- 221
1
vote
0
answers
64
views
Maximize discrete harmonic function at given point
Let $n>0$, and let $S_n$ denote the discrete square
$S_n=[|-n,n|]^2$ (so $S_n$ has $(2n+1)^2$ elements). Let $K_n$ denote the set of four corner points $\lbrace (\pm n,\pm n)\rbrace$, and $C_n=S_n\...
- 621
2
votes
0
answers
299
views
Practical application of envelope theorem for linear programs
Assume that we have solved a (standard) linear program
$$
\text{minimize}_{x\in {\mathbb R^n}}\,\, c_0^Tx, \,\,\,\,\, \text{s.t. } A_0x \leq b_0,
$$
and would like to know how sensitive is the optimal ...
- 7,182
2
votes
1
answer
3k
views
max-flow at max-cost
I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
- 121
0
votes
0
answers
135
views
Number of polyhedra with N faces?
A. Up to isomorphism, how many polyhedra with N faces are there? Assume each face can be a triangle, square, pentagon, hexagon, etc... Furthermore each edge can be resized to any nonzero positive ...
- 101
1
vote
0
answers
55
views
Separation on discrete set
Consider the set $L = \prod_{i=1}^n\{1,0\}$, i.e. L consists of the element of n-tuples whose entries are 0 or 1. Also we can regard $L$ as a subset of $R^n$.
Define linear functions $f(x)= a_1x_1+ \...
- 61
2
votes
0
answers
64
views
Finding orthogonal basis with constraint
Is there any fast algorithm that output an orthogonal basis $e_i,i\leq n$ of $R^n$
with $e_i\in V_i$? Where $V_i,i\leq n$ are given linear subspaces of $R^n$.
And is there any condition on $V_i,i\leq ...
- 909
2
votes
0
answers
71
views
Existence of probability distribution satisfying upper/lower bounds on events
Suppose we have a finite sample space $S$ and some events $A_1, \dots, A_k \subseteq S$. We would like to put a probability distribution on $S$ so that no element has probability greater than a ...
- 21
3
votes
2
answers
134
views
Unit-Distance Polyhedra
What polyhedra are known to have two vertices adjacent if and only if they are of distance $d$ apart, for fixed $d$? For example, regular Platonic solids satisfy this condition, so I am looking for ...
- 131
4
votes
1
answer
345
views
Existence of Nonnegative Solutions of Linear Systems of Equations and Inequalities with particular constraints
Suppose we have an $n \times m$ nonnegative matrix $A$, where each row sums to $1$. I wonder whether there exists an $m \times n$ nonnegative matrix $X$ that satisfies the following constraints:
...
- 49
2
votes
1
answer
201
views
Minimum cover for sets in which each element appears in exactly 2 sets?
Is there an algorithm for finding minimal covers of a set of sets in which each element of the universe appears in exactly 2 sets? I realize that LP relaxation approximates this to within a factor of ...
7
votes
0
answers
1k
views
Closed-form solution of a linear programming question
Among all the probability matrices
\begin{equation*}
P =
\left(\begin{array}{cccc}
p_{00} & p_{01} & \ldots & p_{0,J-1} \\
p_{10} & p_{11} & \ldots & p_{1,J-1} \\
\vdots & \...
1
vote
1
answer
104
views
Testing whether two vertices are neighbours
I face the following problem: I am given a high-dimensional, convex, bounded polyhedron in both vertex description: $X = \mathrm{conv} \, \{ v_1, \ldots, v_K \}$ and halfspace description: $X = \{ x \...
0
votes
0
answers
63
views
Distinguishing (possibly lower dimensional) $1$-skeleton of a regular graph inscribed in a sphere
Consider you have two (possibly same) convex $1$-skeleton of a regular graph $A$ and $B$ in $m$-dimensions inscribed in a sphere with possibly exponential number of vertices in $n$-dimension with ...
user76479
2
votes
2
answers
438
views
Perturbation of Linear Programs
Consider the linear program,
$$\begin{array}{ll} \text{maximize} & c^T x\\ \text{subject to} & Ax \leq b\\
& x \geq 0\end{array}$$
I want to study the sensitivity of the optimal $x^*$ ...
- 275
4
votes
0
answers
229
views
Harborth's conjecture and polyhedra
Harborth's conjecture states that every planar graph can be drawn on a plane only using staight line segments of rational or integral edge length.
( There is a good mathoverflow page for this ...
- 481
4
votes
1
answer
289
views
Convex polyhedra, combinatorial types and Symmetry
Steinitz theorem says that combinatorial types of convex polyhedra is identified with 3-connected planar graph, called by a polyhedral graph.
A symmetry of polyhedral graph means that a vertex ...
- 481
0
votes
1
answer
204
views
Is the linear production game a convex game?
In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem.
Does anyone know if the LPG is a convex ...
- 17
1
vote
1
answer
391
views
Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
Suppose you have two polytopes $P_1, P_2 \in \Bbb{R}^n$ given by
$$ P_1 = \lbrace x: A_1 x \le b_1\rbrace$$
$$ P_2 = \lbrace x: A_2 x \le b_2\rbrace $$
I wish to find their convex hull, that is a ...
- 2,689
2
votes
0
answers
177
views
Formulating shortest path as submodular minimization
I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function.
The answer ...
- 21
6
votes
1
answer
263
views
Algorithm that solves every Mixed Integer Linear Program (to optimality)?
Given a Mixed Integer Linear Program with rational coefficients (both for the objective functions and all constraints), is it always possible to solve it algorithmically?
I know that you usually ...
- 1,282
2
votes
0
answers
112
views
Pcross-like, nonogram-like in near-linear time [closed]
I have a problem with a puzzle game like pcross in which I have a nxn square: At any index of rows and columns I have an integer that say the maximum numbers of points that I can place in that row/col....
2
votes
1
answer
531
views
Complexity of Deciding Feasibility of a system of linear inequalities over restricted variables
I am working out an interesting problem and would like some help with this particular sub problem:
Suppose we have a matrix $ M =\left\lbrace a_{ij}\right\rbrace $ of size $n\times m$ where $ a_{ij}\...
- 21
0
votes
1
answer
543
views
Convert general optimization problem to LP problem
I am trying to convert the following problem into a linear programming problem:
There are $M\times N$ matrix $T$ of real numbers between 0 and 1 and $N\times 1$ vector $w$ of real numbers between 0 ...
- 99
9
votes
3
answers
436
views
Labeling edges of an icosahedron with sum constraints
The question is inspired by this previous MO question. There it was shown that it's possible to label the edges of a cube by the numbers $\{1,2,\ldots,6,8,9, \ldots, 13\}$ in such a way that:
Three ...
- 20.8k
0
votes
1
answer
2k
views
When to use non-negative-least square and least-square [closed]
What are the typical case we need to use Non-negative least squares NNLS
$$
||Ax - B||^2
$$
instead of least-square $$ Ax-B$$ (or vice versa)?
And is there any drawback in applying them on large $A$...
- 135
3
votes
1
answer
260
views
Better alternative to solve quadratic programming for large matrices
I have the following problem. Let's say we have $x_{jk}$ it is an expression value of gene $j$ in a sample $k$. It is the average of expression levels across the cell types $s_{ij}$, weighted by ...
- 135
6
votes
1
answer
182
views
Self-avoiding/reflecting geodesics on a convex surface
Let $S$ be the surface of a convex body embedded in $\mathbb{R}^3$.
For me $S$ is a convex polyhedron,
but I am happy to view $S$ as a smooth body with positive Gaussian curvature
at each point, or ...
- 151k
3
votes
0
answers
970
views
Testing if a point is inside a convex polytope formed by halfspaces in n-dimension
Assume we have a convex polytope that is formed by the intersection of $k$-halfspaces in $\mathbb{R}^{n}$.
$$
a_{0,0}x^{n-1} + {a}_{0,1}x^{n-2} + ... a_{0,n-1} \leq 0
$$
$$
a_{1,0}x^{n-1} + {a}_{1,...
- 31
3
votes
1
answer
136
views
symmetric group of regular polyhedrons
Let $\Delta^n$ be the regular $n$-simplex spanned by $(n+1)$ vertices, equipped with an Riemannian metric such that all the edges are of equal length. For example,
$\Delta^2$:
$\Delta^3$:
Let $c:=c(...
- 543
0
votes
1
answer
82
views
Introducton books for $\frak{E}_p(I)$
Are there any good books different from abstract harmonic analysis by hewitt to study $\frak{E}_p(I)$. where $\frak{E}_p(I)$ is: Let $I$ be an arbitrary index set. For each $i\in I$ let $H_i$ ...
- 209
8
votes
0
answers
171
views
Which -icial sets produce the "standard" representations of symmetric groups?
Suppose you have a system of cell complexes (say, even convex polyhedra) $(P_n)_{n\geqslant0}$ which occur as faces of each other and are used to define the corresponding notion of "$P_*$-set". So ...
- 18.4k
5
votes
1
answer
146
views
How does one go from convexity to submodularity?
If I have a function which is convex in the hypercube, $[-1,1]^n$ then when would it imply that its restriction to $\{-1,1\}^n$ is submodular?
It would be helpful is someone can share some specific ...
- 1,893
1
vote
1
answer
219
views
approximate diameter of polytopes in high dimensions
I just came across the following problem:
Let us consider the unit corner of the n-cube
$$
\Delta^n = \left\{(t_1,\cdots,t_n)\in\mathbb{R}^n\mid\sum_{i = 1}^{n}{t_i} \leq 1 \mbox{ and } t_i \ge 0 \...
- 75
2
votes
0
answers
154
views
Listing all Lattice Points in a Box
Let $B := [-1,1]^n$ be an $n$-dimensional box. Moreover, let $v_1,\ldots,v_n \in \mathbb{R}^n$ form a basis of $\mathbb{R}^n$, where the entries of the $v_i$ are explicitly irrational. We can assume ...
- 173
3
votes
2
answers
792
views
Has anyone developed a technique to generate a polytope given (possibly redundant) inequality constraints? [closed]
I've found a few papers that deal with removing redundant inequality constraints for linear programs, but I'm just trying to find the vertices for a feasible region, given a set of inequality ...
- 131
1
vote
0
answers
171
views
Finding all feasible solutions
Let $u$ be a $n_{max} \times m$ matrix. Let $z$ be a $n_{max} \times s_{max} \times n_{max}$ cube. Let $w$ be a $n_{max} \times 1$ vector. All the three matrices can have values from the set $\{ 0, 1\}...
- 175
2
votes
0
answers
210
views
Finding optimal linear transformation for intersection of convex polytopes
I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) ...
- 695
0
votes
0
answers
107
views
Under which conditions is the union of conic hulls of sets in a cartesian product equal to $\mathbb{R}^N$?
Question: Under which conditions on $A, B\in\mathbb{R}^{N\times N}$ is the function $f: \mathbb{R}^N\mapsto \mathbb{R}^N$,
$$f(v) = A[v]_+ + B[-v]_+$$
surjective? Here $[.]_+$ is an elementwise ...
- 123
1
vote
0
answers
120
views
The column generation technique on a Train Unit Assignment Problem [Linear Programming]
I am doing an assignment where I need to implement a mathematical model that I can't wrap my head around. For the technique of column generation, one would need to my understanding, a master problem ...
- 111
4
votes
1
answer
3k
views
Find the minimum distance between two convex hulls
We work over $\mathbb{R}^N$. Let $\mathbf{P}_1$ denote the hyperplane constructed using $N$ points, each of which is on a different axis (there are $N$ axes). We denote by $\mathbf{P}_2$ the convex ...
- 233
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 ...
- 13.2k
9
votes
4
answers
475
views
Uniform Sampling Subject to Linear Equalities and Non-Negativity Constraint
I'm trying to sample uniformly on the intersections of faces of several simplicies, with all coordinates being non-negative. That is, given constraints
$$A\vec{w}=\vec{b} \ \ and \ \ \vec{w} \geq \vec{...
- 191
1
vote
1
answer
561
views
Convex polyhedron and its Gauß-curvature [closed]
I have asked this question on MathSE and no one could give me an answer. So I'll post my question here.
What I am trying to prove:
A convex polyhedron has positive Gauß-Curvature at every vertex.
...
- 129
4
votes
1
answer
891
views
Basic result in semi-infinite linear programming
Consider a standard linear program of the form $$\textrm{minimize}_x~~~~ c^Tx~~~~ s.t. \\ Ax = b \\ x \geq 0$$ with $x\in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. It is well known that, if ...
- 4,049
2
votes
1
answer
186
views
How can I find the maximum value of this function?
For given values of $A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$, how can I find the value of:
$$
\max_{x \in [0,1]^n} \|Ax+b \|_1
$$
Or is this problem NP-hard?
- 23
26
votes
7
answers
3k
views
What's that shape? Inferring a 3D shape from random shadows
Let $P$ be a bounded, simply connected region of $\mathbb{R}^3$.
$P$ could be a polyhedron, or a smooth shape, or an arbitrary shape;
I'll assume below that $P$ is a (non-degenerate, perhaps non-...
- 151k
2
votes
1
answer
229
views
Algorithm to find the vertices of the equidistant lines between N closed polygonal lines
I have a set $\{C_1, C_2, \ldots, C_N\}$ of $N$ nonintersecting closed piecewise linear curves on the Euclidean plane. For every point $x \in \mathbb{R}^2$ we say it belongs to a territory serviced by ...
- 329
1
vote
0
answers
85
views
Smallest sum of original column entries in 2d matrix [closed]
I have an interesting optimization problem I am trying to solve now and I thought I'd share it here in order to find the best answer. The problem itself is not complicated and it is stated like this:
...
- 111
8
votes
1
answer
443
views
Convex Polyhedra Scissors Congruence Problem
I am currently writing a geometry paper "Rectifications of Convex Polyhedra" and I am confused to have discovered what appears to be a remarkable discrete geometric fact:
Conjecture: Let $P$ be a ...
- 1,431