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.
360
questions
4
votes
2
answers
91
views
$O(n^{2-\epsilon})$ bound on choosing $n$ points on the hypersphere to maximize $\pm 1$ weighted sum of their $\binom{n}{2}$ inner products
Given $n,d\in\mathbb{N}, n\gg d$, I'm looking for a bound on the maximum (or minimum) expected value of the following game:
Draw a vector $\epsilon\in\{\pm 1\}^{\binom{n}{2}}$, uniformly at random. ...
- 41
5
votes
0
answers
48
views
Roundest polyhedra: how well can we bound the edge count of their faces?
By "roundest" I mean having the lowest surface area for the highest volume, given a fixed number of faces $n$. There've been a few questions about them on here (including from me), but I'm ...
- 3,138
20
votes
2
answers
544
views
What is the smallest size of a shape in which all fixed $n$-polyominos can fit?
Let $n$ be an integer and consider all fixed $n$-polyominos, i.e., without rotation or reflection. I am interested in finding a shape in which all polyominos can embed. (It is OK if multiple ...
- 369
1
vote
2
answers
61
views
Minimum edge-weighted directed subgraph in polynomial time
I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of ...
- 13
4
votes
2
answers
118
views
Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment
I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
- 229
4
votes
1
answer
193
views
Reliability of ILP approach to number-theoretic optimization
This question is inspired by the recent answer, where @RobPratt proposed to use integer linear programming (ILP) for solving a number-theoretic optimization problem. I will consider a very similar ...
- 25.2k
2
votes
0
answers
70
views
Modified quadratic assignment problem
Let $Y,Z$ be $n\times k$ matrices and assume all columns have been standardized such that their means are zero and variances 1. I seek an $n\times n$ permutation matrix $P$ such that
$$\left\Vert Y^{T}...
- 133
25
votes
3
answers
2k
views
Splitting the integers from $1$ to $2n$ into two sets with products as close as possible
For each positive integer $n$, split the integers $1$ to $2n$ into two sets of $n$ elements each, and such that the products of the elements in each of these sets are as close as possible, say they ...
- 3,229
2
votes
0
answers
41
views
Maximize connectivity probability with a number of edges
We are given a graph $G$, whose edges are either open or closed. Initially all the edges are closed. For each edge $e$, if we choose to activate it, then after the activation, it becomes open with ...
- 491
0
votes
0
answers
50
views
Graph reduction and combinatorial optimization
Crossposted at Theoretical Computer Science SE
We are given a multigraph $G$. Consider two nodes $u$ and $v$ with multiple edges between them. Each elementary edge is associated with a metric called ...
- 491
1
vote
2
answers
78
views
References for geometric properties of optimal Euclidean traveling salesman tour
Consider a finite set of points $V \subseteq \mathbb{R}^2 $ as a TSP-instance under the standard $\| \cdot \|_2$ norm. (TSP stands for traveling salesman tour.) We know that every optimal TSP tour $T$ ...
- 11
7
votes
1
answer
283
views
Smallest relation in complement of partial order that prohibits its extension
Let $P$ be a partial order on a finite set $S$ (assume that every element is related to at least one other element besides itself…this raises a few quick questions: is this implied by the definition ...
- 716
5
votes
0
answers
130
views
Reference request: maximal determinant of matrices with pairwise orthogonal rows and entries in $\{1, 0, -1\}$
We know that "Hadamard maximal determinant problem" concerns the largest determinant of a matrix of oder $n$ with entries in $\{-1,1\}$ or $\{0, 1\}$. For $n=4k$, it is the Hadamard ...
- 665
1
vote
1
answer
97
views
How to distribute least number of $D$ card decks amongst $n$ people so that any $k$ people have a full deck and no $k-1$ people have a full deck
Decks are composed of 1 copy of each of $D$ unique cards. The set of cards is $C$ ($|C|=D$), the set of people is $P$ ($|P|=n\geq k$).
Starting with a simpler case (dropping the $k-1$ restriction)
One ...
- 19
3
votes
1
answer
99
views
Algorithm to minimize $\operatorname{tr}(PAP^TB)$?
Let say I have two $n$ x $n$ matrices $A$ and $B$ where all elements are real positive values. I want to find some $n$ x $n$ permutation matrix $P$ such that $\operatorname{tr}(P A P ^T B)$ is ...
0
votes
1
answer
98
views
Best algorithm for meeting scheduling optimization so that total number of held meetings is minimized
Problem Description
I want to hold meetings where some given number of people will participate.
They have some vacant dates respectively but they don't have the same date on which all of them can ...
1
vote
1
answer
76
views
Permute a sparse random matrix to resemble a diagonal matrix as much as possible
Say we generate an $N \times N$ sparse random matrix $W$, where each element $W_{ij}$ was independently chosen to be $1$ with probability $p=\frac{a}{N}$, and $0$ with probability $1-p$. We are ...
- 187
0
votes
0
answers
27
views
Minimal distance between intersections of a regular grid parameterized by its change-of-basis matrix
Let a 2D grid basis $\mathcal{B}(\theta_1, \theta_2,r_1, r_2)$ whose change-of-basis matrix with respect to $\mathcal{B}_0$ the canonical basis of $\mathbb{R}^2$ writes :
$$P_{\mathcal{B}_0}^{\mathcal{...
1
vote
0
answers
78
views
Efficient algorithm for a distance on strings
Let $(M,d)$ be a metric space. Consider two sequences $a = (a_i)_{i=1}^n$, $b = (b_i)_{i=1}^m$, $n, m \in \mathbb{N}$ with elements in $M$. For two sequences $[n],[m]$, call $$\Gamma([n], [m]) = \big\{...
2
votes
0
answers
44
views
A variant of the elliptope relaxation
Given a p.s.d. matrix $A$, one may want to find:
$$
\max_x x^t A x \mbox{ such that } x \mbox{ has entries }1 \mbox{ or } {-1}.
$$
This hard problem has a well known relaxation based on the so called ...
- 1,931
0
votes
0
answers
19
views
MSTs as "connectivity donors" for ILPs of TSPs
Traditionally the constraints that eliminate subtours from the optimal solution of an ILP for a TSP are based on partitions of the vertex set that resemble a $2$-factor of the problem instance.
...
- 11k
0
votes
0
answers
29
views
Subtour-gluing constraints for ILP formulation of TSPs
If one doesn't want to introduce additional variables to the ILP of a TSP instance, one has to add exponentially many so-called subtour-elimination constraints; in practical calculations subtour-...
- 11k
0
votes
0
answers
28
views
Regrouping the leaf nodes of the WordNet DAG
Motivation
I am trying to find a criterion to regroup the classes of the ImageNet challenge dataset, one of the most important datasets used in Machine Learning.
The ImageNet dataset has 1000 classes ...
7
votes
2
answers
248
views
Is there an efficient generalized algorithm to find at least one binary word with the maximum rotational imbalance and the full $\{0, 1\}$-balance?
Assuming that $x$ is a sequence of $l$ bits (i.e. a binary word of length $l$) and $0 \le m < l$, let $R(x, m)$ denote the result of the left bitwise rotation (i.e. the left circular shift) of $x$ ...
- 645
0
votes
1
answer
19
views
Transformation of an unconstrained binary quadratic optimization problem into a constrained binary linear programming problem
I know that a constrained linear optimization problem can be transformed into an unconstrained binary quadratic optimization problem (UBQP). Does anyone know if the inverse result is solved in the ...
- 11
1
vote
0
answers
20
views
Topology of densest graphs whose optimal $3D$-matching can be calculated efficiently
let $A=\lbrace a_1,\,\dots,\,a_k\rbrace $ and $B=\lbrace b_1,\,\dots,\,b_{2k}\rbrace,\ A\cap B=\emptyset$ be be a partition of a graph's vertex set $V$, i.e. $V\,=\,A\cup B$.
Question:
has $G:=\...
- 11k
0
votes
0
answers
6
views
Bounds on number of subtour elimination constraints needed for solving TSPs to optimality
Question:
what is the "subtour complexity" of the TSP, that measures how the number of subtour constraints the ILP, that finally solves a TSP instance to optimality, can have in the worst ...
- 11k
0
votes
0
answers
73
views
Why is Gaussian distribution always chosen for smoothed analysis?
I came across the algorithmic perfomance analysis model of smoothed analysis. In all references that I read a Gaussian distribution was used for perturbation (e.g. Spielman and Teng 2004 for the ...
- 11
0
votes
1
answer
39
views
Do we really need degree constraints for ILP formulations of TSP problems
The Dantzig-Fulkerson ILP-formulation of the symmetric TSP is
$$\min\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n c_{ij}x_{\lbrace i,j\rbrace}\quad\text{s.t.}\\ \sum\limits_{j\ne i,\,j=1}^n x_{\lbrace ...
- 11k
1
vote
0
answers
28
views
Vertex cover via maximally unbalanced spanning trees
The vertex cover problem asks for a smallest subset $U\subseteq V$ that is adjacent to all edges of a symmetric graph $G(V,E)$.
Inspired by the observation that led to this question Perfectly balanced ...
- 11k
5
votes
1
answer
147
views
Graph combinatorial optimization problem
Let $G$ be a simple graph with vertex set $V$, such that for any two vertices $u,v\in V$, we have at least $k$ edge-disjoint paths of length $2$ (i.e., formed by $2$ edges) connecting $u$ with $v$. ...
- 1,173
1
vote
1
answer
123
views
Combinatorial graph optimization problem on integer adjacency matrices
We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers.
Let $z_{i,j}:=\frac{M_{i,j}}{M_{i,j}+\sum_{k\neq i,j}\min(M_{i,k},M_{k,j})}$ for all $1\le i<j \le n$, and
$z:=\...
- 1,173
2
votes
1
answer
117
views
Generating short Hamilton cycles from complete graphs
Let $G(V,E)$ be a complete symmetric graph without self-loops or parallel edges; depending on the context the edges may however be interpreted as a pair of antiparallel arcs of equal weight.
A vertex ...
- 11k
1
vote
1
answer
106
views
Knapsack like problem with nonnegative weight constraint
I am dealing with a knapsack-like problem with one difference from the conventional problem: the “weights” can be positive or negative and the constraint is $\sum w_i x_i \ge 0$ instead of $\sum w_i ...
- 13
-1
votes
1
answer
77
views
Finding a $k$-subset which maximizes a matrix sum
Let $M\in \mathbb{R}^{N\times N}$ be a given matrix and $k\ge 2$ be a given integer. Then my question is the following optimization problem:
Is there a polynomial-time solution to the following ...
9
votes
1
answer
256
views
Partitioning a set of lattice points in the plane into rectangles
The "long comment" by Pietro Majer on Reference for puzzle on dividing piles and scoring products suggests the
following problem. Let $S$ be a finite subset of $\mathbb{Z}\times
\mathbb{Z}$. ...
- 43.7k
3
votes
1
answer
70
views
Upper bound for the crossed-terms of a sum of multinomial coefficients
I am trying to upper bound the variance of a centered tree and I would like to get an upper bound which would look like : $$\sum\limits_{\substack{ (l_1, ..., l_d) \neq (k_1, ..., k_d), \\ \sum_{j=1}^...
- 33
0
votes
0
answers
28
views
Does LKH perform best with $\mathrm{1\unicode{x2013}trees}$
The LKH heuristic essentially generates sequence connected graphs with $n$ edges by means calculating minimum-weight spanning trees of $n-1$ of the vertices and connects the unspanned vertex to the ...
- 11k
0
votes
1
answer
91
views
Mapping problem reminiscent of Mastermind
Given 2 finite sets $S$ and $M$, with $\operatorname{card}(S) \geq \operatorname{card}(M)$, and an item $z \not\in M$. There is an unknown function $f: S \to M \cup \{z\}$, which is known to be one-to-...
0
votes
0
answers
20
views
Tour expansion with min-cost flow
Question:
has the problem of formulating optimal tour-expansion for Symmetric TSP's already been mentioned as a means for faster tour-expansion in the sense of potentially intergrating more than one ...
- 11k
1
vote
0
answers
58
views
Facility location and traveling salesman
This question is based on Distributing points evenly on a sphere and Facility location on manifolds
The 'dispersal problem' (which can be mapped to packing disks in many cases) places $n$ points in a ...
- 3,349
0
votes
1
answer
73
views
Integer programming for bin covering problem
I encounter an integer programming problem like this:
Suppose a student needs to take exams in n courses {math, physics, literature, etc}. To pass the exam in course i, the student needs to spend an ...
0
votes
1
answer
131
views
Finding a subset of vectors whose sum is close to a given vector
Given a set of vectors $x_1,...,x_n\in\mathbb{R}^d$ and a vector $y$, find a subset $I\subset\{1,2,...,n\}$ such that $\|\sum_{i\in I} x_i-y\|$ is as small as possible. Here $\|.\|$ can be any norm, ...
- 21
3
votes
1
answer
413
views
Magic circle (instead of magic square)
Motivation. I stumbled over this riddle (unfortunately in German): the goal is to fill the numbers $1\ldots7$ (or, equivalently, $0\ldots6$) into the $7$ little circles so that the sums of all numbers ...
- 39.3k
7
votes
1
answer
148
views
Metric TSP with integer edge cost
Given a metric TSP with integer edge cost upper-bounded by a constant $C_{\max}$, can we find an poly-time algorithm solving this TSP instance?
- 491
0
votes
0
answers
51
views
What do optimal tours tell about finite point sets?
Let $T_{\mathrm{MIN}}$ and $T_{\mathrm{MAX}}$ denote the shortest, resp. longest Hamilton cycle through a set of $n=2k+1$ points.
Let further $S_{\mathrm{MIN}}$ and $S_{\mathrm{MAX}}$ be the "...
- 11k
0
votes
0
answers
34
views
Approximabilty of submodular over modular maximization
Given a non-decreasing, normalized, submodular function $f : 2^{[n]}\mapsto \mathbb{R}_+$ and a modular non-decreasing function $g$, I am wondering what is the best approximation ratio I can hope for ...
- 171
3
votes
1
answer
217
views
Is anything written about winning the "Dollar Game" in the minimal number of moves?
I run some Master's projects on Chip-Firing games, using the Holly Krieger's Numberphile video on the topic as an initial motivation, and going on to prove the main theorem stated there (that you can ...
- 2,292
0
votes
1
answer
37
views
Maximize this score function on a directed tree
Let $\mathbb N_0^\ast$ be the set of all finite words/sequences over $\mathbb N_0$ and $\varepsilon$ the empty word. For a word $a=(a_1,\ldots,a_n)$ we define $\operatorname{len}a:=n$, $\Sigma a:=\...
- 237
1
vote
0
answers
70
views
Gadgets that reduce NP hard problems to the MAX-3-DCC Problem
A while ago I had asked for benchmark instance for the MAX-3-DCC Problem but did not receive any feedback.
This question is a follow up aimed at concrete examples of reductions of NP hard problems to ...
- 11k