All Questions
739 questions
1
vote
0
answers
28
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
2
votes
1
answer
875
views
Interpreting mincost flow dual variables
Consider the task of finding flow of size $b$ with minimum possible cost.
It may be formulated as linear programming in a following way:
$$\boxed{\begin{gather}
\min\limits_{f_{ij} \in \mathbb R} &...
CommunityBot
- 1
0
votes
2
answers
530
views
Any idea of solving an optimization problem with cubic constraints?
I have the following optimization problem with cubic constraints, which is hard to solve. Are there any ideas, or related references, of solving such a problem?
$$ \begin{array}{ll} \underset {y, z} {\...
CommunityBot
- 1
1
vote
0
answers
122
views
Growth polynomial of the Associahedron graph ? (Is it approximately Gaussian ?)
Consider Associahedron, consider graph build from its vertices and edges. Choose some vertex. Let us count the number of vertices on distances $k$ from the selected vertex. Write a generating ...
- 24.9k
11
votes
1
answer
651
views
How to correctly state Cauchy's rigidity theorem?
Cauchy's rigidity theorem is often stated briefly as
Any two (convex, 3-dimensional) polyhedra with pairwise congruent faces are themselves congruent.
As a more formal generalization to general ...
- 13.6k
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
1
vote
0
answers
56
views
Tiling with one of each 3D shape
Encouraged by the positive solutions to my question,
Tiling with one of each shape,
I'd like to pose the $\mathbb{R}^3$ equivalent:
Q. Is there a tiling of $\mathbb{R}^3$ by (bounded) polyhedra, one ...
- 151k
0
votes
0
answers
14
views
Sum of Simplex Volumes with Corners from Points in Convex Configuration
Question:
given $k,\,k>n$ points in convex configuration and general position in $n$ dimensional Euclidean space, i.e. no $n+1$ points of which are co-hyperplanar,
what can be said about how the ...
- 13.2k
14
votes
1
answer
556
views
What is the "schematic" point of view for regular polyhedra?
Last week, I read Wikipedia's article on Alexander Grothendieck. It lists his twelve greatest contributions to mathematics as accounted for in Grothendieck's own Récoltes et Semailles. The final item ...
- 498
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
- 109k
5
votes
2
answers
217
views
Smooth toric variety which is a cube is a bott tower (reference request)
According to Lee, Masuda and Park (page 3), the following result is "well-known in toric topology". I've found a proof, but I would like a published reference.
Let $X$ be a toric variety. ...
- 66
2
votes
3
answers
197
views
Is there a way to parametrize the configuration space of all convex polyhedra of a given combinatorial type as a convex set?
I'm sure this is easy/known, but I'm not hitting an appropriate search term for finding the answer and the coffee hasn't kicked in enough to come up with it myself:
Let $T$ be a simplicial 2-complex ...
CommunityBot
- 1
4
votes
1
answer
1k
views
Does the Lebesgue Differentiation Theorem hold for regular polytopes?
Lebesgue's differentiation theorem states that if $x$ is a point in $\mathbb{R}^n$ and $f:\mathbb{R}^n\rightarrow\mathbb{R}$ is a Lebesgue integrable function, then the limit of $\frac{\int_B f d\...
- 28k
1
vote
1
answer
115
views
$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves
$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
CommunityBot
- 1
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 63.9k
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 128k
1
vote
1
answer
331
views
Finding a special solution in a solution set over F2
Given a solution set of a linear system of the following form
$$
\{ \begin{bmatrix}
x_{1} \\
\vdots \\
x_{n}
\end{bmatrix} = \vec{v_1} * x_1 + \dots + \vec{...
CommunityBot
- 1
3
votes
1
answer
239
views
The realization space of non-convex polyhedra - What is known?
The space $\mathfrak R_{\mathrm c}(P)$ of convex realizations of a (3-dimensional, spherical) polyhedron $P$ is known to be well-behaved: it is a contractible manifold of dimension $\#\text{edges}+6$ (...
CommunityBot
- 1
3
votes
1
answer
368
views
Lot sizing problem: how to add these cuts efficiently
Consider the set of constraints of the uncapacitated lot sizing problem:
$$
\{(x,s,y)\in \mathbb{R}^n_+ \times \mathbb{R}^n_+ \times \mathbb{B}^n \;|\;s_{t-1}+x_t = d_t+s_t,\; x_t \le My_t,\; t=1,\...
CommunityBot
- 1
0
votes
1
answer
114
views
Mixed integer program and continuous Diophantine approximation
Let $n\in\mathbb{N}$ such that $n\geq 2$ and let $0<r<1$ be a real number. We wish to solve the following problem.
$$\min_{(t,(z_j)_{j=2}^n) \in \mathbb{R}\times \mathbb{Z}^{n-1}} t$$
subject to ...
CommunityBot
- 1
0
votes
1
answer
396
views
What is the best way to choose initial basis when applying simplex method to an equality form of LP?
Currently I'm trying to write a practically fast LP solver for a sparse instance, which is by simplex method with LU decomposition and eta-matrix update. In the development I realized that I'm not ...
CommunityBot
- 1
1
vote
0
answers
99
views
Minimum of the maximum element frequency given the family size and the universe size
[Crossposted at math.stackexchange].
Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$.
I have written and solved ...
- 988
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 ...
- 221
0
votes
0
answers
48
views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,214
9
votes
1
answer
519
views
If we know the combinatorics of a polyhedron, and all but one of its dihedral angles, does that uniquely determine the remaining dihedral angle?
If we know the combinatorics of a polyhedron, and all but one of its dihedral angles, does that uniquely determine the remaining dihedral angle?
I’m happy to assume the polyhedron is simply connected, ...
- 2,896
5
votes
0
answers
82
views
What tools can show that (possibly irregular) dodecahedra do not fill space?
(Formerly on MSE.)
Here is a fairly natural question: Can three-dimensional space be filled with convex polyhedra of the same incidence structure (if not the same geometry) as the regular dodecahedron,...
- 3,068
2
votes
3
answers
1k
views
Concrete works by Alexandre Grothendieck, other than Dessin d'Enfants?
For me "Dessin d'Enfants" by Alexandre Grothendieck is the more concrete research work he has done. I would like to know if there are others.
When he was teaching at Montpellier University (...
- 6,357
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 ...
- 132
0
votes
0
answers
115
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
5
votes
1
answer
176
views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 5,429
0
votes
0
answers
52
views
Polyhedra volume, faces and edges from vertices
Given a set of vertices in 3D corresponding to a convex polyhedron, what is the most efficient way to find its volume, faces, and edges?
I've found some techniques using convex hulls. But I think I ...
- 101
41
votes
3
answers
3k
views
Can the unsolvability of quintics be seen in the geometry of the icosahedron?
Q1. Is it possible to somehow "see" the unsolvability of quintic polynomials
in the $A_5$ symmetries of the icosahedron (or dodecahedron)?
Perhaps this is too vague a question.
Q2. Are there ...
CommunityBot
- 1
15
votes
1
answer
530
views
Dividing a polyhedron into two similar copies
The paper Dividing a polygon into two similar polygons proves that there are only three families of polygons that are irrep-2-tiles (can be subdivided into similar copies of the original).
Right ...
- 17k
25
votes
3
answers
2k
views
Is the Ford-Fulkerson algorithm a tropical rational function?
The Ford-Fulkerson algorithm
Let me recall the standard scenario of flow optimization (for integer flows at least):
Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Consider a digraph $D$ with vertex ...
- 33.8k
3
votes
0
answers
105
views
Techniques for solving linear inequalities
For $n$ real variables $x_1, \ldots, x_n$, I have a bunch of inequalities of form $2 x_i > x_j + x_k$ or $2 x_i < x_j + x_k$, where $i,j,k$ are distinct. My goal is to determine whether this set ...
- 63.9k
1
vote
0
answers
69
views
Polyhedra with equal faces
It is easy to see that for isosceles tetrahedra (https://en.wikipedia.org/wiki/Disphenoid) all faces are equal acute triangles. If we consider regular tetrahedra and attach a regular triangular ...
- 2,858
5
votes
1
answer
204
views
Orienting the dual of the associahedron
Let $A_n$ be the dual simplicial complex to the associahedron on $n$ letters. The complex $A_n$ is thus a simplicial triangulation of an $(n-3)$-dimensional sphere. The vertices of $A_n$ correspond ...
- 44.8k
4
votes
0
answers
46
views
Implementation of Friedman's algorithm of reconstructing simple polytopes
In Finding a Simple Polytope from Its Graph in Polynomial Time, Friedman gave a polynomial time algorithm on reconstructing a simple polytope from its graph. Has this algorithm been actually ...
11
votes
1
answer
211
views
Is it possible for the dihedral angles of a polyhedron to all grow simultaneously?
(Originally on MSE.)
Suppose $P$ and $Q$ are combinatorially equivalent non-self-intersecting polyhedra in $\mathbb{R}^3$, with $f$ a map from edges of $P$ to edges of $Q$ under said combinatorial ...
- 3,068
0
votes
0
answers
39
views
Max-flow modeling with unified vehicle and commodity variables
I am working on a network flow problem that involves routing through a time-space network. The network consists of:
A single source node and a single demand node.
A fleet of vehicles with specified ...
- 63.9k
1
vote
0
answers
51
views
Enumeration of uniform polyhedra
[I already asked this question on MSE (here) but got no answer so I am trying here]
It is known that there are two infinite classes of polyhedra (prisms and antiprisms) together with $75$ uniform ...
- 1,451
0
votes
0
answers
30
views
Application of greedy approach for optimization
I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$
where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
- 23
4
votes
1
answer
146
views
Bounding distance to an intersection of polyhedra
Let $P$ and $Q$ be polyhedra in ${\mathbb R}^m$ with a non-empty intersection. I believe there should exist a constant $C_{PQ}>0$ such that for any point $x\in {\mathbb R}^m$ the following ...
- 109k
3
votes
2
answers
205
views
Bounding distance to a polyhedron
I need to estimate the Euclidean distance from a point $x\in {\mathbb R}^m$ to a polyhedron $P\subset {\mathbb R}^m$ in terms of distances from $x$ to the tangent hyperplanes which define $P$. By a ...
- 1,579
8
votes
2
answers
1k
views
Minesweeper as a linear algebra problem
I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
- 99
0
votes
1
answer
127
views
4 triangular faces 6 vertices not tetrahedron [closed]
I have made a solid and would like to know its' name, volume and related formulas. It is made using a flat potato chip bag. The end opposite the factory seal is sealed perpendicular to the factory ...
- 842
2
votes
1
answer
213
views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
9
votes
2
answers
843
views
How did they come up with the MRRW bound?
Among the good asymptotic bounds in coding theory in the MRRW bound. It is obtained by using the linear programming problem of Delsarte's and providing a solution. The LP problem is
Suppose $C \...
- 232
13
votes
3
answers
725
views
Are there Monohedra with odd numbers of faces?
A monohedron is a convex polyhedron with all faces mutually congruent but with no other symmetry necessarily needed. So obviously, this is a wide class of polyhedra that includes the Platonic solids ...
- 2,370