17 votes
Maximum minimum difference between $f(k+1)$ and average of $f(0), \dots, f(2k+1)$
Consider the absorbing Markov process $X_0,X_1,\dots$ of random nonnegative integers where $X_0 = 1$, and for each $i$, $X_{i+1}$ is drawn uniformly at random from $0,\dots,2X_i$. In log scale, this ...
- 120k
15 votes
Accepted
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
This is a tough question, and I don’t think there’s a definitive answer yet. For some mathematical details, see the following survey articles: https://arxiv.org/abs/1611.01685 https://arxiv.org/abs/...
- 17.3k
11 votes
How did they come up with the MRRW bound?
For linear programming type bounds it is sometimes only possible to give effective bounds (that is bounds that work and are manageable) and what is surprising is that the primitive method often gives ...
- 3,269
11 votes
Formula for volume of a convex polytope
Here is one paper, whose introduction will lead you to others: Lasserre, Jean B., and Eduardo S. Zeron. "A new algorithm for the volume of a convex polytope." arXiv math/0106168 (2001). If you want ...
- 153k
11 votes
Why is modular forms applicable to packing density bounds from linear programming at $n\in\{8,24\}$?
In my understanding, the connection to modular forms came via a result of Cohn and Elkies in their paper "New upper bounds on sphere packings I," Ann. of Math. 157 (2003) 689-714, also on the arxiv. ...
- 2,175
8 votes
Accepted
Definition of packing property
That Def 1 and Def 2 are equivalent is a well-known Conjecture, still open as far as I know. Curiously, you can translate the whole conjecture to the language of commutative algebra, see for example ...
- 30.9k
7 votes
The cone of positive semidefinite matrices is self-dual? (reference needed)
I know you are looking for a reference and you probably know how to prove it (and that the post is old). However, I want to include a short form of the proof for those coming to the post for this ...
- 14.5k
7 votes
Is Binary Integer Linear Programming solvable in polynomial time?
Often called Binary Integer Programming (BIP). Wikipedia: Integer programming is NP-complete. In particular, the special case of 0-1 integer linear programming, in which unknowns are binary, and ...
- 153k
7 votes
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Here is a proof of Conjecture 2. First, we have \begin{split} \sum_{k=1}^n M(n,k) &= \sum_{k=1}^n \sum_{m=k}^n \sum_{d|\gcd(m,k)} d\cdot\mu(d) \\ &= \sum_{m=1}^n \sum_{k=1}^m \sum_{d|\gcd(m,k)...
- 38.3k
7 votes
Accepted
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
You can solve this as a minimum-weight perfect matching problem in a graph with a node for each point and an edge for each pair of points. Because the distances satisfy the triangle inequality, an ...
- 5,774
7 votes
Maximum minimum difference between $f(k+1)$ and average of $f(0), \dots, f(2k+1)$
No proof of an optimum here, but at least a demonstration that one can improve, slightly, on the zero infimum. Let me restrict myself to power law functions, $f(k)=k^\alpha$, $\alpha>0$. We seek $$...
- 201k
6 votes
Accepted
If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?
The application of proximal gradient to this exact problem is considered in (equations (2) and (35) in) the Uncertainty in Artificial Intelligence (UAI) 2019 paper Fast Proximal Gradient Descent for A ...
- 1,547
6 votes
Accepted
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
For $d=2$ the maximal $n$ is $3=d+1$. Indeed, between 4 points $x_1,x_2,x_3,x_4$ either one of them, $x_k$, belongs to the convex hull of three others, then $\langle \theta,x_k\rangle$ can not be the ...
- 115k
5 votes
Strong polynomial algorithm for linear programming
The best known general result is due to Eva Tardos' "A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs", published in 1986. Basically, it says that only bitsizes of coefficients ...
- 14.6k
5 votes
Under what conditions does an Integer Programming problem run in polynomial time?
The way I think about Kannan's algorithm (or, for that matter, any of the several "Lenstra-type" algorithms which present similar bounds as the original Lenstra algo from 1983) is that it's designed ...
- 151
5 votes
Accepted
a linear programming problem
The statement in the gray box is an immediate consequence of Helly's theorem: for each $i$, the set $\{ v\in\mathbb{R}^n\colon\ f_i(v)\geq 0\}$ is convex, and because of $r>n+1$, the condition ...
- 6,151
5 votes
Accepted
Sampling uniformly from the vertices of a polytope
Here is one efficient approach, performing a random walk with a rapid mixing time, that has been implemented for a particular class of polytopes, but which might well be adaptable to a more general ...
- 201k
5 votes
Accepted
Famous theorems that are special cases of linear programming (or convex) duality
To elaborate on M. Winter's comment: Von Neumann's minimax theorem for two-person zero-sum games can be thought of as a consequence of LP duality, although his first proof of the theorem did not make ...
5 votes
Formula for volume of a convex polytope
The volume of the resulting convex polytope is given by the leading coefficient of the Ehrhart (quasi)polynomial if all matrices in your half-space description are rational (that is, have only ...
- 994
5 votes
Accepted
Correct way to conduct equilibrium scaling of linear/integer/MIP program
Regarding integer columns, it means the columns that correspond to integer variables. The $j\in \mathcal{I}$ notation makes that explicit. The idea is that scaling continuous variables preserves ...
- 5,774
4 votes
Accepted
Is the Ford-Fulkerson algorithm a tropical rational function?
Here is an extremely inefficient implementation of Edmonds-Karp (breadth-first search) given as a tropical rational map. (Hopefully I've understood the definition of tropical rational map correctly.) ...
- 7,377
4 votes
Accepted
What does the basis of the null space of the constraint matrix of a flow problem look like?
An illustrated example right-away Not to immediately bore you with lengthy preliminary remarks, let me begin with an illustration which, in a sense, already is an answer in itself. Here is an example ...
- 6,151
4 votes
Better tactics for removing redundant constraints than Linear Programming?
Forgive me for reviving this post, but I felt I should point out that it is a theorem that the complexity of LP and the complexity of removing all redundant constraints is the same. 1997. Telgen, Jan. ...
- 141
4 votes
A question about polytopes related to linear programming
By Farkas' Lemma (https://en.wikipedia.org/wiki/Farkas%27_lemma), $\mathbf{A}{x}\leq \mathbf{b}$ has a solution $\mathbf{x}\in\mathbb{R}^n$ if and only if for all $\mathbf{y}\geq 0$ with $\mathbf{A}^T\...
- 25.9k
4 votes
Accepted
Interior point of a convex polytope
Finding all vertices of the polytope would have the same complexity as the Vertex Enumeration Problem. I do not think that's a practical approach. The polytope is the intersection of the box $0\leq ...
- 1,286
4 votes
Maximize function on rotation matrices
Multiplying by $S = \operatorname{diag}(\pm 1, \pm 1, \pm 1)$ (any combination of signs) leaves the objective function unchanged. So this function has multiple maxima: if $Q$ is one, then $SQ$ is ...
- 20.5k
4 votes
Accepted
Fractional values in linear programming
Yes, this is a known consequence of the fact that there always exists an optimal solution that is basic (an extreme point of the feasible region). This property is the foundation of the simplex ...
- 5,774
4 votes
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
@RobPratt's answer describes a good general-purpose approach. The specific case where edge weights are given by Euclidean distances is also a well-studied problem. The paper A Divide-and-Conquer ...
- 25.8k
4 votes
Accepted
Method for (binary) optimization under constraints
This is the transportation problem in a bipartite network, with a supply of $1$ at each $j$ node and a demand of $t_i$ at demand node $i$. The problem can be solved via linear programming, a minimum-...
- 5,774
4 votes
Accepted
Efficient algorithm for graph problem
If $v_1$ and $v_l$ are fixed then constructing a minimum weight breadth-first tree of height $l{-}1$ and finally optimally attach vertex $v_l$. Iterating over all candidate pairs of $v_1$ and $v_l$ ...
- 13.9k
Only top scored, non community-wiki answers of a minimum length are eligible