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 &...
- 3,525
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}^{...
- 29
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,160
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 ...
- 11
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 ...
- 251
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 ...
- 11
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 ...
- 909
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 ...
- 43
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)(\...
- 101
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}...
- 21
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\...
- 21.4k
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^...
- 12.4k
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, ...
- 40.1k
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} :=...
- 745
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 ...
- 12.4k
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 ...
- 13.5k
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|, ...
- 6,812
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
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 ...
- 71
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 ...
- 11
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}) - \...
- 175
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$.
...
- 175
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 ...
- 21.4k
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 ...
- 12.4k
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$...
- 43
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 ...
- 21.5k
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$ ...
- 61
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-...
- 12.4k
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-...
- 23
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 ...
- 1,854
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, $...
- 43
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:
...
- 11
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}$$...
user494931
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,868
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 ...
- 33
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 ...
- 807
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 ...
- 1,657
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 ...
- 21
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,657
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 ...
- 807
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; ...
- 12.4k
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 ...
- 13
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$...
- 459
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 ...
- 29.5k