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
1
vote
1answer
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 ...
2
votes
1answer
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$...
0
votes
0answers
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 ...
4
votes
2answers
240 views

High degree differences in bipartite graphs

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us define the quantity: $$\mathcal{I}_k(G) := \sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\...
1
vote
1answer
69 views

Knapsack problem with capacity constraint

The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
15
votes
2answers
634 views

n sets, each is large, the intersection of every three is small, what is the size of the union?

Let $A_1, A_2, \ldots, A_n$ be $n$ sets such that: (1) for each $i\in [n]$, $\frac{n}{3}\leq |A_i|\leq n$; (2) for any $1\leq i<j<k\leq n$, $|A_i\cap A_j\cap A_k|\leq a$, where $a$ is a constant ...
4
votes
0answers
139 views

Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$

Crossposted at Theoretical Computer Science SE A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$....
1
vote
1answer
81 views

Knapsack problem with value range constraint

The traditional knapsack problem is that: given a sequence of $i$ items with positive weights $w_1,w_2,...,w_i$, positive values $v_1,v_2,...,v_i$, and a bag with capacity $B$, we want to insert items ...
0
votes
0answers
18 views

Probability that edge exchange yields a tour

let $H$ be a Hamilton cycle in a complete topological symmetric graph $G$ of finite size. Question: what is the probability that a vertex-disjoint cycle cover $C_k$ that is generated from $H$ by ...
1
vote
0answers
63 views

Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph

A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
0
votes
1answer
28 views

What's the meaning of this in equality in the lot-sizing and scheduling problem

I learned about the MILP models proposed by Pochet and Wolsey. Here are the formulations of one of these models(MILP3). So the decision variables and the primary formulation are as following: Based ...
0
votes
0answers
49 views

Bounds on the lengths of circuits in a metric space

Given a collection $V$ of $N$ points in a metric space $(M, d)$, I define a circuit as a sequence $w = (w_1, w_2, ..., w_N)$ which visits each point in $V$ and has a length given by $$|w| = \sum_{i=1}^...
9
votes
3answers
414 views

Pairs of vertices with high degree difference

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following quantity: $$\mathcal{I}_k(G) :=...
1
vote
1answer
35 views

$\mathrm{LP}$ formulation for $\mathrm{k}$-$\operatorname{opt}$ moves

$\mathrm{k}$-$\operatorname{opt}$ moves are an idea to improve non-optimal Hamilton cycles in weighted symmetric graphs by exchanging $\mathrm{k}$ tour-edges with $\mathrm{k}$ edges that do not belong ...
1
vote
1answer
54 views

Column subset selection with least angle optimization

Given a matrix $A$ I need to select a "representative" subset of its columns so that the each non-selected column is as close as possible to a selected one. Formally: Given $A \in \mathbb{R}...
0
votes
1answer
104 views

What is the computational complexity of the calculation of $ \Psi(x) $?

What is the computational complexity of the calculation of $ \Psi(x) $ described below: Let $\left\{ f_i : \{0,1,\dots,m\} \to \mathbb{R} \right\}_{i=1}^n$. For each $x \in \{0,1,\dots,m\}$ we ...
2
votes
0answers
118 views

Maximum number of regions in a disk partitioned by pairs of parallel chords

We are given a disk $D$ in $\mathbb{R}^2$. Let $C$ be its boundary (i.e., the circle bounding $D$ on its plane). Let $P(n,d)$ be a set of $n$ pairs of chords of $C$ such that for each $\{c,c'\}\in P(n,...
1
vote
1answer
34 views

Relation of 1-trees to optimal tours

Question: given a complete symmetric graph $G(V,E)$ with $n$ vertices and edges $e_{ij}$ having weight $\omega_{ij}$, does there always exists a vector of vertex potentials $(\pi_1,\,\dots,\,\pi_n)$ ...
1
vote
0answers
57 views

Monotone rearrangements of function, constrained optimization in $\mathcal{L}^p$

By $\mathcal{S}$ let us denote the set of such step functions $f:[0,1]\to [0,1]$ that additionally satisfy: $$\forall_{ x>\frac{1}{2}} \ \ \lambda\Big(f=x\Big) \ = \ x\cdot \Big[\lambda\Big(f=x\Big)...
3
votes
0answers
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 ...
1
vote
0answers
26 views

Term or reference for a set of integer edge weights to guarantee distinct weighted degrees

I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(...
0
votes
1answer
69 views

A question on graph partitioning

Given a connected un-directed simple graph $G=(V,E)$, is there a polynomial time algorithm to find the smallest subset $S$ of $V$ such that each node in $V \setminus S$ has at least 50% of its ...
0
votes
0answers
34 views

Examples of recursive TSP heuristics

Question: What are examples of heuristics for the Traveling Salesman Problem, that are recursive in the sense that they can efficiently calculate the shortest Hamilton cycle in a graph if the optimal ...
0
votes
0answers
17 views

Complexity of heaviest 2-optimal vertex-disjoint cycle covers

Calculating lightest vertex-disjoint cycle covers of finite complete symmetric graphs with weighted edges can be done efficiently and also renders the edge set of the calculated cycles free of pairs ...
1
vote
0answers
24 views

Optimality of trees generated via edge exchanges

let MST be the minimum spanning tree of a weighted finite graph; what can be said about the weight-optimality of the trees generated from the MST by sequentially exchanging a tree edge with a non-tree ...
0
votes
0answers
36 views

How to prevent spanning trees from spiraling

Spanning trees and especially minimum spanning trees are the anchor point of a whole class of TSP heuristics, most prominently the Christofides algorithm. I noticed however that there may be MSTs for ...
0
votes
0answers
12 views

Optimality of a heuristic for conflict resolution

Given a set $\Sigma$ of items of which each element $e$ has value $\omega_e$ and a subset $\chi_e\subseteq \Sigma\setminus e$ of incompatible items. Question: what is known about the heuristic of ...
1
vote
0answers
57 views

Generating triangulations with given topology

I am looking for information about the problem of identifying the heaviest minimal subset $F\subset E$ of the edgeset $E$ of a complete symmetric graph $G(V,E)$ with randomly weighted edges such that ...
3
votes
0answers
66 views

Additional symmetries of the Traveling Salesman Polytope

Given the complete graph $K_n=(V,E)$, the Traveling Salesman Polytope is a convex polytope in $\Bbb R^E$ obtained as the convex hull of the indicator vectors of (edge-sets of) Hamiltonian cycles in $...
0
votes
1answer
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]$, ...
0
votes
0answers
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, ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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, ...
2
votes
0answers
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 ...
7
votes
1answer
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 ...
3
votes
1answer
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 ...
0
votes
0answers
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) ...
2
votes
0answers
53 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=...
5
votes
1answer
214 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=...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
18 views

How to define optimal substructure in graph search problems if the edges are functions instead of weights?

Consider a graph $G = (V,E)$ where each edge is associated with a parameter $\theta$ where the parameter is a vector and is constant for each edge. For example, edge $e_{ij}$ from $v_i \in V$ to $v_j \...
0
votes
0answers
14 views

Hardness of finding optimal tours in Hamiltonian Apollonian gaskets

Given an euclidean planar TSP instance where the cities are the centers of the disks of an Apollonian gasket for which the contact-graph that is induced by the disks is Hamiltonian, it is a trivial ...
1
vote
0answers
21 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:\ \...
6
votes
1answer
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 ...
1
vote
0answers
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 ...
6
votes
2answers
320 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 ...
0
votes
0answers
12 views

Calculating vertex-weights for generating graphs that are critically free of negative cycles

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 $\...

1
2 3 4 5
7