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
2 votes
1 answer
153 views

Combinatorial process on multisets of integers

Edit: I prefer to formulate first the problem as Fedor Petrov suggests in the comments: We are given a multiset $F$, initially containing only the single integer $h$. Sequentially, at each time step, ...
Penelope Benenati's user avatar
2 votes
0 answers
108 views

What is the optimal upper bound of $|T_1|+|T_2|+|T_3|$ if $T_1, T_2, T_3$ are trees covering a planar graph

By a classical theorem of Nash-Williams, the edges of every connected $n$-vertex planar graph can be covered by three trees $T_1,T_2$ and $T_3$. Does anyone know of any results from an article or a ...
Xin Zhang's user avatar
  • 1,130
7 votes
1 answer
349 views

Vectors with minimal Hamming weight in a rational vector space?

Suppose given $n\ge 1$ and a subspace $U$ in $\mathbb{Q}^n$. It is given as $\mathbb{Q}$-span of certain known vectors. For $x \in U$, we let the Hamming weight of $x$ be the number of its nonzero ...
Matthias Künzer's user avatar
3 votes
1 answer
141 views

Combinatorial Euclidean geometry problem

Let $\mathcal{S}^d_{\epsilon}$ be the collection of all sets $S:=\{\mathbf{x}_1, \mathbf{x}_2, \ldots \mathbf{x}_{d+1}\}$ of $d+1$ points in a $d$-dimensional Euclidean space such that, for a given ...
Penelope Benenati's user avatar
2 votes
0 answers
64 views

Minimizing a certain norm of the identity operator on $\mathbb R^2$

$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
Iosif Pinelis's user avatar
5 votes
1 answer
316 views

On a certain norm of the identity operator on $\mathbb R^2$

$\newcommand\R{\mathbb R}\newcommand\Q{\mathcal Q}$For mutually orthogonal vectors unit vectors $a=[a_1,\dots,a_n]^T$ and $b=[b_1,\dots,b_n]^T$ in $\R^n=\R^{n\times1}$ (so that $n\ge2$) and for all $x=...
Iosif Pinelis's user avatar
1 vote
0 answers
45 views

Barycentric coordinates of weighted edges

Given $K_n$ with weighted edges, we can fix an edge $e_{AB}$, iterate over all non-adjacent edges $e_{CD}\in E\setminus e_{AD}$ and record how often $e_{AB}$ was in the lightest, intermediate or ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
42 views

Methods for useful visualisations of complete weighted graphs

Question: which methods for visualising complete weighted and symmetric graphs, i.e. $K_n$, are useful in the sense that they can aid in mathematical research? The Traveling Salesman Problem may ...
Manfred Weis's user avatar
  • 12.6k
1 vote
0 answers
33 views

Calculating vertex weights via mutually tangent circles of triangles

given a metric graph with positive edge weights $\left|e_{ij}\right|$ a standard task, especially in the context of the Traveling Salesman Problem, is to calculate $\max\sum\limits_{i=1}^n\omega_i:\ \...
Manfred Weis's user avatar
  • 12.6k
6 votes
1 answer
165 views

Subsets of a ball/sphere with the largest sum of distances

$\newcommand\R{\mathbb R}\newcommand\S{\mathbb S}$Let $B_d$ and $S_{d-1}$ denote, respectively, the closed unit ball and the unit sphere in $\R^d$. Let us say that a finite subset $F$ of $B_d$ is ...
Iosif Pinelis's user avatar
1 vote
0 answers
100 views

The earliest discrete optimization problem

