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

241
questions

**0**

votes

**0**answers

23 views

### How to solve this non-continuous optimization problem?

I hope you are well. I have a non-continuous optimization problem as follows;
...

**0**

votes

**0**answers

38 views

### Gröbner basis and integer programming

I was studying about grobner basis and observed one application of it in integer programming which is pretty much amazing but tougher than available methods like branch bound. Then what is the benefit ...

**0**

votes

**0**answers

10 views

### Finding weight minimal swap-free directed vertex covers

Suppose a complete directed graph is given with $n$ vertices and $n(n-1)$ weighted arcs $a_{ij}$ and we have $\omega(a_{ij}\ne\omega{a_{ji})$ for at least one pair of antiparallel arcs and the ...

**4**

votes

**1**answer

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

**1**

vote

**1**answer

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

**0**

votes

**1**answer

25 views

### Basis pursuit algorithms for exponentially large matrices?

Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is $\arg\min_x\lVert x \rVert_0$ subject to $y = Ax$, where $A$ is an exponentially large matrix ...

**0**

votes

**1**answer

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

**4**

votes

**3**answers

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

**0**

votes

**1**answer

48 views

### Minimize overlap penalty between paths in graph

Suppose we have a weighted undirected graph $G(V,E)$. We are given the information that $V_a \cap V_b = \emptyset$ and $V_a,V_b \subset V$.
We want to find paths from all vertices in $V_a$ to all ...

**1**

vote

**1**answer

64 views

### Algorithm for finding minimally overlapping paths in a graph

I'm curious to find an algorithm that solves the following graph-theory problem.
Suppose I have a graph $G(V,E)$ with two disjoint sets of vertices, $V_a$ and $V_b$.
My goal is to find paths from ...

**1**

vote

**0**answers

128 views

### Algorithmic combinatorial discrete problem (randomized lazy update?)

We are given a vector $\mathbf{b}$ of size $h$. Initially we have $\mathbf{b}_i=1$ for all $i\in \{1, 2, \ldots, h\}$. In a sequential fashion, at each time step $t=1, \ldots, n$, an index $j(t)$ is (...

**0**

votes

**0**answers

13 views

### Defining planar geometric shape hulls via graph connectivity

A fundamental problem in Computational Geometry is to generalize convex hulls to simple polygons that partition a given finite set $\boldsymbol{P}$ into two sets $\boldsymbol{C}$ of corners and $\...

**0**

votes

**0**answers

47 views

### Shortest path in a k-partite graph which passes through each partition exactly once

Suppose $G$ is a connected undirected positive edge-weighted k-partite graph, and let $G_1, \cdots, G_k$ be the vertex partitions. Also assume that $G_1$ and $G_k$ have exactly one vertex each, call ...

**2**

votes

**2**answers

136 views

### Transforming an optimization problem to maxmin formulation

Given $N=mn$ real numbers $a_i$, we seek to partition them into $n$ subsets $S_j$ ($1\le j\le n$), each containing $m$ numbers, so as to maximize $\prod_{j=1}^n \sum_{a_i\in S_j} a_i$. My questions ...

**1**

vote

**0**answers

41 views

### Upperbound on Shannon capacity of graph and strong product of graph

Given a Graph $G = (V=[n],E)$, if a symmetric matrix $B$ fits $G$, it has non-zero diagonal elements and 0 on off-diagonal entries if $\{i,j\}$ are non-edge in $G$.
Let \begin{equation}
R(G) = \min ...

**1**

vote

**1**answer

80 views

### Eigenvalues of adjacency matrix of a k-regular graph

If $A_G$ is the adjacency matrix of a k-regular graph, let $B = J+xA_G$, where J is the matrix whose elements are all 1s and $x\in R$ is a scalar. If $\lambda_1\geq\lambda_2\geq \dots \geq \lambda_n$ ...

**0**

votes

**0**answers

66 views

### Maximize sum of supermodular functions over nested sets

Let $R$ be a function that maps a set and a positive integer to a real positive number. We have that for any positive integer $t$ and $S \subseteq \{1, \ldots, t\}$, $R(S, t)$ satisfies:
For all $t &...

**0**

votes

**0**answers

20 views

### Heuristics for the heaviest eulerian subgraph

Given a complete symmetric graph with $n=2k$ vertices and positive edgeweights, are there any better algorithms for determining the heaviest eulerian subgraph than this one that strives for finding ...

**0**

votes

**1**answer

87 views

### longest possible chain from a collection of ordered pairs/ co-ordinates [closed]

I have a bunch of ordered pairs x, y where 0 < x < y <= n (some given upper bound)
like S = [(1,2), (1,3), (1,4), (2,3), (3,4)]
I need to find the Length of the longest subset where all the ...

**3**

votes

**0**answers

67 views

### Minimizing weight values while preserving the collection of maximum-weight independent sets

Consider an undirected graph $G = (V,E)$ with a weight function $w \colon V \to \mathbb{N}$ on its vertices. Let $\alpha_w(G)$ denote the maximum weight of an independent set in $G$, i.e., the maximum ...

**7**

votes

**1**answer

260 views

### Sum of degree differences for simple graphs

For a simple graph $G$ on $n$ vertices, let us define
$$\mathcal{I}_{n}(G)=\sum_{i,j=1}^{n}|\deg\ x_{i}-\deg\ x_{j}|^{3}.$$
I know that there are many different topological indices defined and ...

**1**

vote

**1**answer

82 views

### Find the largest subset of all binary arrays of length $n$ with $r$ ones which have pairwise distance greater than $m$

Let $\Omega = \left\lbrace x : |x| = r \, \text{for} \, x \in \mathbb{Z}_2^n \right\rbrace$ for $r \in \mathbb{N}$. We want to find the the biggest subset of $\Omega$, $\Gamma = \left\lbrace x \in \...

**-1**

votes

**1**answer

42 views

### What is known about iterated matching as a TSP heuristic

A fairly wellknown heuristic for TSP that is based on matching is described in the 2003 paper Match twice and stitch: a new TSP tour construction heuristic by Andrew B. Kahng and Sherief Reda.
Its ...

**0**

votes

**0**answers

32 views

### Reasons for inapplicability of complete induction to tour expansion

It is known that tour expansion is a rather poor heuristic for generating short Hamilton cycles even in the planar Euclidean case. That comes as a surprise when learning of that for the first time.
...

**1**

vote

**1**answer

82 views

### Looking for an efficient way of maximising 'pair scores' for subset of 30 selected from 50 to 10 000 objects

Context: I have a tiling program that uses a directed breadth first search algorithm. It is 'directed' by what I call 'pair scoring'. There are $N$ polyforms (pieces) used in the tiling. I have an $N\...

**5**

votes

**3**answers

480 views

### Optimization algorithm sought

Suppose I have $N$ pairs of positive numbers $(a_1, b_1), (a_2, b_2), \dotsc, (a_N, b_N).$ and I want to find a subset of $M$ of them maximizing
$$
\frac{\sum_{j=1}^M a_{i_j}}{\sum_{j=1}^M b_{i_j}}.
$$...

**1**

vote

**1**answer

70 views

### What is the minimal possible size of a subset of this semigroup satisfying the following conditions?

Suppose $A$ is some set. Let's define a pair semigroup over $A$ as $P[A] = (A\times A \cup \{0\}, \circ)$, where the $\circ$ operation is defined by the following two identities:
$\forall a \in P[A]$ ...

**0**

votes

**0**answers

44 views

### Maximizing a non-monotone possibly-negative function

I have been doing a little literature review of submodular optimization.
Something struck me as strange: while there is a greedy algorithm that gives you a optimality bound for a monotone submodular ...

**1**

vote

**0**answers

23 views

### Filtering optimization problem

First, let me give you some background. I develop embedded software and I have a filtering problem where I think I could use some help from mathematicians.
I have a filtering table which has the ...

**2**

votes

**0**answers

50 views

### A combinatorial question about encoding the subsets of logarithmic-bounded cardinality

Let $k \in \mathbb N - \{0\}$ and $f(n) = \binom n 0 + \binom n 1 + \dotsc + \binom n {\log^k n}$.
Our question is:
$f(n) = o(2^{\log^{k+1} \ (n)})$ or $f(n) = \Theta(2^{\log^{k+1} \ (n)})$, which ...

**0**

votes

**3**answers

287 views

### Im looking for an algorithm that can solve or approximate the solution to a problem

Let me first explain the problem using an analogy.
Let's say you have $N$ doors and $M$ keys. Each door can be opened with a combination of keys, each combination is also unique (i.e. there aren't be ...

**0**

votes

**0**answers

45 views

### Resource Allocation Problem

The following problem:
$$\max\sum_{i=1}^Ng_i(x_i)$$
$$\text{a.s. }\quad x_1+x_2+\ldots +x_N\leq b$$
where $b\geq0$ integer and $x_i\geq 0$ integer, $g_i(0)=0$ for each $i=1,2,\ldots,N$.
It is the ...

**0**

votes

**1**answer

75 views

### Probability that the solution to a combinatorial optimization problem changes after random modifications

given a combinatorial optimization problem, say the Traveling Salesman Problem, the optimal solution is a set of elements (edges in this case) that satisfy certain constraints (constituting to a ...

**2**

votes

**1**answer

84 views

### Worst case performance of heuristic for the non-eulerian Windy Postman Problem

The Windy Postman Problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in ...

**2**

votes

**0**answers

43 views

### Proof for the NP-hardness of the Max-3-DCC Problem

The Max-3-DCC is the variant of vertex cycle cover problem where each of the vertex disjoint oriented cycles consists of at least 3 arcs and every vertex belongs to exactly one of those cycles; ...

**0**

votes

**0**answers

34 views

### Transformation of asymmetric traveling salesman problems into Chinese postman problems

I have found transformations of Chinese Postman Problems (CPPs) into Asymmetric Traveling Salesman Problems (ATSPs), but didn't find anything about transformations in the opposite direction.
Having ...

**1**

vote

**0**answers

34 views

### Determining the minimum weight maximal oriented subgraph of a complete directed graph

Let $G(V,A,W):\ |V| = n,\ A=V\times V\setminus \lbrace (v,\ v)\rbrace,\ W\in\mathbb{R}_+^{n\times n},\ W^T\ne W $ be a complete directed graph with asymmetric weights.
Questions:
What is ...

**1**

vote

**1**answer

56 views

### Tighter lower bound of the lower triangular sum of an arbitrary Latin square

In this math.stackexchange.com question I seek a tighter bound than the one I presented in there in the question. Rob Pratt puts forth a conjecture in his answer motivated by the dual problem of the ...

**0**

votes

**1**answer

47 views

### Variant of the linear programming problem

Good afternoon, my experience in mathematical programming is low. I would like to know if there is any general method to address the following problem:
$$\text{Minimize }\sum_{i=1}^n d_i(x_j)$$
$$s.a....

**1**

vote

**0**answers

18 views

### Generalization of Nemhauser's theorem for submodular functions

Nemhauser's theorem shows that if $f:2^{\Omega}\to \mathbb{R}$ is a monotone and submodular function, then greedy algorithm gives $(1-e^{-1})$-approximation of optimal solution. More precisely, we ...

**0**

votes

**0**answers

62 views

### Linear-algebraic simplification of the Smallest Grammar Problem

I don't get any people interested on MSE usually with this type of problem, and it is an untried idea. So I'm testing the waters out here. :)
The smallest grammar problem problem once solved will ...

**1**

vote

**0**answers

78 views

### Binary search extension for determining a hyperplane splitting a set of points in $\mathbb{R}^d$

We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\...

**1**

vote

**0**answers

78 views

### Maximum number of ways of splitting a set of points with an hyperplane

Given a set $S$ of $n$ points in $\mathbb{R}^d$, let $D_S$ be the set
$\{\mathbf{v}=|\mathbf{u}-\mathbf{u'}|: \mathbf{u},\mathbf{u'}\in S\}$ (where $\forall i=1,2,\ldots, d$, $\mathbf{v}_i=|\mathbf{u}...

**4**

votes

**2**answers

138 views

### Exactness of the semidefinite programming (SDP) relaxation of maximum cut (Max-Cut)

Currently, what conditions are known to be sufficient for the SDP relaxation of Max-Cut to be exact?

**1**

vote

**1**answer

159 views

### $0$-“norm” minimization with least-squares regularization

I have the following optimization problem in $\mathbf{x} \in \mathbb{R}^{K \times 1}$
$$\min_{\mathbf{x}>0} \quad \|\mathbf{A}\mathbf{x}\|_0 + \alpha \|\mathbf{B}\mathbf{x}-\mathbf{c}\|_2^2$$
...

**2**

votes

**0**answers

181 views

### The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...

**5**

votes

**1**answer

152 views

### Do the Odd Cycles of a Graph Define a Matroid?

An Odd Cycle Transversal is a set of vertices that, when removed from a graph, renders it bipartite.
Question:
does the collection of "critical" sets of vertices, whose removal renders a ...

**6**

votes

**1**answer

379 views

### Creating many big sets of small numbers

There are $n$ numbers $a_1,\ldots,a_n\in [0,1]$.
Their sum is $\sum_{i=1}^n a_i = s$, where $s$ is some integer.
We want to group them into sets so that the sum of each set is at least $t$, where $t$...

**2**

votes

**0**answers

22 views

### Complexity of weighted fractional edge coloring

Given an edge-weighted multigraph $G=(V,E)$ with a positive, rational weight function $(w(e): e \in E)$, the weighted fractional edge coloring problem (WFECP) is to compute ($\min 1^T x$ subject to $...

**3**

votes

**1**answer

277 views

### Sequential prize searching

There are $N$ rooms. In each room $i$, with probability $p_i$ one can find a prize. The cost of searching room $i$ for the prize is $c_i$. A user can search at most $n$ out of $N$ rooms. If a prize is ...