Questions tagged [combinatorial-optimization]
Combinatorial optimization typically deals with optimizing over a finite set of objects that have some combinatorial structure (e.g. trees, matchings, matroids). Approximation algorithms, polyhedral methods, and integer programming are all on topic.
436
questions
2
votes
1
answer
153
views
Combinatorial process on multisets of integers
Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments:
We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
2
votes
0
answers
108
views
What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph
By a classical theorem of Nash-Williams, the edges of every connected $n$-vertex planar graph can be covered by three trees $T_1,T_2$ and $T_3$. Does anyone know of any results from an article or a ...
7
votes
1
answer
349
views
Vectors with minimal Hamming weight in a rational vector space?
Suppose given $n\ge 1$ and a subspace $U$ in $\mathbb{Q}^n$. It is given as $\mathbb{Q}$-span of certain known vectors.
For $x \in U$, we let the Hamming weight of $x$ be the number of its nonzero ...
3
votes
1
answer
141
views
Combinatorial Euclidean geometry problem
Let $\mathcal{S}^d_{\epsilon}$ be the collection of all sets $S:=\{\mathbf{x}_1, \mathbf{x}_2, \ldots \mathbf{x}_{d+1}\}$ of $d+1$ points in a $d$-dimensional Euclidean space such that, for a given ...
2
votes
0
answers
64
views
Minimizing a certain norm of the identity operator on $\mathbb R^2$
$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
5
votes
1
answer
316
views
On a certain norm of the identity operator on $\mathbb R^2$
$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
1
vote
0
answers
45
views
Barycentric coordinates of weighted edges
Given $K_n$ with weighted edges, we can fix an edge $e_{AB}$, iterate over all non-adjacent edges $e_{CD}\in E\setminus e_{AD}$ and record how often $e_{AB}$ was in the lightest, intermediate or ...
1
vote
0
answers
42
views
Methods for useful visualisations of complete weighted graphs
Question:
which methods for visualising complete weighted and symmetric graphs, i.e. $K_n$, are useful in the sense that they can aid in mathematical research?
The Traveling Salesman Problem may ...
1
vote
0
answers
33
views
Calculating vertex weights via mutually tangent circles of triangles
given a metric graph with positive edge weights $\left|e_{ij}\right|$ a standard task, especially in the context of the Traveling Salesman Problem, is to calculate $\max\sum\limits_{i=1}^n\omega_i:\ \...
6
votes
1
answer
165
views
Subsets of a ball/sphere with the largest sum of distances
$\newcommand\R{\mathbb R}\newcommand\S{\mathbb S}$Let $B_d$ and $S_{d-1}$ denote, respectively, the closed unit ball and the unit sphere in $\R^d$. Let us say that a finite subset $F$ of $B_d$ is ...
1
vote
0
answers
100
views
The earliest discrete optimization problem
What is the earliest example of anything that could be considered a discrete optimization problem? I can find plenty of examples of ancient continuous optimization problems (e.g. Dido's isoperimetric ...
6
votes
2
answers
408
views
Snake algorithm that minimizes straight lines
How can I find the non-self-intersecting loop that uses the least amount of straight lines (curves left/right as often as possible every turn) and still loops back on itself?
Here's an example we have ...
2
votes
2
answers
372
views
Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$
Let $S$ be a set of $n \gg 1$ points lying on the interval $[0,1]$. Given a point $p\in[0,1]$, let $S_p\subseteq S\times S$ be the set formed by all pairs of points $(x,y)$ with $x,y\in S$, such that ...
2
votes
0
answers
98
views
Sparse signal recovery (nonlinear case)
Let $K \subset \mathbb{R}^n$, it may be that $K$ is "very thin" (e.g. $K$ is a $k$-dimensional affine subset of $\mathbb{R}^n$, with $k \ll n$). I'm interested in the case where $K$ is ...
0
votes
1
answer
316
views
Expectation of the ratio of two discrete random variables with combinatorial constraints
We are given a set $S=\{1, 2, \ldots, n\}$ where $n\gg 1$, and for all indices $1\le i \le n$, $i$ is associated with a real value $\alpha_i\!\cdot\! v_i$, where $\alpha_i\in[0,1]$ and $v_i\in(0,1]$.
...
0
votes
1
answer
59
views
Bounding the ratio of the $\ell_1$-norms of two real-valued $n$-vectors as a linear combination of their $n$ element-wise ratios
Let $a_1, a_2, \ldots a_n$ and $b_1, b_2, \ldots b_n$ be two sequences of $n\gg 1$ real numbers such that, for all $1\le i\le n$, we have $0<a_i \le b_i\le 1$. Let the ratio $R$ defined as follows:
...
2
votes
2
answers
276
views
Combinatorial optimization problem with interdependent constraints on points in $[0,1]$
We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...
1
vote
1
answer
93
views
Weak submodularity for consecutive indices
Let $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ be defined by $f(x,y) = \frac{x^2}{y}$. Let $X = \left\lbrace x_1, \dots, x_n\right\rbrace \subseteq \mathbf{R}$, $Y = \left\lbrace ...
7
votes
3
answers
263
views
Shrinking subset and product
Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that maximizes $|...
1
vote
1
answer
111
views
Shrinking subset with disjoint unions
Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be disjoint finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that ...
2
votes
0
answers
33
views
Algorithm for lightest unnested planar vertex-disjoint cycle-cover
Question:
given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$,
what is the ...
12
votes
0
answers
12k
views
A New York Times tiles-based graph theory question
The New York Times has a daily puzzle named Tiles that works as follows. Start with $m$ squares (in the official version, this is 30, in a 6x5 grid), and a set of $p>4$ possible patterns (typically ...
3
votes
1
answer
394
views
Symmetric distribution optimization problem of distances between points in $[0,1]$
Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $x, y, z$ the outcomes of three i.i.d. random variables $X, Y, Z$ with distribution $\mathcal{D}$, sorted in increasing order, ...
2
votes
1
answer
216
views
Probability distribution optimization problem of distances between points in $[0,1]$
Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $X, Y, Z$ three i.i.d. random variables with distribution $\mathcal{D}$, and $T$ a random variable uniformly distributed in $[...
2
votes
0
answers
85
views
Optimal paths in set-weighted graphs
Let $G = (V,E)$ be an $n$-vertex graph, let $R$ be a finite set (to be specific, let us assume that $R = [n]$), and let $W : V \rightarrow 2^R$. Let us call the pair $(G, W)$ a set-weighted graph.
Now ...
0
votes
0
answers
124
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,\...
5
votes
0
answers
198
views
Existence of a honeycomb composed by nearly-hyperspherical $d$-dimensional cells having the same shape and size
Let $\mathcal{H}$ the class of all honeycombs composed by $d$-dimensional cells $C$ having all the same shape and size in a $d$-dimensional space $\mathcal{S}$.
Let $s(C)$ and $\ell(C)$ be ...
4
votes
1
answer
358
views
Trade-off between hypervolume and diameter of $d$-dimensional shapes having a hypercubic smallest bounding box
Given any $d$-dimensional shape $X$, let $V(X)$ be its $d$-dimensional volume, and let $\ell(X)$ be the length of the longest line segment connecting two points of $X$.
Let $\mathcal{S}_C$ be the set ...
1
vote
0
answers
35
views
Directed vertex-disjoint 3-cycle covers from Windy Postman tours?
It is a result of Zaw Win (paywall) that optimal Windy Postman tours in eulerian digraphs can be calculated in polynomial time.
Bodo Manthey has shown that directed 3-Cycle Covers are APX hard to ...
2
votes
0
answers
38
views
Optimal Directed Graph with Maximum Number of Interactions
Definitions:
The number of interactions of a directed graph $(V,E)$, denoted by $\operatorname{inter}(V,E)$ is defined by
$$
\operatorname{inter}(V,E) = \sum_{e,f\in V} I_{\gamma{[e,f]}},
$$
where $...
0
votes
1
answer
57
views
Implementing Bemporad optimization algorithm
I need to reproduce the results of a relatively old paper of a paper and one of the steps is to solve an IQP problem, the algorithm suggested is this one. Which I don't know it's the best way to do it ...
2
votes
3
answers
290
views
Geometric probabilistic problem on triangles on a plane
We are given a triangle $T$ on a plane $P$, with sidelengths $a$, $b$ and $c$, where $c \ge b \ge a > 0$. A straight line $L$ on $P$ is selected uniformly at random from the set of all the ...
3
votes
1
answer
249
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 ...
1
vote
0
answers
74
views
SDP relaxation vs. Monte Carlo for MaxCut: which one performs better?
the Goemans Williamson SDP relaxation of the MAXCUT problem famously gives a polynomial approximation ratio of .87856 for the MAXCUT on regular graphs.
Another popular approach to obtain efficient ...
1
vote
0
answers
52
views
Reductions to the MAX-3-DCC Problem
I am currently working on the Max-3-DCC problem that asks for the heaviest vertex-disjoint cycle cover of weighted directed graphs.
The problem has been reduced to 3-SAT in 1979 by L. Valiant in his ...
4
votes
0
answers
244
views
Distance properties of the permutations of a set of points in a Euclidean space
We are given a set of $n$ distinct points $S=\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$ in a Euclidean space $\mathbb{R}^d$, where the distance between two points $\mathbf{x}_i,\mathbf{x}_j\...
0
votes
1
answer
173
views
Relationship between cycle length, number of chords, and number of induced $P_{4}$ subgraphs of the cycle
I was wondering if there was a known relationship between the length of cycle, the number of chords of the cycle, and the number of induced $P_{4}$ subgraphs of the cycle.
Here, I am referring to ...
0
votes
1
answer
116
views
Relaxing Meyniel graphs: condition for strongly perfect instead of very strongly perfect
A Meyniel graph, $\mathcal{G}$ is a graph in which every cycle of odd length at least 5 has at least 2 chords.
First off, I have a technical question which is very important to me:
what is meant by ...
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 ...
1
vote
1
answer
141
views
Bound for multinomial expansion involving Poisson random variables
Let $x_i, i=1, \ldots n$ be Poisson random variables with parameters $\lambda_i$ correspondingly with condition that $\sum_{i=1}^nx_i=T$. Due to linearity of the expectation one can write:
$$
E\left(\...
5
votes
1
answer
394
views
What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?
Also asked on MSE: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?.
Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=...
5
votes
1
answer
436
views
Extending submodular functions from a sublattice
This came about when I was studying the connection between matroids and strong
greedoids, but it has broken through into a subject I am not particularly
familiar with: submodular functions on lattices....
0
votes
1
answer
167
views
Removing linear term in Quadratic assignment problem
Let us consider the following Quadratic assignment problem:
\begin{equation}
\tag{QP1}
\max_{\begin{matrix}x_{ij}\in\{0,1\} \\ \forall j \sum_i x_{ij}=1 \\ \forall i \sum_j x_{ij}=1 \end{matrix}} x^...
2
votes
0
answers
62
views
Path-covering for vertex-transitive graphs
I have the following dummy problem:
Claim - There exists $N$ such that for $n > N$, if $G_n$ be a connected directed vertex-transitive graph with $n$ vertices, then there exists a set $S$ of paths ...
1
vote
1
answer
108
views
Embedding of spheres which satisfies intersection rules
Let $S = \{S_1, \dots ,S_n\}$ be a finite set of $d$-dimensional spheres with the same radius, and let $E$ be a combination of intersections between them, where an intersection is a rule of the form $...
4
votes
1
answer
333
views
Minimization of a discrete valued function
$$
\min_{f} \sum_{i=1}^n \max \left( 0, 2f(i) - f(i-1) -f(i+1)\right),
$$
where the minimum is taken over all the functions $f$ from $\{0,1,2,\ldots,n+1\}$ to $[0,x]$, $x <1$, such that $f$ is non-...
1
vote
1
answer
139
views
Monge's solution to the 'transporting earth' problem
In Schrijver's A course in combinatorial optimization (page 49, Application 3.3), I came across the transporting earth problem which is quoted below (replaced the French text by its English ...
2
votes
1
answer
225
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{...
0
votes
1
answer
111
views
Optimal partition search
Given an integer $n$, and 2 real sequences $\{a_1, \dots, a_n\}$ and $\{b_1, \dots, b_n\}$, with $a_i$, $b_i$ > 0, for all $i$. For a fixed $m < n$ let $\{P_1, \dots, P_m\}$ be a partition of the ...
7
votes
3
answers
487
views
Minimum number of swaps needed to 'group' a sequence?
Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...