All Questions
1,021 questions
0
votes
0
answers
890
views
Maximum shortest path problem
I have the following problem. You have a graph and every edge has a certain set of possible weights. The question is to find the assignment of those weight which will maximize the shortest path.
In ...
- 342
14
votes
1
answer
641
views
Subdivision of pentagon into six congruent pieces
I posted this on math.stackexchange, but got no answers.
It is easy to divide a 2-gon into 3 congruent line segments. It is also easy to divide a triangle into 4 smaller triangles that are congruent. ...
- 15.8k
2
votes
0
answers
126
views
Unveiling hidden structures
One way to unveil a hidden structure of a undirected graph - given as an adjacency matrix - is to permute the rows and columns until a pattern with a maximal geometrical symmetry is found. (The ...
- 9,720
5
votes
1
answer
921
views
What makes a geometric construction more or less stable?
I'm not entirely sure if this is "research level" math or not, but I asked on Math.SE and it was suggested I try asking here, so hopefully it's of interest to this community. (Original question on M....
- 151
19
votes
4
answers
1k
views
Applications of linear programming duality in combinatorics
So, I know that one can apply the strong LP duality theorem to specific instances of maximum flow problems to recover some nontrivial theorems in combinatorics, such as Hall's theorem, Koenig's ...
- 997
1
vote
0
answers
1k
views
Number of different combinations in a 0-1 knapsack problem with integer weights [closed]
My question is actually very similar to this other one: Given a vector of positive integers, count the number of combinations which have a sum that produces a different value. But, since this previous ...
- 153
3
votes
1
answer
634
views
Properties of one dimensional null space
Let $\mathcal{G}$ be denote the set of all $3 \times 3$ real symmetric matrices and let $\mathcal{G}^+$ denote the set of all $3 \times 3$ positive semidefinite matrices (see definition).
Let $S: \...
- 31
4
votes
2
answers
722
views
Minimum number of rectangles in a polygon
Given a polygon and dimension $d$, find a minimum partition of rectangles that has either of its dimensions equal to $d$.
Example:
Consider the following diagram:
I want to cover maximum shaded ...
- 175
0
votes
1
answer
124
views
Triangle inside the Closed Curve
For any piece wise smooth, simple closed curve $\gamma$ in the Euclidean plane $E^2$ and fix a point $G$ inside the area circled by $\gamma$.
Show: There exists three points $A,B$ and $C$ on the $\...
- 1,915
1
vote
0
answers
1k
views
Analytic formula for minimizing the maximum inner product of a set of vectors
Given $x_j\in\mathbb{R}^n$, $j=1,\ldots,p$, find
$$
\widehat{w} \in \arg\min_{\Vert w\Vert=1}\max_{1\le j\le p} |\langle w,x_j\rangle|.
$$
I am also interested in the special case where we further ...
- 710
1
vote
1
answer
184
views
Do doubly infeasible Linear Programming problems always have doubly infeasible bases?
Consider a Linear Programming problem in dictionary form,
$$\max\Big\{f^\pi+\!\!\!\sum_{j\in D(\pi)}\!\! d^\pi_jx_j~\Big|~\forall~i\!\in\!B(\pi)~~~ b^\pi_i+\!\!\!\sum_{j\in D(\pi)}\!\! G^\pi_{ij}x_j\...
- 21
5
votes
2
answers
985
views
Automatic proof in Euclidean Geometry using Theory of Groebner Bases
I've done the same question in math.stackexchange here "https://math.stackexchange.com/questions/1938261/automatic-proof-in-euclidean-geometry-using-theory-of-groebner-bases?noredirect=1#...
- 441
7
votes
0
answers
318
views
Status of an open question in Artin's "Geometric Algebra"
In Artin's book "Geometric Algebra", Chapter II, the author states some axioms for geometry (section 1) and then begins to prove some results about the symmetries of the geometry (section 2).
The ...
- 501
0
votes
1
answer
201
views
Recursive linear programming on a linear subset of a simplex
The problem I am working on is:
Given an $n$ dimensional vector $r \in \mathcal{R}^n$, and a convex set $G=\{\mu \in \mathcal{R}^n | \mu_i \ge 0, ~ \mu^T \mathbf{1}=1, ~ A\mu =0 \}$ where $\mathbf{1}...
2
votes
3
answers
1k
views
Quadratic Programming With Piecewise Linear Term
The problem I have can be defined as:
$$
\min \frac{1}{2}\mathbf{x}^T\mathbf{Q}\mathbf{x} + \mathbf{c}^T\mathbf{x}
$$
s.t. linear equality constraints:
$$
\mathbf{Ax=b}
$$
and linear inequality ...
- 131
2
votes
1
answer
180
views
An inequality on cyclic polygon defined by Newton's identities
Let $n$-regular polygon $X_1X_2\cdots X_n$ with the circumcribed circle $(O)$. Let $n$ points $A_1, A_2,\cdots,A_n$ lie on the circle $(O)$. Let $x_{ij}=X_iX_j$ (for $1 \le i<j \le n) $. Let $a_{ij}...
- 1,044
0
votes
1
answer
212
views
How to find out if a polytope contains a sphere?
Given a polytope described by linear inequalities $Ax \le b, x \in \mathbb R^n$, how do you find out if there exist a (non degenerate) sphere of dimension $n-1$ contained in the polytope?
Thanks!
- 225
2
votes
1
answer
137
views
Exist $A_1, A_2,\cdots , A_n$ be $n$ points on a sphere, satisfy if $i-j=l-m$ then $A_iA_j=A_lA_m$
Conjecture: Let $n\geq4$. Is there a set of $n$ non-planar point $A_1, A_2,\cdots , A_n$ be $n$ on a sphere (three-dimensional space) satisfying the conditions: if $i-j=l-m$ then $d(A_i, A_j) = d(A_l, ...
- 1,044
13
votes
1
answer
615
views
Find structure geometry of $A_1, A_2,...,A_n$ such that $\prod_{i<j} A_iA_j$ is maximum
In any triangle we have the well-known inequality:
$$\sin{A}\sin{B}\sin{C} \le \frac{3\sqrt{3}}{8} (1)$$
Signification of inequality (1): Let three points $A, B, C$ lie on a circle then $AB.BC.CA$ ...
- 1,044
1
vote
0
answers
187
views
Strong Duality of Mixed Integer Linear Program
The problem at hand is to optimize a mixed-integer linear program closely related to the maximum flow problem. I would like to reformulate the problem with its dual and I'm concerned with the ...
- 11
3
votes
2
answers
1k
views
SDP relaxation vs LP relaxation
I have a question I hope you might be able to answer.
Let's say we have an integer program for the stable set problem (or clique, not principal).
\begin{equation}
\begin{aligned}
& \text{...
- 342
2
votes
1
answer
171
views
Maximization of Binary Multilinear Fractional Function
Problem: Let $a_{i,j}$, $b_{i,j}\in\mathbb{R}$ for all $(i,j)\in\left[m\right]^2$ such that $a_{i,j}=a_{j,i}$ and $b_{i,j}=b_{j,i}$. Let $z_k\in\{0,1\}$ for $k\in\left[m\right]$. We wish to maximize,
...
7
votes
3
answers
221
views
What is special in dimension $2$ (When characterizing isometries using the cofactor matrix)?
Let $A$ be a real $n \times n$ matrix. Denote by $\operatorname{cof} A$ The cofactor matrix of $A$. By definition, $A (\operatorname{cof} A)^T=\det A \cdot I$.
Thus, it is immediate that $A \in \...
- 6,741
2
votes
3
answers
2k
views
Better tactics for removing redundant constraints than Linear Programming?
After reading:
Detection of Redundant Constraints
It appears that linear-programming is the most commonly known way to remove ALL redundant constraints from a system of inequalities of the form
$$ ...
- 2,689
2
votes
1
answer
529
views
Integer programming and Groebner basis
I enjoyed reading different papers about using Groebner basis to solve integer programming.
Is there any literature about the complexity and/or comparison with other (more classical) methods like ...
- 337
1
vote
1
answer
155
views
Derive a vertex representation of a permutohedron from its linear-inequalities form
Let us define the $n$-permutohedron $P_n$ as the set of all $x\in\mathbb{Q}^n$ such that
$$\sum_{i=1}^n x_i = \binom{n{+}1}{2}\ \ \ \land\ \ \ \forall\,\text{nonempty}\ S\subsetneq\mathbb{N}_n\colon\ ...
user94257
38
votes
1
answer
2k
views
Sofa in a snaky 3D corridor
What is the largest volume object that can pass though a
$1 \times 1 \times L$ "snaky" corridor, where $L$ is large
enough to be irrelvant, say $L > 6$.
...
- 151k
0
votes
1
answer
172
views
An inequality in product space $V$ [closed]
I found an inequality as following: Let $x, y, z$ be three complex numbers then:
\begin{equation*} \frac{1}{2}(|y+z-x|+|x+z-y| + |y+x-z|) \le |x| + |y|+|z|+\frac{1}{2}|x+y+z| \end{equation*} (1)
The ...
- 1,044
2
votes
1
answer
253
views
A generalization of the Tucker circle theorem and the Thomsen theorem associated with a conic
I gave a generalization of the Tucker circle theorem and the Thomsen theorem at here. Now, I give a more generalization of these theorems as following:
Problem: Let $A_1A_2A_3A_4A_5A_6$ be a hexagon, ...
- 1,044
1
vote
1
answer
1k
views
convert absolute form into linear programming problem [closed]
I would like to convert this problem into a Linear Programming Problem :
$\min |x|+|y|+|z|$
subject to $x+y \leq 1$
$2x+z=3$.
The solution to this problem is given chapter and here. But I still ...
- 113
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
4
votes
1
answer
420
views
Does the collection of algebraic/number-theoretic methods applied to Euclidean Geometry have a name?
I am currently writing an essay on the history of geometry. To educate myself on the subject, I sometimes read the following Wikipedia article on the history of Euclidean Geometry. It seems to me that,...
- 57
20
votes
2
answers
2k
views
The geometric median of a triangle
Let $\Omega\subset \mathbb R^n$ be a compact domain of dimension $n$. Define the geometric median on $\Omega$ as the point $m_{\Omega}\in \mathbb R^n$ such that the integral $\int_{\Omega}|x-m_{\Omega}...
- 14.3k
4
votes
0
answers
184
views
Optimal instructions for the modular construction of rectlinear Lego structures
Let $X$ be a compact (or periodic) union of integer translates of unit cubes such that the interior of $X$ is connected. (If it makes any difference, suppose that the dimension $n$ of $X$ is 3.) I am ...
- 15.4k
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
8
votes
1
answer
566
views
Law of sines for tetrahedra
Wikipedia gives a generalization of the law of sines to higher dimensions, as defined in F. Eriksson, The law of sines for tetrahedra and n-simplices. However, this generalization misses an important ...
- 81
2
votes
1
answer
565
views
Pasch axiom and Pythagorean field condition?
I am looking for a reference for the claim that the Pasch axiom is equivalent to the Pythagorean field condition, and with respect to what base theory this should be true.
Since posting the question, ...
- 16.6k
1
vote
1
answer
194
views
Set of General Linear Position with Nonzero Measure
I came to the following question, but I don't have quite a good idea how to approach.
Can a set $A\subset \mathbb{R}^n , n\ge 2$ with nonzero measure be in a general linear position?
I believe that,...
- 909
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 ...
33
votes
3
answers
3k
views
Understanding sphere packing in higher dimensions
In a recent publication by the Ukrainian mathematician Maryna Viazovska the Kepler problem for dimension $8$ and $24$, namely the densest packing of spheres, was solved.
Admittedly it is very ...
user88381
2
votes
0
answers
278
views
A chain of six circles associated with six points on a circle (in Mobius plane) [closed]
I found a conjecture: A chain of six circles associated with six points on a circle (in Mobius plane).
This is a generalization of the last my previous question in Three chains of six circles. (Noting ...
- 1,044
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 & \...
3
votes
0
answers
239
views
A conjecture on six planes [closed]
When I read Cox's Theorem, and Clifford's Circle Theorem and Miquel six circles theorem, I found the conjecture as folowing. And I checked the conjecture by the Geogebra sofware, the conjecture is ...
- 1,044
4
votes
1
answer
1k
views
A new theorem in projective geometry
My question: I am looking for a proof of problem as following:
Introduction: When I research a theorem as following:
Theorem 1: Let $ABC$ be a triangle, let $(S)$ be a circumconic of $ABC$, let $P$...
- 1,044