What is the earliest example of anything that could be considered a discrete optimization problem? I can find plenty of examples of ancient continuous optimization problems (e.g. Dido's isoperimetric ...
Maggie Catalano's user avatar
6 votes
2 answers
408 views

Snake algorithm that minimizes straight lines

How can I find the non-self-intersecting loop that uses the least amount of straight lines (curves left/right as often as possible every turn) and still loops back on itself? Here's an example we have ...
Tzlil's user avatar
  • 61
2 votes
2 answers
372 views

Probabilistic combinatorial optimization problem on the distances between pairs of points in $[0,1]$

Let $S$ be a set of $n \gg 1$ points lying on the interval $[0,1]$. Given a point $p\in[0,1]$, let $S_p\subseteq S\times S$ be the set formed by all pairs of points $(x,y)$ with $x,y\in S$, such that ...
Penelope Benenati's user avatar
2 votes
0 answers
98 views

Sparse signal recovery (nonlinear case)

Let $K \subset \mathbb{R}^n$, it may be that $K$ is "very thin" (e.g. $K$ is a $k$-dimensional affine subset of $\mathbb{R}^n$, with $k \ll n$). I'm interested in the case where $K$ is ...
Sébastien Loisel's user avatar
0 votes
1 answer
316 views

Expectation of the ratio of two discrete random variables with combinatorial constraints

We are given a set $S=\{1, 2, \ldots, n\}$ where $n\gg 1$, and for all indices $1\le i \le n$, $i$ is associated with a real value $\alpha_i\!\cdot\! v_i$, where $\alpha_i\in[0,1]$ and $v_i\in(0,1]$. ...
Penelope Benenati's user avatar
0 votes
1 answer
59 views

Bounding the ratio of the $\ell_1$-norms of two real-valued $n$-vectors as a linear combination of their $n$ element-wise ratios

Let $a_1, a_2, \ldots a_n$ and $b_1, b_2, \ldots b_n$ be two sequences of $n\gg 1$ real numbers such that, for all $1\le i\le n$, we have $0<a_i \le b_i\le 1$. Let the ratio $R$ defined as follows: ...
Penelope Benenati's user avatar
2 votes
2 answers
276 views

Combinatorial optimization problem with interdependent constraints on points in $[0,1]$

We are given a set $S$ of $n$ real numbers in $[0,1]$, with $0,1\in S$, and a value $\alpha\in(0,1/2)$. For each ordered triplet $(i,j,k)$ of values contained in $S$ (with $i\le j \le k$), we define ...
Penelope Benenati's user avatar
1 vote
1 answer
93 views

Weak submodularity for consecutive indices

Let $f\colon \mathbf{R} \times \mathbf{R}^+ \rightarrow \mathbf{R}$ be defined by $f(x,y) = \frac{x^2}{y}$. Let $X = \left\lbrace x_1, \dots, x_n\right\rbrace \subseteq \mathbf{R}$, $Y = \left\lbrace ...
Charles Pehlivanian's user avatar
7 votes
3 answers
263 views

Shrinking subset and product

Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that maximizes $|...
pi66's user avatar
  • 1,199
1 vote
1 answer
111 views

Shrinking subset with disjoint unions

Given a segment and a value $c$ less than the segment length, let $A_1,\dots,A_n$ be disjoint finite unions of intervals on the segment. We choose a finite union of intervals $B$ with $|B|=c$ that ...
pi66's user avatar
  • 1,199
2 votes
0 answers
33 views

Algorithm for lightest unnested planar vertex-disjoint cycle-cover

Question: given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$, what is the ...
Manfred Weis's user avatar
  • 12.6k
12 votes
0 answers
12k views

A New York Times tiles-based graph theory question

The New York Times has a daily puzzle named Tiles that works as follows. Start with $m$ squares (in the official version, this is 30, in a 6x5 grid), and a set of $p>4$ possible patterns (typically ...
David Pepper's user avatar
3 votes
1 answer
394 views

Symmetric distribution optimization problem of distances between points in $[0,1]$

Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $x, y, z$ the outcomes of three i.i.d. random variables $X, Y, Z$ with distribution $\mathcal{D}$, sorted in increasing order, ...
Penelope Benenati's user avatar
2 votes
1 answer
216 views

Probability distribution optimization problem of distances between points in $[0,1]$

Let $\mathcal{D}$ be a probability distribution with support $[0,1]$. Let $X, Y, Z$ three i.i.d. random variables with distribution $\mathcal{D}$, and $T$ a random variable uniformly distributed in $[...
Penelope Benenati's user avatar
2 votes
0 answers
85 views

Optimal paths in set-weighted graphs

Let $G = (V,E)$ be an $n$-vertex graph, let $R$ be a finite set (to be specific, let us assume that $R = [n]$), and let $W : V \rightarrow 2^R$. Let us call the pair $(G, W)$ a set-weighted graph. Now ...
Victor's user avatar
  • 655
0 votes
0 answers
124 views

Maximizing a vector after a series of matrix multiplications

Problem Statement Let's say we have a set of $n\times n$ matrices $X=\{M_1,\ldots,M_r\}$ and weights of these matrices $\{w_1,\ldots,w_r\}$ along with a set of "initial vectors" $\{v_1,\...
exfret's user avatar
  • 479
5 votes
0 answers
198 views

Existence of a honeycomb composed by nearly-hyperspherical $d$-dimensional cells having the same shape and size

Let $\mathcal{H}$ the class of all honeycombs composed by $d$-dimensional cells $C$ having all the same shape and size in a $d$-dimensional space $\mathcal{S}$. Let $s(C)$ and $\ell(C)$ be ...
Penelope Benenati's user avatar
4 votes
1 answer
358 views

Trade-off between hypervolume and diameter of $d$-dimensional shapes having a hypercubic smallest bounding box

Given any $d$-dimensional shape $X$, let $V(X)$ be its $d$-dimensional volume, and let $\ell(X)$ be the length of the longest line segment connecting two points of $X$. Let $\mathcal{S}_C$ be the set ...
Penelope Benenati's user avatar
1 vote
0 answers
35 views

Directed vertex-disjoint 3-cycle covers from Windy Postman tours?

It is a result of Zaw Win (paywall) that optimal Windy Postman tours in eulerian digraphs can be calculated in polynomial time. Bodo Manthey has shown that directed 3-Cycle Covers are APX hard to ...
Manfred Weis's user avatar
  • 12.6k
2 votes
0 answers
38 views

Optimal Directed Graph with Maximum Number of Interactions

Definitions: The number of interactions of a directed graph $(V,E)$, denoted by $\operatorname{inter}(V,E)$ is defined by $$ \operatorname{inter}(V,E) = \sum_{e,f\in V} I_{\gamma{[e,f]}}, $$ where $...
ABIM's user avatar
  • 5,019
0 votes
1 answer
57 views

Implementing Bemporad optimization algorithm

I need to reproduce the results of a relatively old paper of a paper and one of the steps is to solve an IQP problem, the algorithm suggested is this one. Which I don't know it's the best way to do it ...
user8469759's user avatar
2 votes
3 answers
290 views

Geometric probabilistic problem on triangles on a plane

We are given a triangle $T$ on a plane $P$, with sidelengths $a$, $b$ and $c$, where $c \ge b \ge a > 0$. A straight line $L$ on $P$ is selected uniformly at random from the set of all the ...
Penelope Benenati's user avatar
3 votes
1 answer
249 views

Optimal rule for multiple stopping times for defect finding

Suppose a quality inspector is inspecting $b$ black amongst which $d_B$ are known to be defective and $w$ white gadgets amongst which $d_W$ are known to be defective. The gadgets come down along an ...
Hans's user avatar
  • 2,169
1 vote
0 answers
74 views

SDP relaxation vs. Monte Carlo for MaxCut: which one performs better?

the Goemans Williamson SDP relaxation of the MAXCUT problem famously gives a polynomial approximation ratio of .87856 for the MAXCUT on regular graphs. Another popular approach to obtain efficient ...
user134977's user avatar
1 vote
0 answers
52 views

Reductions to the MAX-3-DCC Problem

I am currently working on the Max-3-DCC problem that asks for the heaviest vertex-disjoint cycle cover of weighted directed graphs. The problem has been reduced to 3-SAT in 1979 by L. Valiant in his ...
Manfred Weis's user avatar
  • 12.6k
4 votes
0 answers
244 views

Distance properties of the permutations of a set of points in a Euclidean space

We are given a set of $n$ distinct points $S=\{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n\}$ in a Euclidean space $\mathbb{R}^d$, where the distance between two points $\mathbf{x}_i,\mathbf{x}_j\...
Penelope Benenati's user avatar
0 votes
1 answer
173 views

Relationship between cycle length, number of chords, and number of induced $P_{4}$ subgraphs of the cycle

I was wondering if there was a known relationship between the length of cycle, the number of chords of the cycle, and the number of induced $P_{4}$ subgraphs of the cycle. Here, I am referring to ...
yessssir's user avatar
0 votes
1 answer
116 views

Relaxing Meyniel graphs: condition for strongly perfect instead of very strongly perfect

A Meyniel graph, $\mathcal{G}$ is a graph in which every cycle of odd length at least 5 has at least 2 chords. First off, I have a technical question which is very important to me: what is meant by ...
yessssir's user avatar
1 vote
0 answers
38 views

Structural properties of polytopes for mainstream integer or linear programs

Are there any papers/textbooks/monographs that describe distinguishing properties of the polytopes that arise when solving the linear relaxation of well-known integer programs? For example, it is ...
Tom Solberg's user avatar
  • 3,929
1 vote
1 answer
141 views

Bound for multinomial expansion involving Poisson random variables

Let $x_i, i=1, \ldots n$ be Poisson random variables with parameters $\lambda_i$ correspondingly with condition that $\sum_{i=1}^nx_i=T$. Due to linearity of the expectation one can write: $$ E\left(\...
user124297's user avatar
5 votes
1 answer
394 views

What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?

Also asked on MSE: What is the best way to partition the $4$-subsets of $\{1,2,3,\dots,n\}$?. Consider the set $X = \{1,2,3,\dots,n\}$. Define the collection of all $4$-subsets of $X$ by $$\mathcal A=...
ArtOfProblemSolving's user avatar
5 votes
1 answer
436 views

Extending submodular functions from a sublattice

This came about when I was studying the connection between matroids and strong greedoids, but it has broken through into a subject I am not particularly familiar with: submodular functions on lattices....
darij grinberg's user avatar
0 votes
1 answer
167 views

Removing linear term in Quadratic assignment problem

Let us consider the following Quadratic assignment problem: \begin{equation} \tag{QP1} \max_{\begin{matrix}x_{ij}\in\{0,1\} \\ \forall j \sum_i x_{ij}=1 \\ \forall i \sum_j x_{ij}=1 \end{matrix}} x^...
Titouan Vayer's user avatar
2 votes
0 answers
62 views

Path-covering for vertex-transitive graphs

I have the following dummy problem: Claim - There exists $N$ such that for $n > N$, if $G_n$ be a connected directed vertex-transitive graph with $n$ vertices, then there exists a set $S$ of paths ...
Zach Hunter's user avatar
  • 3,393
1 vote
1 answer
108 views

Embedding of spheres which satisfies intersection rules

Let $S = \{S_1, \dots ,S_n\}$ be a finite set of $d$-dimensional spheres with the same radius, and let $E$ be a combination of intersections between them, where an intersection is a rule of the form $...
Alfred's user avatar
  • 879
4 votes
1 answer
333 views

Minimization of a discrete valued function

$$ \min_{f} \sum_{i=1}^n \max \left( 0, 2f(i) - f(i-1) -f(i+1)\right), $$ where the minimum is taken over all the functions $f$ from $\{0,1,2,\ldots,n+1\}$ to $[0,x]$, $x <1$, such that $f$ is non-...
user avatar
1 vote
1 answer
139 views

Monge's solution to the 'transporting earth' problem

In Schrijver's A course in combinatorial optimization (page 49, Application 3.3), I came across the transporting earth problem which is quoted below (replaced the French text by its English ...
Pritam Majumder's user avatar
2 votes
1 answer
225 views

Basis pursuit algorithms for exponentially large matrices?

Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices? That is $$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...
user1576720's user avatar
0 votes
1 answer
111 views

Optimal partition search

Given an integer $n$, and 2 real sequences $\{a_1, \dots, a_n\}$ and $\{b_1, \dots, b_n\}$, with $a_i$, $b_i$ > 0, for all $i$. For a fixed $m < n$ let $\{P_1, \dots, P_m\}$ be a partition of the ...
Charles Pehlivanian's user avatar
7 votes
3 answers
487 views

Minimum number of swaps needed to 'group' a sequence?

Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...
DSM's user avatar
  • 1,196

1 2 3
4
5
9