**28**

votes

**3**answers

2k views

### What is the best way to peel fruit?

A mango made me wonder about this. (See also this question, which is in a similar spirit.)
Fix $L >0$ and a smooth body (possibly nonconvex—pears or bananas are fair game!) $B \subset \mathbb{R}^3$...

**7**

votes

**2**answers

1k views

### Conic hulls and cones

Suppose I have a number of vectors in $\mathbb{R}^n.$ The first question is: what is the most efficient algorithm to compute their "conic hull" (the minimal convex cone which contains them)? The next ...

**25**

votes

**5**answers

2k views

### When does symmetry in an optimization problem imply that all variables are equal at optimality?

There are many optimization problems in which the variables are symmetric in the objective and the constraints; i.e., you can swap any two variables, and the problem remains the same. Let's call such ...

**17**

votes

**3**answers

1k views

### “Entropy” proof of Brunn-Minkowski Inequality?

I read in an information theory textbook the Brunn-Minkowski inequality follows from the Entropy Power inequality.
The first one says that if $A,B$ are convex polygons in $\mathbb{R}^d$, then
$$ m(...

**7**

votes

**4**answers

1k views

### Is there a name for the matrix equation A X B + B X A + C X C = D?

I happen to be working on a problem that reduces to solving the following equation:
$$\mathbf{A X B} + \mathbf{B X A} + \mathbf{C X C} = \mathbf{D}$$
where A through D are known matrices ( A, B, D ...

**6**

votes

**5**answers

2k views

### Application of polynomials with non-negative coefficients

Question 1: Are there any deeper applications (in any field of mathematics) of polynomials (with possibly more than one variable) over the real numbers whose coefficients are non-negative? So far I ...

**16**

votes

**6**answers

5k views

### Solving NP problems in (usually) Polynomial time?

Just because a problem is NP-complete doesn't mean it can't be usually solved quickly.
The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...

**12**

votes

**4**answers

475 views

### Minimal-length embeddings of braids into R^3 with fixed endpoints

(Apologies in advance for any imprecision in the following; I am a computer scientist and regret never having taken an actual course on topology.)
One way to define the pure braid group $P_n$ is as ...

**10**

votes

**2**answers

516 views

### Optimal inspection path on a sphere

Suppose you would like to "inspect" every point of a unit-radius
sphere $S \subset \mathbb{R}^3$ by walking along a path $\gamma$
on $S$, but you can only see a distance $d$ from where you stand.
...

**5**

votes

**1**answer

2k views

### Non-negative quadratic maximization

For a given symmetric and positive semidefinite $n \times n$ matrix $A$, we want to solve the problem $$\max_{||x|| = 1, \ x\geq 0} x^T A x.$$
Here, $x\geq 0$ indicates that $x$ must be component-wise ...

**3**

votes

**4**answers

2k views

### Minimizing the modulus of a polynomial around a circle

I'm probably missing something elementary here, but I guess the only way to be sure is to ask here.
Now, I have encountered a situation where given an nth-degree polynomial $p_n(z)$ with complex ...

**14**

votes

**4**answers

483 views

### Maximum of the Vandermonde determinant / minimum of the logarithmic energy

The problem is to find the asymptotics (as $n\to\infty$) of the maximum (say $M_n$) of the Vandermonde determinant
$$V_n:=\prod_{0\le i<j\le n-1}(a_j-a_i)
$$
over all $a_0,\dots,a_{n-1}$ such ...

**10**

votes

**1**answer

297 views

### Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...

**4**

votes

**0**answers

311 views

### The Gömböc and monostatic objects

This made the popular news a few years ago. Summary: it's the first homogeneous, convex solid to be found with only one stable and one unstable mechanical equilibrium when resting on a flat surface. I ...

**4**

votes

**1**answer

140 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 ...

**3**

votes

**2**answers

214 views

### Generalized Moore Graphs

A generalized Moore graph - as defined by Cerf, Cowan, Mullin and Stanton - is one for which the girth G and diameter D satisfy G ≥ 2D - 1. These graphs retain many of the optimal properties of Moore ...

**9**

votes

**4**answers

541 views

### The distribution of the shortest path through $n$ points

In the big picture, I'd like to know: if I sample $n$ points uniformly at random in the unit square, what is the probability that the shortest path that visits each one of them is very small?
More ...

**4**

votes

**2**answers

561 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 ...

**3**

votes

**1**answer

860 views

### Symplectic block-diagonalization of a real symmetric Hamiltonian matrix

Given a $2n\times 2n$ real, symmetric, Hamiltonian matrix $W$ (anticommutes with the symplectic metric), is there an orthogonal, symplectic matrix $R$ such that $R^\top WR$ is block-diagonal?
Being ...

**3**

votes

**2**answers

499 views

### Cubic graphs which are “difficult to navigate”

Suppose I am inside a finite, weighted cubic graph without loops, with no information regarding its layout, including the number of vertices or distances to the adjacent vertices. I want to reach a ...

**2**

votes

**1**answer

113 views

### Optimizing finite-length approximations to space-filling loops

Take a loop in the unit disk D^2, with length l where length is defined as the supremum of the lengths of piecewise linear approximations. What is the smallest r such that every radius-r subdisk of D^...

**1**

vote

**0**answers

85 views

### Optimal Control / Hamilton-Jacobi-Bellman Equation

I face the following optimal control problem: let $X=(X_{1},X_{2})^{\top}$ be a controlled (Ito-)process with dynamics
$dX_{1}(t)=\big(X_{1}(t)\,\mu_{1} + a(t)\big)\;dt + X_{1}(t)\,\sigma_{1}\;dW_{1}(...