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

426
questions

2
votes

0
answers

132
views

+50

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

124
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

309
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

61
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

50
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

1
answer

66
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

43
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

44
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

122
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

56
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

0
answers

81
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

168
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

61
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

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

0
votes

1
answer

48
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

66
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

125
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} :=...

0
votes

0
answers

20
views

### LP formulation of $k$-opt moves

Question:
what is known about formulating $k$-opt moves that strive for improving the length of Hamilton cycles by means of exchanging $k$ of the tour edges with $k$ non-tour edges?
Specifically:
are ...

1
vote

0
answers

100
views

### On determinant and permanent of certain homotopy defined simple matrices

Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$
$$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$
hold ($per$ refers to permanent).
I. What ...

2
votes

0
answers

47
views

### Properties of the "girth function" of a matroid

Given an independent set representation of a matroid $M=(E,\mathcal{F})$ its ``rank function'' $r$ defined on the powerset of $E$ is:
$$
\forall X \subseteq E, \quad r(X) = \max_{Y \subseteq X}\{|Y|, ...

0
votes

1
answer

135
views

### A variation of Set Cover

Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to ...

1
vote

0
answers

48
views

### Knotted Traveling Salesperson route

Let us consider fixed points in space, if we apply the well-known Traveling Salesperson Problem algorithm, we get the shortest route. It can give a nontrivial knot in the three-space. The question is ...

1
vote

0
answers

40
views

### How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following.
Given a graph $G = \{V,E\}$,
we have a distance matrix (the ...

2
votes

0
answers

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

1
vote

2
answers

114
views

### How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?

I am looking for an algorithm to solve the following optimization problem
$$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$
where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$.
...

11
votes

2
answers

588
views

### A discrete optimization problem related to the AM-GM inequality

Let $k\in\mathbb{Z}_{>0}$, and $s\in\mathbb{N}$, and for $m_1,\ldots,m_k$ some nonnegative integers, consider the problem of maximizing the product
$$
(1+m_1)(1+m_2)\cdots(1+m_k)
$$
under the ...

11
votes

0
answers

430
views

### What sequence maximizes the final distance?

This problem was created by professor Ronaldo Garcia from Universidade Federal de Goiás (UFG) and he showed it to me at an event in my university. This problem has a lot of history and he told me he ...

0
votes

0
answers

13
views

### Counterexample to non-optimal symmetric edge detection heuristic

The undirected TSP problem allows for the efficient detection of Nonoptimal Edges for the Symmetric Traveling Salesman Problem
It is also known that the edges that constitute to the heaviest perfect ...

0
votes

0
answers

52
views

### Greedy algorithm for color-balanced spanning tree

Given a graph $G = (V, E)$, we can partition $E$ to $p$ disjoint colors, i.e., $E = S_1 \cup S_2 \cup \cdots \cup S_p $. The goal of color-balanced spanning tree problem is to find a spanning tree $T$...

4
votes

0
answers

217
views

### What does the best die look like?

Intransitive dice have attracted a lot of attention - especially in the context of recreational math - since their introduction by Efron in the 1960s. More recently, there has been work studying ...

0
votes

0
answers

114
views

### On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph

Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...

0
votes

0
answers

18
views

### ILP formulations for tour-improvements

Question:
what is known about the problem of formulating tour-improvement as an integer linear problem (ILP)?
To be specific:
what are necessary and/or sufficient constraints, besides the degree-...

0
votes

0
answers

52
views

### Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph

This is about graph theory.
Define an h-dimensional hyperedge as a set that contains h vertices.
A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...

1
vote

0
answers

51
views

### A multi-layer version of Menger's theorem

Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more ...

2
votes

1
answer

167
views

### Can information theory characterise a (topological) space?

Consider an objective function f: $\mathbb{R}^n\rightarrow\mathbb{R}$, with a vector of variables $\theta$, i.e. $f(\theta)$, $\theta \in \mathbb{R}^n$. Depending on $f$, there can be interesting ...

2
votes

1
answer

89
views

### How to prove the local search algorithm can find the maximum weight independent set in a matroid with cardinality constraint?

I am trying to prove a simple local search algorithm could solve exactly this problem:
$\underset{S \in I(M), |S|=k}{max} c(S)$
where $M$ is a matroid, and $ I(M)$ is the set of all independent set, $...

1
vote

1
answer

90
views

### Minimum set of numbers which covers all the values of all digits

Introduction
Let's consider binary numbers for simplification and let's consider 4 bits numbers. Sets which answer my problem are:
...

0
votes

1
answer

108
views

### Traveling salesperson problem algorithm [closed]

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...

3
votes

1
answer

279
views

### How to find the maximum of a sum of squares of sums?

Is there any better than a brute force method for finding the maximum
$$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$...

3
votes

0
answers

97
views

### The matrix representation of an interval graph

It is well-known that many classes of graphs have matrix representations that can be written concisely. For example,
The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...

3
votes

1
answer

135
views

### Algorithm for finding a minimum weight circuit in a weighted binary matroid

For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times.
Also for a matroid $M = (E, I)$ one can use the ...

0
votes

0
answers

114
views

### Conjecture on the unsolvability of the $\{3 \times 3 \times \cdots \times 3\} \subseteq \mathbb{R}^k$ dots problem starting from the central point

In 2020 (see Solving the $106$ years old $3^k$ points problem with the clockwise-algorithm, JFMA, 3(2), p. 96), I conjectured that, in the Euclidean space $\mathbb{R}^k$, we can cover any given set of ...

3
votes

0
answers

188
views

### Probabilistic optimization problem on tree vertex selection without replacement proportional to the degree

We are given a tree $T(V,E)$ with $|V|=n$ vertices, where $V=\{v_1,v_2,\ldots, v_n\}$. We denote by $d_i$ the degree of vertex $v_i$ for all $i\in\{1,2,\ldots,n\}$.
In a sequential fashion, we select ...

0
votes

0
answers

84
views

### Boolean operation on n dimensional polyhedron

A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$.
Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...

2
votes

0
answers

99
views

### Optimization problem on randomly selecting subintervals from a given interval with combinatorial constraints

We select uniformly at random $k$ pairwise disjoint intervals from a given interval $[0,s]$ with length respectively equal to $\ell_1, \ell_2, \ldots, \ell_k\ $, i.e., we select uniformly at random $k$...

1
vote

1
answer

482
views

### Finding an optimal covering trail for the set $\{0,1,2,3\}\times\{0,1,2,3\}\times\{0,1,2,3\}$

Here is a key question (i.e., Question 2 below) that, if correctly answered, would let me support a very general conjecture on a wide class of related problems, a conjecture that I have never shared ...

0
votes

1
answer

57
views

### Dual equivalence of minimum feedback-vertex sets and cycle packing

it is known that the duals of feedback-set problems are set-packing problems; in the context of digraphs the feedback set are either a minimal set of vertices or edges that hit every oriented cycle; ...

1
vote

2
answers

91
views

### Choosing $k$ different assignments of binary variables in order to capture the largest volume of the joint probability distribution

Assume you have $n$ independent binary variables $\{x_1,\dots,x_n\}$ and for each variable $x_i$ you know that its value is equal to $1$ with a probability $p_i$. I would like to enumerate the joint ...

2
votes

1
answer

149
views

### Optimal prefix-free code design with a complex objective function

We have a long message $m$ to encode. The message is composed of a set of symbols $\{s_i\}$. Let $p_i$ denote the number of appearance of $s_i$ in $m$. We seek to find a prefix-free code for each $s_i$...

1
vote

0
answers

39
views

### Compute 01-vectors in the orbit of a given vector wrt a finitely-generated abelian subgroup of SL(n,ℤ)

Given a vector $v\in\mathbb Z^n$ and pairwise commutative matrices $M_1,\dotsc,M_k\in \operatorname{SL}(n,\mathbb Z)$, how to compute all 01-vectors in the orbit of $v$ with respect to multiplication ...