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