# 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
Filter by
Sorted by
Tagged with
23 views

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

I hope you are well. I have a non-continuous optimization problem as follows; ...
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 ...
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 (...
13 views

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 ...
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 ...
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 ...
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 ...
82 views

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}}.$$...
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]$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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; ...
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 ...
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 ...
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 ...
47 views

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