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.
480 questions
1
vote
0
answers
37
views
Prove rigorously a constraint on the efficiency of intermediate segments in a polygonal chain over a regular $k$-grid
Let $k, r \in \mathbb{N}$ with $k \ge 2$ and $r \ge 3$, and let $n_1, n_2, \ldots, n_k \in \mathbb{N}$ satisfy $3 \le n_1 \le n_2 \le \cdots \le n_k$.
We define
${G_n}^k := \{0,1,\ldots,n_1-1\} \times ...
- 1,965
4
votes
1
answer
278
views
On the number of $0$-$1$ vectors with pairwise distinct sums $v_i + v_j$
Let $n \ge 1$. A set of vectors $v_1, \ldots, v_m \in \{0,1\}^n$ is called admissible if all pairwise sums $v_i + v_j$ (with $1 \le i \le j \le m$) are distinct. We want to find the number $a(n)$, ...
- 13.5k
0
votes
1
answer
117
views
Optimal probing problem
We are provided with a set of $n$ targets.
Each target is characterized by a utility value.
We know the distribution of the utility value for each target, but do not know its current value.
Therefore, ...
- 327
10
votes
1
answer
269
views
Minimum number of blocks needed to make the path unique
Given a number $n$ and an $n\times n$ grid. Consider a connected path from the lower left corner to the upper right corner. Here, a path means a series of adjacent blocks that do not revisit any ...
- 1,153
1
vote
2
answers
461
views
Largest 3-zero-sum-free subset in $(\mathbb{Z}/4\mathbb{Z})^n$?
I’m investigating the largest subset $H \subseteq (\mathbb{Z}/4\mathbb{Z})^n$ with no three distinct vectors $x, y, z \in H$ such that $x + y + z \equiv 0 \pmod{4}$ (pointwise addition), as posed by ...
- 11
17
votes
1
answer
917
views
A combinatorial problem about piles that sounds easy but might not be
So here's a problem that has tormented me for years:
You have $N$ rocks, and need to distribute them into $K$ piles, potentially some of them empty. After the initial distribution into piles of sizes ...
2
votes
0
answers
143
views
Can a laser beam hit all points of $\{0,1,2\}^k \subset \mathbb{R}^k$ using $\frac{3^k-3}{2}$ mirrors only if emitted from outside the open $k$-cube?
Note: I already posted the $3$-dimensional version of this question on Mathematics Stack Exchange, but no answer has been received so far, so I hope that MathOverflow can be a more suitable place in ...
- 1,965
2
votes
0
answers
293
views
Extremal regular bipartite directed graph
Assign exactly one $0$ and one $1$ to the two ends of each edge of a regular simple undirected bipartite graph of $e$ edges, uniform degree $d$ and number of vertices $2v$. The assignment of the pair $...
- 2,363
0
votes
0
answers
222
views
Combinatorial code design
I would like to know the feasibility of the following linear programming problem related to coding theory.
Given a natural number $d$, binary entry matrix $X:=[x(i,j)\in B],\ B:=\{0,1\},\ i\in B^d,\ j\...
- 2,363
7
votes
1
answer
409
views
A possible graph canonical labeling
Given a simple unlabeled graph $G = (V,E)$ with vertices $V=\{1,\ldots,n\}$, let $L(G)$ a labeled graph obtained by labeling the vertices of $G$ through an $l: V \rightarrow V$ such that:
$$\sum_{\{...
- 1,186
15
votes
0
answers
305
views
Guessing a permutation in a way analogous to Wordle
Let $w$ be a permutation of $\{1,2,\dots,n\}$ chosen uniformly at
random. You have to determine $w$ by successively guessing
permutations $v_1, v_2, \dots$. After each guess $v_j$ you are told
where $...
- 53.6k
5
votes
1
answer
439
views
Total unhappy couples in a variant of the Stable Marriage Problem
Thinking about this question that I report here for convenience:
There are $n$ men and $n$ women. Each man has a strict preference (ordering/ranking) over all women, and each woman has a strict ...
- 1,186
8
votes
3
answers
616
views
Existence of nested squares with nonnegative sums
Let $T$ be a $4\times 4$ torus square for which the left/right, the up/down sides are glued. Each cell has a real number, and the sum of the $16$ numbers is $0$. Prove or disprove: there always exist ...
- 1,073
1
vote
0
answers
147
views
An elementary optimization problem
(Also posted at mathstackexchange some 2+ weeks ago, but hasn't got answered.)
If $y_1,\dotsc,y_N\ge 0$ satisfy $y_1^2+\dotsb+y_N^2=3/2$ and $y_1^3+\dotsb+y_N^3\ge1/2$ then, clearly, $\max y_i\ge 1/3$....
- 568
0
votes
0
answers
76
views
Showing that theta body of self-complementary graph is largest set of assignments of probabilities under certain restrictions
I am trying to understand the proof of lemma 3 from this paper
Let $G$ be a graph with vertex set $V(G)$, edge set $E(G)$ and clique set $C(G)$. The fractional vertex polytope $QSTAB(G)$, the theta ...
- 101
5
votes
2
answers
822
views
In Euclidean space, if it's easy to generate random elements of a set, is it also easy to compute the projection to the set?
Let $A \in \mathbb{R}^m$ be some set with the property that it is easy (polynomial-time computation) to generate random elements $r \in A$. Is it then also easy to compute
$$ P_A(x) := \arg \min_{y\in ...
- 1,173
4
votes
2
answers
220
views
Simpler proof of arborescence packing and isolating cut equivalence
Let $G$ be a directed graph with specified vertex $v$. We define a $v$-cut in $G$ to be a set of edges whose deletion from $G$ results in a graph where some vertex $w\neq v$ cannot be reached by a ...
- 599
0
votes
0
answers
55
views
Optimisation problem: Explicit visits in a graph with prerequisite and encompassing edges
I have not been able to find a solution to this problem, the way I approached it was by trying to combine a greedy approach for encompassing nodes and topological sorting for prerequisites.
Context: I'...
- 1
1
vote
0
answers
161
views
A lower bound question in Combinatorics
Given a function $f:{X\choose d}\to {X\choose \ell}$ where $X=\{1,2,\ldots,n\}$, $n>d>\ell$ and $(\forall A\in {X\choose d}) \ f(A)\subset A$. Prove that
$$\log|Range(f)|=\Omega\left(\ell\log\...
0
votes
0
answers
60
views
Approximating unknown monotone functions efficiently
I have two unknown non-negative vectors $\vec{\alpha}, \vec{w}$ of length $n$, where $\sum_{i=1}^n \alpha_i =1$.
I define the following function $f:[0,1]^n\rightarrow \mathbb{R}_{\geq 0}$ where $f(\...
- 177
13
votes
1
answer
405
views
Isomorphism between maximal planar graphs and minimal set unions
I asked a version of this question on MSE (see Minimum number of unions to make collection of subsets) but only got a linear program as an answer. I would like a proof.
It is well known that the ...
- 81
2
votes
0
answers
124
views
Algorithm for optimal set partition
Given a function $f:2^{[n]} \to [0, \infty)$, the problem is to find a partition $\mathscr{P}$ of $[n]$ which maximizes $\sum_{S \in \mathscr{P}} f(S)$. I am also interested in the case where $\...
- 121
0
votes
1
answer
143
views
A variant of Knapsack problem
In the standard Knapsack problem, the objective is to maximize $\sum c_i x_i$. I encounter a variant where the objective is to minimize $\sum c_i a^{x_i}$ where $a\in(0,1)$ is a constant. I am looking ...
- 327
2
votes
0
answers
79
views
Longest TSP in the unitary disc
I have the unitary disc $D=\{(x,y) \in R^2: x^2 + y^2 \leq 1\} $, and an integer $n \geq 2$. I want to select $n$ points in $D$ to maximise the length shortest path that connects them all. In other ...
4
votes
1
answer
295
views
How to maximize the variance of a subset of integers?
$\DeclareMathOperator{\Var}{Var}$Given the set of numbers $\Omega := \{1, \ldots, n\}, n \in \mathbb{Z}^+$, how can I choose a subset, $A$ of $\Omega$ , such that $\min(\Var(A), \Var(\Omega \setminus ...
- 169
2
votes
1
answer
255
views
Integral hull of a polyhedron is polyhedron
$\DeclareMathOperator\Convexhull{Convexhull}$Let $Q \subseteq \mathbb R^n$ be a rational polyhedron and let $Q_I=\Convexhull(Q \cap \mathbb Z^n)$. By finite basis theorem, we have $Q=P+C$ for some ...
- 31
0
votes
1
answer
100
views
Cycle-Sculpturing with Minimal Vertex-Deletion
given a simple, finite and symmetric graph $G(V,E)$ with $n$ vertices and at least $n$ edges
Question:
how can the smallest set of vertices $W\subset V$ be calculated for which the graph induced by $...
- 14k
1
vote
1
answer
401
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^...
- 21
4
votes
1
answer
252
views
Optimal partition of $n$ points
Given an integer $n$, and 3 real sequences $\{x_1, \dots, x_n\}, \{y_1, \dots, y_n\}$ and $\{w_1, \dots, w_n\}$ with $x_k, y_k, w_k > 0$, for all $k \in \{1, \dots, n\}$. For a fixed $p < n$ ...
- 43
0
votes
0
answers
202
views
How to find a configuration of lines
In $\mathbb{R}^3$, can anyone help find a configuration of 5 lines such that the minimum of the smallest semi-axis lengths of the ellipsoid $ \mathbf{x}^T \mathbf{A} \mathbf{x} = 1 $, where $\mathbf{A}...
- 61
1
vote
0
answers
39
views
Complexity of optimal cartesian matching
Question:
what is known about the algorithmic aspects of optimally matching a set $\mathcal{P} = \prod\limits_{i=1}^n \left(1,\,\cdots,\,k_i\right)$ of grid-points to a set of $\prod\limits_{i=1}^...
- 14k
2
votes
0
answers
69
views
Cluster minimizing sum of cost of clusters
Given a dataset $X,$ having $p$ features, organize the units $x_i \in X $ into fixed number of clusters $g,$ with fixed cluster size $B.$
Clustering policy: minimize the sum of a linear combination of ...
- 31
6
votes
1
answer
298
views
Maximizing the mutual Hamming distance in $\big[{\cal P}([n])\big]^n$
If $X$ is a set and $A,B\subseteq X$ we let the Hamming distance of $A,B$ be defined as $d_H(A,B) = \big|(A\setminus B)\cup(B\setminus A)\big|$. If $\newcommand{\S}{{\cal S}}\S\subseteq {\cal P}(X)$, ...
1
vote
0
answers
82
views
Finding a path of given length with maximal relative weight
Let $G$ be a directed graph with vertices $V$ and edges $E \subset V\times V$. A path of length $n \geq 2$ in $G$ is a sequence of vertices $(i_{0},i_{1},\ldots,i_{n-1})$ such that $(i_{k},i_{k+1}) \...
- 912
1
vote
0
answers
126
views
How to solve a optimal matching problem where the "quality" of matching is only determined once all nodes are matched
Note: I'm not a mathematician; I'm just a biologist with basic math background trying to solve a scientific problem, so please excuse my ignorance.
The gist of the problem is as follows:
I have two ...
3
votes
1
answer
208
views
Optimizing sum of $k$ positive integers with the product $m$
The product of $k$ positive integers $x_1,x_2,\ldots,x_k$ is $m$, I'm wondering how to find the minimum and maximum of $\sum_{i=1}^kx_i$. For the maximization problem, in order to exclude the trivial ...
- 417
1
vote
0
answers
335
views
A question about decomposition of irreducible root system
Fix an irreducible root system $\Phi$ with rank $r$ and a root base $\Delta$ (we only care type ADE). Call a disjoint union $\Phi = \Phi_{1}\sqcup\dotsb\sqcup\Phi_{s}$ a decomposition of $\Phi$ if ...
- 635
6
votes
2
answers
836
views
Bound on the number of unit vectors with the same pairwise inner products
I want to know the bound on the number of unit vectors $v_i$ in $\mathbb{R}^n$ such that $\langle v_i, v_j\rangle=c$ for all $i\ne j$. I know this can be upper bounded by the number of equiangular ...
- 163
3
votes
0
answers
215
views
Understanding why $\frac{\phi^5}{2}$ solves this 3D optimization problem, where $\phi$ is the golden ratio
I would like to understand the deep meaning of a solution which arises from an optimization problem discussed in a paper of mine since it can be simply stated as $\frac{\phi^5}{2}$, where $\phi := \...
- 1,965
3
votes
2
answers
403
views
Algorithm to evaluate "connectedness" of a binary matrix
I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:
...
- 1,186
8
votes
2
answers
376
views
Equal segmentation of a series of numbers
How can a series of real numbers be split into subsets in a way that the sum of the real numbers within each subset is as equal as possible?
Coming across from StackOverflow this is the first time, I'...
- 83
1
vote
0
answers
107
views
Conjecture on the increasing efficiency of the shortest minimum-link polygonal chains covering any grids of the form $\{0,1,2\}^k$ as $k$ grows
From the well-known Nine dots problem, we know that we need a polygonal chain with at least $4$ edges to connect the $9$ points of the planar grid $G_{3,2}:=\{\{0, 1, 2\} \times \{0, 1, 2\}\} \subset \...
- 1,965
2
votes
1
answer
188
views
Finding survivable paths with a set of vulnerable edges
Consider a graph $G=(V,E)$ and a source-destination pair $(s,t)$. A set of edges $E'\subseteq E$ are vulnerable in the sense that at most $k$ of them may fail. My problem is to find a set of $(s,t)$ ...
- 327
8
votes
1
answer
900
views
Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree
Let $k$ be a given positive integer, and then consider the unit hypercube $\{0, 1\}^k \subset \mathbb{R}^k$ (i.e., a $k$-dimensional "cube" in the well-known Euclidean space).
We need to ...
- 1,965
0
votes
0
answers
166
views
A variant of Steiner tree
Consider a directed Steiner tree problem with a source node $s$ a set $T$ of terminals with the following constraint. For each node $v$ on the tree, we assign a branching value $b_v$ as follows. (1) $...
- 327
1
vote
0
answers
112
views
Is there an efficient algorithm for finding a fundamental cycle basis of a graph with the fewest odd cycles? Failing that, a hardness result on this?
I can think of a greedy algorithm:
Let $B$ be a fundamental cycle basis of graph $G$ induced by spanning tree (or forest) $T$
For $e\in T$, let $n_+(e)$ ($n_-(e)$) be the number of even (odd) cycles ...
- 33
5
votes
1
answer
495
views
Shortest polygonal chain with $6$ edges visiting all the vertices of a cube
I am trying to find which is the minimum total Euclidean length of all the edges of a minimum-link polygonal chain joining the $8$ vertices of a given cube, located in the Euclidean space. In detail, ...
- 1,965
3
votes
1
answer
354
views
Approximation of poset
Let $(X,\leq)$ be a poset, $X=\{x_1,x_2,\dots,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 \...
- 69
0
votes
0
answers
128
views
Algorithm that can solve or approximate the solution to a combination problem
I have a computational problem on my hands and I would like your help.
Here is my problem (simplified)
Let $X = \{x_1, x_2, \ldots, x_n\}$ represent a set of $n$ values.
Each value $x_i$ has a ...
- 1
5
votes
2
answers
527
views
Maximum determinant of binary matrices with special properties
Let $A$ be an $n$-by-$n$ binary matrix (all elements are in $\{0,1\}$). It is known that the determinant of $A$ is bounded by $O(n^{n/2} / 2^n)$. I am looking for tighter upper bounds for matrices ...
- 3,579