All Questions
739 questions
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 ...
- 41
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
4
votes
2
answers
250
views
Build a topological polytope with a specified CW-structure
I am a topologist and not quite familiar with the tools for building a polytope. I would like to build some topological polytope which is an somewhere in between permutohedron and associahedron which ...
- 2,023
4
votes
2
answers
1k
views
Set Cover:Greedy vs LP
Hi
Both, the greedy and the LP approach for Set Cover give a O(log n) approximation. Is there some inherent difference on the two approximation approaches?
thanks
- 239
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 ...
- 1,579
4
votes
1
answer
94
views
Is the space of Euclidean polyhedra with a fixed $1$-skeleton connected?
Let $\mathcal{A}_\Gamma$ be the space of convex (non-degenerate) Euclidean polyhedra with $1$-skeleton a certain polyhedral graph $\Gamma$. This space can be seen as a subset of $\mathcal{Gr}_2(\...
- 285
4
votes
1
answer
2k
views
Under what conditions does an Integer Programming problem run in polynomial time?
Given $AX\leq B$ where $A\in\Bbb Z^{m\times n}$,$B\in\Bbb Z^m$ finding $X\in\Bbb Z^n$ where $m\geq n$ is the integer programming problem. If $A$ is totally unimodular then the problem is solvable in ...
- 13.9k
4
votes
2
answers
212
views
combinatorial and linear duality
Let $S$ be a finite set, and let $W$ be a nonempty set of subsets of $S$; we will identify every subset of $S$ with its characteristic function, a 0-1 vector in $\mathbb R^S$. The combinatorial dual $\...
- 987
4
votes
1
answer
320
views
Seeking criteria for "threadable" pairs of centrosymmetric polyhedra
Let $A$ and $B$ be origin-centered centrosymmetric polyhedra in $\mathbb{R}^3$:
"for every point $(x, y, z)$ [...] there is an indistinguishable point $(-x, -y, -z)$."
Say that $A$ and $B$ are ...
- 151k
4
votes
3
answers
1k
views
Number of Hyper-cube cuts
In how many ways a single hyperplane can cut a hypercube? Two "ways" are considered different, if the sets into which they divide vertices of the hypercube are different. So e.g. a line can cut 2-...
- 51
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?
- 1,182
4
votes
1
answer
142
views
On polyhedrons with specified numbers of congruent faces
Basic question: Given 3 integers n, n1 and n2 such that n1+n2 = n, to form an n-face polyhedron such that n1 of its faces are mutually congruent and the remaining n2 faces are different but congruent ...
- 5,979
4
votes
1
answer
131
views
Any visualization software for the intrinsic metric of a convex polyhedron?
I'd like to find a visual simulation of what it would be like to 'live' in a polyhedron with the intrinsic, piecewise-Euclidean length metric. Of course, to make it easier to visualize, I'd prefer to ...
- 3,359
4
votes
2
answers
4k
views
Dual Norm For Sum of 2-Norms
What is the dual of a norm that is the sum of two-norms? Specifically, say we have the following norm for $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}_i \in \mathbb{R}^{m \times n}$
$\|\mathbf{x}\| = ...
4
votes
1
answer
360
views
On Dehn's infinitesimal rigidity theorem
Dehn's theorem states that any simplicial strictly convex polyedron P in Euclidean 3-space is infinitesimally rigid (that is, any non-trivial first order deformation of P induces a variation of its ...
- 61
4
votes
1
answer
966
views
Solving for Hamiltonian path with constraints on allowable routes through vertices
Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...
4
votes
1
answer
2k
views
solving multiple linear programming problems with the same set of constraints
Hi,
I need to solve a set of linear programs of the form:
Problem $i$: $\quad \max c_i \cdot x$ s.t. $ A x \leq b$.
The $c_i$'s are different vectors so each problem has a different objective ...
- 560
4
votes
1
answer
174
views
Finding Motzkin's original paper on copositive quadratic forms
I am currently in the process of writing my thesis about copositive matrices and would like to write a chronological narrative about the ascent of these matrices to the prominent place they have today ...
- 153
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
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
4
votes
1
answer
694
views
$\mathcal{H}$-polyhedron under a linear map
Let $P = \{ x \in \mathbb{R}^n \mid Ax \leq b \}$ be a (bounded) polyhedron for $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$, $n,m > 0$.
Moreover, let $M \colon \mathbb{R}^n \to \...
- 321
4
votes
1
answer
3k
views
optimization of inverse matrix with constraint on matrix elements
everyone! I have this optimization problem with constraint.
$D$ and $T$ are symmetric matrices, where T is known and D is the unknown parameter.
$x$ and $v$ are two known p-dimensional vectors.
The ...
- 49
4
votes
1
answer
143
views
Polyhedra with minimal edge length
Given a fixed volume and fixed surface area I would like to construct polyhedra that minimize the total length of the edges. This seems like a straight-forward problem to solve by brute force for ...
- 41
4
votes
2
answers
2k
views
Simplified knapsack problem
There is a problem that I can not solve.
Given a set of items (each item has some integer weight) we have to fill bag with some number of copies of these items, with the only restriction that the ...
- 41
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 ...
- 183
4
votes
2
answers
242
views
Clustering of vertices in an $n$-dimensional cube
Consider the vertices of an $n$-dimensional cube. The distance between two vertices is measured as the minimum number of edges between the two vertices. Now consider a subset of these vertices.
If we ...
- 41
4
votes
1
answer
204
views
Reference: Packing under translation is in NP
I am looking for a reference for a result that I am aware of.
Let me describe the result.
Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP
time, if $p_1,\ldots,p_n$ can be ...
- 479
4
votes
1
answer
1k
views
What is the average area of the shadow of a convex shape taken over all possible orientations?
If we take a sphere, its surface area is exactly 4 times the area of its shadow. How can it be generalised for any convex shape?
- 343
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
4
votes
1
answer
585
views
How to implement linear constraints that include several absolute values
Dear all,
I am trying to implement a linear constraint that includes several absolute values in the form: Abs(A) + Abs(B) + Abs(C) + Abs(D) + ... = 1
Since the minimization problem includes quite a ...
- 41
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 ...
- 41
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
4
votes
1
answer
750
views
submatrix of a given size with maximum frobenius norm
Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
- 859
4
votes
1
answer
288
views
Equivalent method for maximum likelihood estimation of covariance parameters
My goal is to estimate the parameters of a covariance matrix $\Omega$, by maximizing the following log-likelihood function:
$$\log L(\vec\tau, \rho, \sigma \mid W, X) = -m\ln(\left | \Omega \right |) ...
- 141
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 ...
4
votes
0
answers
82
views
Classification of space-filling (by identical copies) convex polyhedra in R^3
Is the classification of space-filling (by identical copies) convex polyhedra in R^3 is known ?
There are only 5 "parallelohedra" - filling by translation.
But if relax that property to ...
- 24.9k
4
votes
0
answers
147
views
Name for facet of a cone containing all but one edge
Let $C \subseteq \mathbb R^n$ be a polyhedral cone, so generated by its edges ($1$-dimensional faces) and $F \subseteq C$ a facet (codimension $1$ face) of it containing every edge except $e$. In ...
- 27.8k
4
votes
0
answers
202
views
$\ell^1$-norm minimization duality
I am looking for an explicit description and discussion of the dual of the $\ell^1$-norm minimization problem $\lVert A x\rVert_1\to\min$, where $A$ is a matrix, and $x$ belongs to the $n$-simplex $\...
- 17k
4
votes
0
answers
539
views
Using Linear Programming as an iterative procedure
Suppose, we have a linear program and an optimal solution to it. Suppose now, we get a new constraint. We want to obtain an optimal solution to the given linear program extended by that new constraint....
- 391
4
votes
0
answers
153
views
Perimeters of nested convex spherical polygons
I seek a reference—not a proof—that if $P_1$ and $P_2$
are two convex polygons on a sphere composed of geodesic segments,
contained in a hemisphere, and
$P_1 \subseteq P_2$, then the ...
- 151k
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
0
answers
2k
views
Regular cross-sections of a dodecahedron; analogous sections of 4-polytopes
One can intersect a dodecahedron with a plane and
obtain an equilateral triangle, a square, a regular pentagon,
a regular hexagon, and a regular decagon:
&...
- 151k
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 ...
- 41
3
votes
2
answers
877
views
Polyhedra Classification
The following is inspired by this question. From time to time I search the web for tables of polyhedra, but without much success. Part of the problem is that there are many non-equivalent questions ...
- 3,081
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 ...
- 491
3
votes
2
answers
437
views
convex polytope integer points
is there a simple proof for the following lemma:
An unbounded convex polytope (defined by linear constraints) has either zero integer points or infinite many integer points.
- 39
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 ...
- 151
3
votes
2
answers
791
views
complexity of finding optimal matchings of given fixed size
It is known, that maximal matchings (i.e. matchings with the maximal number of edges) and optimal matchings (i.e. matchings for which the sum of edge weights is optimal) can be calculated in ...
- 13.2k
3
votes
2
answers
10k
views
linear programming with OR restrictions
Hi all. I have a linear program with the restriction that every variable can be zero or greater than or equal to a positive constant. That is:
minimize: $w^Tx$
subject to: $Ax=b$, $Cx \le d$ and for ...
- 57
3
votes
1
answer
533
views
Solving a system of linear inequalities
Consider the following system of inequalities:
$Ax=b$;
$x\geq 0$;
A is a $m\times n$ (non-square) and sparse matrix in which some part of entries are rational. How this system can be solved without ...
- 221