All Questions
29 questions with no upvoted or accepted answers
6
votes
0
answers
74
views
Roundest polyhedra: how well can we bound the edge count of their faces?
By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...
- 3,612
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
163
views
Convexified threshold of a function
Upd. The question in a nutshell: find convex set on plane which is «closest» to a given non-convex set.
It is given integrable function $0\leq f(x,y)\leq 1$ with bounded support: $f(x,y)=0$ when $x^2+...
3
votes
1
answer
208
views
Approximation of Poset
Let $(X,\leq)$ be a poset, $X=\{x_1,x_2,...,x_n\}$. Preference matrix $\textbf{P}=[p_{ij}]$ (which is known and fixed), satisfies $p_{ij}=1-p_{ji},p_{ii}=\frac{1}{2}$, and
$$\forall i \neq j, x_i \leq ...
- 61
3
votes
0
answers
121
views
Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$
Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix).
Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...
- 205
3
votes
1
answer
269
views
Optimal rule for multiple stopping times for defect finding
Suppose a quality inspector is inspecting $b$ black amongst which $d_B$ are known to be defective and $w$ white gadgets amongst which $d_W$ are known to be defective. The gadgets come down along an ...
- 2,239
3
votes
2
answers
287
views
Probability that the solution to a combinatorial optimization problem changes after random modifications
Given a combinatorial optimization problem, say the Traveling Salesman Problem, the optimal solution is a set of elements (edges in this case) that satisfy certain constraints (constituting to a ...
- 13.2k
2
votes
0
answers
120
views
How to solve $\min_{\mathbf{x}\in \{\pm 1\}^N} \lVert \operatorname{sign}(\mathbf{Wx}) - \mathbf{y} \rVert_2^2$ where $\mathbf{y}\in \{\pm 1\}^N$?
Given the matrix $\mathbf{W} \in \mathbb{R}^{N \times N}$ and the vector $\mathbf{y} \in \{\pm 1\}^N$, how to solve
$$\min_{\mathbf{x}\in \{\pm 1\}^N} \left\| \operatorname{sign}(\mathbf{Wx}) - \...
- 175
2
votes
0
answers
119
views
Modified quadratic assignment problem
Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that
$$\left\Vert Y^{T}...
- 133
2
votes
0
answers
56
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
- 2,772
2
votes
1
answer
240
views
Basis pursuit algorithms for exponentially large matrices?
Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is
$$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...
- 21
2
votes
1
answer
329
views
Worst case performance of heuristic for the non-Eulerian windy postman problem
The windy postman problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in ...
- 13.2k
2
votes
1
answer
710
views
$0$-"norm" minimization with least-squares regularization
I have the following optimization problem in $\mathbf{x} \in \mathbb{R}^{K \times 1}$
$$\min_{\mathbf{x}>0} \quad \|\mathbf{A}\mathbf{x}\|_0 + \alpha \|\mathbf{B}\mathbf{x}-\mathbf{c}\|_2^2$$
...
2
votes
0
answers
81
views
Solving Mixed-Integer Non-Linear Optimization Problem
I would like to solve the following optimization problem:
\begin{array}{ll}
\underset{x_{i}\geq0,\, \pi_{i}\in\{0,1\}}{\text{minimize}} & \displaystyle\sum_{i=1}^n x_i\\
\text{subject to} & ...
- 21
2
votes
0
answers
46
views
What is known about the relation of the multiple salesman problem and the travelling saelsman problem?
The travelling salesman problem (TSP) is well known (https://en.wikipedia.org/wiki/Travelling_salesman_problem). Let us look at the Euclidean TSP throughout this question.
There is a generalization ...
- 61
1
vote
1
answer
86
views
Complexity of calculating the optimal amalgamation of an optimal cycle-cover
Let $G(V,E)$ be a complete symmetric graph with positive edge weights and let further $\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$ be the minimum-weight vertex-disjoint cycle cover.
The set $E$ of ...
- 13.2k
1
vote
0
answers
96
views
Relationship between Wasserstein projections and metric projections in a linear space
Let $(X,d)$ be a metric space, $x\in X$, and $Y\subset X$ is a closed set. Assume that $X$ is also a real vector space, so that we can form linear combinations over $\mathbb{R}$, but I do not assume ...
- 13
1
vote
0
answers
38
views
Structural properties of polytopes for mainstream integer or linear programs
Are there any papers/textbooks/monographs that describe distinguishing properties of the polytopes that arise when solving the linear relaxation of well-known integer programs? For example, it is ...
- 4,049
1
vote
1
answer
444
views
Looking for an efficient way of maximising 'pair scores' for subset of 30 selected from 50 to 10 000 objects
Context: I have a tiling program that uses a directed breadth first search algorithm. It is 'directed' by what I call 'pair scoring'. There are $N$ polyforms (pieces) used in the tiling. I have an $N\...
- 613
1
vote
0
answers
37
views
Asymptotics for a random set cover problem
Suppose you are given a positive integer $k$ and a probability distribution $f$ on the positive reals. I am interested in the limiting behavior of the following process as $n\to\infty$:
Create an ...
- 4,049
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
0
votes
0
answers
22
views
Alignment of unit vectors under graph-neighbor constraints with a global vector
Statement
Let $G = (V, E)$ be a connected, unweighted, and undirected graph with $n$ nodes, represented by its adjacency matrix $A$. Suppose each node $i$ is associated with a unit vector $ \mathbf{v}...
0
votes
1
answer
236
views
Solving a 0-1 quadratic matrix inequality
I am working on a binary optimization problem. So far I have derived the following constraint functions.
\begin{align}
\begin{bmatrix} \left( P + \sum_{i=1}^n (\sum_{j=1}^n x_{i, j} \alpha_j) e_i e_i^...
- 11
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3
0
votes
0
answers
68
views
Optimal top-k column subset
Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\...
- 101
0
votes
0
answers
96
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
- 29
0
votes
0
answers
127
views
Maximizing a vector after a series of matrix multiplications
Problem Statement
Let's say we have a set of $n\times n$ matrices $X=\{M_1,\ldots,M_r\}$ and weights of these matrices $\{w_1,\ldots,w_r\}$ along with a set of "initial vectors" $\{v_1,\...
- 509
0
votes
0
answers
68
views
Under which conditions discrete versions of convex\concave function are submodular/supermodular?
I have $f(x)$ with $x \in [0,1]$ and $f(x)$ is convex, then, under which conditions discrete function which is defined as $f(x_h)$ on discrete subset of $[0,1]$, for example, $x_h \in \{0, h, 2h, \...
- 355
0
votes
0
answers
47
views
Complexity of optimizing a bi-objective function with integer constraints
I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...
- 121