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.

Filter by
Sorted by
Tagged with
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. ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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}...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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{...
user avatar
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\{...
user avatar
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 ...
user avatar
  • 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. ...
user avatar
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-...
user avatar
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 ...
user avatar
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$ ...
user avatar
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 ...
user avatar
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:=\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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$. ...
user avatar
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:=\...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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}$. ...
user avatar
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}^...
user avatar
  • 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 ...
user avatar
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-...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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?
user avatar
  • 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 "...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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:=\...
user avatar
  • 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 ...
user avatar

1
2 3 4 5
8