# 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.

325 questions
Filter by
Sorted by
Tagged with
72 views

### Is this variant of knapsack problem strongly NP-hard?

Suppose we have a sequence of containers each of which contains multiple items. Each item $I_i$ is associated with an nonnegative weight $w_i$, a nonnegative value $v_i$, and $I_i(C)$ denotes the ID ...
44 views

### Minimizing the degree of outgoing edges in a digraph, does this problem have a name?

I have a problem which can be rephrased in this way. Suppose $G = (V,E)$ is a digraph (directed graph) and for each $v \in V$ we denote with $\delta^+(v)$ the number of outgoing edges of the vertex $v$...
96 views

### k-secretary problem: not knowing the length of the queue

The secretary problem is a famous and old problem. You can find the basic definition of this problem here: https://en.wikipedia.org/wiki/Secretary_problem Now I'm concerned with the k-secretary ...
240 views

414 views

67 views

### Matrix inequality $a X \succeq arcsin(X)$ for some $a > 0$

Let $X \in S^{n}_{+}$ be a positive semi-definite matrix with $X_{ii} = 1$ for all $i \leq n$ (thus $X$ is a correlation matrix). Since $X$ is positive semi-definite, we have $|X_{ij}| \leq 1$ for any ...
26 views

169 views

### Maximize sum of edge weights on spanning tree

Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$. Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
11 views

### Identifying essential degree constraints for ILP formulations of combinatorial optimal graph problems

Many combinatorial graph problems impose degree constraints on vertices; e.g. that the degree of every vertex in the solution to the TSP must be 2. In all LP-formulations I have encountered so far, ...
104 views

### maximum number of colors for an optimal tiling which guaranties infinite paths

This question is a more applicable version of the question I've asked in mathexchange recently: What is the maximum number of colors we can use to color $N^2$ square sub-tiles of $N×N$ square block ...
29 views

### Complexity of calculating the optimal amalgamation of an optimal cycle-cover

Let $G(V,E)$ be a complete symmetric graph with positive edge weights and let further $\mathcal{C}=\lbrace C_1,\,\cdots\,C_k\rbrace$ be the minimum-weight vertex-disjoint cycle cover. The set $E$ of ...
61 views

### Relationship between Wasserstein projections and metric projections in a linear space

Let $(X,d)$ be a metric space, $x\in X$, and $Y\subset X$ is a closed set. Assume that $X$ is also a real vector space, so that we can form linear combinations over $\mathbb{R}$, but I do not assume ...
116 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, ...
102 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 ...
170 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 ...
126 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 ...
17 views

### Is there one 1.5 approximate algorithm to solve edge-fixed TSP and TSP path?

Since we have a 1.5-approximate problem on TSP (Travelling Salesman Problem) and TSP path (under conditions of fixing the start point of the path or fixing one point or fixing two points of the path) ...
53 views

23 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 ...
35 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 ...
18 views

127 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 ...
71 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 ...
Given a complete symmetric graph $G(V,E)$ with $n\in\mathbb{N}$ vertices and edgeweights $\left|e_{ij}\right|\in\mathbb{R}^+$ What is known about algorithms and the complexity of finding a vector \$\...