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
0
votes
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
3answers
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
1answer
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
0answers
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
0answers
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
0answers
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
3answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
1answer
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
1answer
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
0answers
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
0answers
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
0answers
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
0answers
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
2answers
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
1answer
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
0answers
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
1answer
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
1answer
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
0answers
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
1answer
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 ...

1
2 3 4 5