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

455
questions

-1
votes

0
answers

30
views

### Optimal Stratification of Time-Evolving Relational Structures with Constrained Update Mechanisms

Let $(S, T, \preceq)$ be a totally ordered set of timestamps, where $\preceq$ is the natural ordering on timestamps.
Define a relational structure $R$ as a tuple $(I, A, V, \tau)$ where:
$I$ is a ...

2
votes

0
answers

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

6
votes

1
answer

212
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

54
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}) \...

1
vote

0
answers

44
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

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

1
vote

0
answers

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

6
votes

2
answers

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

3
votes

0
answers

138
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 := \...

3
votes

2
answers

319
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:
...

8
votes

2
answers

259
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'...

1
vote

0
answers

67
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 \...

2
votes

1
answer

98
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)$ ...

8
votes

1
answer

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

0
votes

0
answers

116
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) $...

1
vote

0
answers

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

3
votes

1
answer

359
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, ...

3
votes

1
answer

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

0
votes

0
answers

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

5
votes

2
answers

383
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
votes

0
answers

183
views

### Optimal set partition

Given a set of elements $S=\{a_1,a_2,\cdots,a_n\}$, my problem is to find a partition $P$, i.e., partition $S$ into $g$ subsets, the objective is to maximize a utility function $f(P)$, under the ...

3
votes

1
answer

336
views

### Generating all possible subsets in order of sum

Given a set of positive integers, I am looking for method to algorithmically generate all possible subsets in order of their sum. Because the the count of possible subsets is exponential ($2^n$), it ...

4
votes

0
answers

227
views

### Optimal colorings

If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...

1
vote

2
answers

460
views

### What is the proper name for this "tersest path" problem in Infinite Craft?

The web game Infinite Craft gives you a starting set of elements $V_0\subset V$ and a mapping $E$ of type $V\times V\rightarrow V$. In fact, $F$ is commutative: $E(v_a,v_b) = E(v_b,v_a)$. So another ...

3
votes

2
answers

211
views

### Is there a closed-form solution for $\max_D \operatorname{Tr}(ADBD)$

Is there a closed-form solution for
$$\max_D \operatorname{Tr}(ADBD)$$
where $D$ is a $N\times N$ diagonal matrix with $m<N$ number of $1$'s and the rest are $0$'s, and $A$ and $B$ are real ...

1
vote

0
answers

151
views

### Optimal covering trails for every $k$-dimensional cubic lattice $\mathbb{N}^k := \{(x_1, x_2, \dots, x_n) : x_i \in \mathbb{N} \wedge n \geq 3\}$

After a dozen years spent investigating this particular class of problems, I finally give up and I wish to ask you if any improvement is achievable from here on.
The general problem is as follows:
Let ...

2
votes

1
answer

208
views

### Is matrix B obtained from matrix A?

Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...

2
votes

1
answer

150
views

### First known proof of the $2 \cdot n-2$ Theorem for the planar generalization of the Nine dots problem

Reading the Wikipedia page about the well-know Nine dots puzzle, I have just seen that the planar generalization of this problem would have been proven in 1956 (see Wikipedia: Nine dots puzzle), while ...

0
votes

0
answers

35
views

### ILPs with square constraint matrix

Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...

0
votes

0
answers

15
views

### Complexity of finding single source paths with capacity constraints and length constraints

Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...

0
votes

0
answers

26
views

### Monotony of enforced subtour merging

Is it true that for a symmetric TSP instance in the sequence of edges generated by successively:
calculating the optimal 2-factor
adding cardinality constraints on the edgesets of the 2-factor's ...

0
votes

0
answers

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

4
votes

0
answers

262
views

### Place colored balls in boxes that makes it hard to pick few boxes that contains large proportion of each color

There are $n$ boxes filled with red, blue and yellow balls. A box can be empty and it can also contain more than one color. For example, a box can have three red balls, ten blue balls and one yellow ...

3
votes

1
answer

401
views

### Electricity division and bin packing

In the electricity division problem, there is a powerhouse that supplies $s$ kilowatt of electricity. There are $n$ households. The connection size of household $i$ is $d_i$.
The problem is that $s &...

2
votes

0
answers

176
views

### How to prove this weighted sum inequality with non-increasing sequences?

