# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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
54 views

• 1,307
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: ...
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
67 views

• 367
1 vote
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 ...
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
195 views

• 29
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
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 ...
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
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
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 ...
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
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
66 views

• 21