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

1 vote
78 views

1 vote
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 ...
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 vote
123 views

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 ...
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}$. ...
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}^...
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 ...
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-...
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 ...
1 vote
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 ...
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 ...
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, ...
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 ...
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?
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 "...
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 ...
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 ...
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:=\...