Problem
I have two non-increasing sequences, $X = (x_1, x_3, x_5, \ldots, x_{n-1})$ and $Y = (y_1, y_3, y_5, \ldots, y_{n -1})$, $n$ is an even integer. I want to prove this inequality:
$$
\sum_{i=1}^{...

6
votes

1
answer

364
views

### Maximizing a sum minus its maximal summand

This is a followup to a question that appeared on m.SE:
Maximize $\displaystyle f(\pi)=\left(\sum_{i=1}^{n}{i\pi_i}\right)-\max_{1\le i\le n}{(i\pi_i)}$ over permutations $\pi\in S_n$.
The problem ...

1
vote

0
answers

70
views

### Maximum trace of powers of symmetric $\{0,1\}$-valued matrix with fixed row and column sums

Maximize $\operatorname{tr}(A^k)$ over binary symmetric $n$ by $n$ matrices subject to $$a_{ii}=0, \sum_{j=1}^n a_{ij}=d, \sum_{i=1}^na_{ij}=d,$$
where $d,k$ are fixed positive integers.
I am having ...

0
votes

0
answers

72
views

### An $n$-dimensional generalized Hoffman’s circulation theorem?

For a directed graph $G$, a 1-dimensional circulation is a function $f:E(G)\rightarrow \mathbb{R}$ such that for every $v\in V(G)$,
$$\sum_{uv\in E(G)}f(uv)=\sum_{vw\in E(G)}f(vw),$$
where $uv$ is an ...

0
votes

2
answers

123
views

### Graph vertices selection for paths sum minimalization

Let $G = (V, E)$ be a simple, finite, weighted, undirected, connected graph. Let $P = \{p_{ij}, p_{kl}, p_{il}, ... \}$ be a set of paths, where $p_{ij}$ is a path from $i$-th to $j$-th vertex. Is ...

1
vote

0
answers

51
views

### Hardness of an optimization problem when some variables are fixed

Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed.
With the two (related) examples, it is clear that ...

2
votes

0
answers

46
views

### Size of set of positive integers no sum of two distinct elements giving square

Question: find the size of a maximal subset $A$ of $[n]=\{1,\cdots,n\}$ satisfying that for any distinct elements $x,y\in A$, $x+y$ is not a perfect square.
Consider a graph with $n$ vertices: $x$ and ...

2
votes

1
answer

160
views

### Optimization over permutation

The Problem
This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...

0
votes

0
answers

66
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)(\...

2
votes

1
answer

235
views

### Can we say this nonlinear integer programming problem is NP-hard?

I was wondering if the following nonlinear integer programming problem is NP-hard or not.
$$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$
such that $\sum_{i=1}^{n}...

2
votes

1
answer

174
views

### Discrete maximization of geometric mean - reference request

This is a follow-up to my previous MO question:
A discrete optimization problem related to the AM-GM inequality
Let $n,k$ be integers such that $1\le k\le n$. Define the quantity
$$
P(n,k):=\max\ a_1\...

0
votes

1
answer

73
views

### Optimality of a "shopping" heuristic

Suppose the following situation: we have to buy $n$ goods $g_1,\,\dots,\,g_n$ starting at day 1 and we can't buy more than one good per day.
On day $d$ the prices are $p_1^d,\,\dots,\,p_n^d;\quad p_i^...

6
votes

1
answer

365
views

### Desargues ten point configuration $D_{10}$ in LaTeX

I want to draw the Desargues configuration $10_3$ in LaTeX using the standard picture environment, which allows only lines with the slopes $n:m$ where $\max\{|n|,|m|\}\le 6$. Is it possible? If not, ...

2
votes

2
answers

102
views

### Real-world datasets for testing the maximum edge bi-clique problem

We have proposed a new approach to solve the maximum edge bi-clique problem, however, we couldn't succeed to find real-world datasets (graph or bipartite graph datasets) to test our approach. Does ...

2
votes

0
answers

68
views

### What is an efficient non-adaptive group testing scheme if the number of defectives, $d$, grows proportionally to the number of items, $n$?

Suppose that for some $p \in \left(0, 1\right)$ and some $n \in \mathbb{N}$, we have $n$ independent Bernoulli random variables, $X_{1}, X_{2}, \dots, X_{n}$, each with mean $p$. We shall call $X_{1}, ...

3
votes

1
answer

141
views

### How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?

For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut norms are given by
$$\|M\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} m_{i, j} x_i y_j, \qquad \|M\|_{\square} :=...