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 ...
- 31
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)$, ...
- 47.9k
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}) \...
- 798
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 ...
- 417
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 ...
- 43
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 ...
- 163
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 := \...
- 1,307
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:
...
- 906
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'...
- 83
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 \...
- 1,307
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)$ ...
- 367
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 ...
- 1,307
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) $...
- 367
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 ...
- 33
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, ...
- 1,307
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 ...
- 61
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 ...
- 1
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,539
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 ...
- 367
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 ...
- 81
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) \...
- 47.9k
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 ...
- 567
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 ...
- 433
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 ...
- 1,307
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 ...
- 49
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 ...
- 1,307
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,\\ &...
- 12.9k
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 $...
- 21
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 ...
- 12.9k
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 ...
- 3
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 ...
- 41
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 &...
- 3,539
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}^{...
- 29
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,190
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 ...
- 11
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 ...
- 251
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 ...
- 11
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 ...
- 909
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 ...
- 43
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)(\...
- 101
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}...
- 21
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\...
- 22.5k
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^...
- 12.9k
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, ...
- 41.4k
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 ...
- 23
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} :=...
- 745