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

**3**

votes

**0**answers

48 views

### What is the expected minimum total matching distance between two partitions of identically and independently distributed points?

Suppose a square $[0,1]\times [0,1]$ in which $N$ vehicles $V_i$ and $N$ riders $R_i$ are distributed identically and independently (say, uniform distribution), a bipartite matching (or a permutation, ...

**0**

votes

**1**answer

66 views

### How good is the LP relaxation?

Consider the optimization problem
\begin{align}
\max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i
\end{align}where $c,b\in\mathbb{R}_{+}^n$ and $A\in\mathbb{R}_{+}^{n\times n}$...

**3**

votes

**0**answers

54 views

### Optimizing a multivariate symmetric (permutation-invariant) function

Let $\ell$ and $d$ be two integers such that $\ell \le d$.
I would like to find the global maxima of the following symmetric function $f\colon (0,1]^n \to \mathbb{R}$,
$$f(x_1, \ldots, x_n) := \sum_{\...

**4**

votes

**1**answer

163 views

### Generalizations of the “Curious Tiger” Polygon

I actually don't know, whether the polygon I describe here already has name, but let me explain the problem, that is solved by the polygon, with a little story:
Imagine a flat terrain with bushes ...

**6**

votes

**2**answers

237 views

### Domination problem with sets

For nearly two years, I have been struggling with the next task I have already published on MSE, but unfortunately with no respond.
Let $M$ be a non-empty and finite set, $S_1,...,S_k$ subsets
...

**1**

vote

**0**answers

32 views

### Shortest Lattice Vector with restricted $x$

Let $\Lambda$ be a lattice with basis, $B$ consisting of vectors $b_i$, so that the elements of $\Lambda$ are of form, $y\in \Lambda \iff y=Bx=\sum_i b_ix_i$ for some $x_i\in\mathbb{Z}$.
My questions ...

**9**

votes

**0**answers

164 views

### Fundamental circuit characterization of matroid independence complexes

I have the following characterization of independence complexes of matroids, which I think is standard but I can't find a reference. Here it goes:
A pure simplicial complex $\Delta$ is the ...

**2**

votes

**0**answers

30 views

### Finding linear order of set maximising number of consecuitive subsets

I have the following combinatorial optimisation problem of which I think someone has probably solved it before. Has someone come across this problem before, maybe in a different setting than in the ...

**1**

vote

**1**answer

54 views

### Random Optimization on Graphs: Minimum Cut

Consider a complete graph on $n$ vertices. To each edge, $(i,j)$, we assign a weight, $W_{ij}$, which comes from some known distribution iid. Then, we ask the following question. Among all (weighted) ...

**8**

votes

**1**answer

174 views

### Making binary matrix positive semidefinite by switching signs

Let $A \in \{\pm 1\}^{n \times n}$ be a symmetric matrix whose diagonal entries are $+1$. Let $f(A)$ be the smallest number of signs we need to change in $A$ so that it becomes positive semidefinite (...

**0**

votes

**0**answers

28 views

### how to get this deterministic equivalent formulation of its original probabilistic counterpart by knapsack constraint?

I'm reading this article with title "a probabilistic model applied to emergency service vehicle location". https://www.sciencedirect.com/science/article/pii/S0377221708002336
This is a very good ...

**2**

votes

**1**answer

217 views

### The minimum rank of a matrix over GF(2) when part of non-zero off-diagonal elements are set to be zero

Given an $n\times n$ matrix $A$, whose elements are over $GF\left(2\right)$ and all diagonal elements are $1$. There are $m\ (m\leq n^2-n)$ non-zero off-diagonal elements in $A$. If we are allowed to ...

**1**

vote

**1**answer

42 views

### Optimal Graph Splitting

Question:
Given a finite symmetric TSP instance with $2n$ sites, what is the complexity of and what are algorithms for determining two sets of sites $A$ and $B$, each containing $n$ elemenents so that ...

**3**

votes

**2**answers

233 views

### A structural optimization problem

I have $n$ objects $O_i$, each of them having $3$ values, $O_i = (A_i, B_i, C_i)$. I am trying to group them into $k$ groups $P_u$ such as $P_u =(A_u, B_u, C_u)$ such that
$$\text{minimize} \quad \...

**0**

votes

**1**answer

47 views

### A simple quadratic integer optimization problem

Consider the following optimization problem in positive integers $n_1, n_2, n_3$.
$$\begin{array}{ll} \text{maximize} & n_1(n_2+n_3)\\ \text{subject to} & n_1+n_2+n_3 = N\end{array}$$
If $...

**2**

votes

**0**answers

75 views

### Largest number of sets $k$ among given $m$ sets that give union size lower than a given bound

Given $m$ sets $S_1, S_2, \dots, S_m$ and a bound $b$, find as many sets as possible among $m$ sets, says $S_{i_i}, S_{i_2}, \dots, S_{i_k}$ such that
$$\big| S_{i_i} \cup S_{i_2} \cup \cdots \cup S_{...

**1**

vote

**0**answers

20 views

### Divide and Conquer Heuristics for the Symmetric TSP

Question:
have there been serious attempts to design divide and conquer heuristics for generating near optimal Hamilton Cycles in complete symmetric graphs?
For clarification:
by a ...

**0**

votes

**0**answers

49 views

### Optimization Problem: Minimize the number of elements in a collection with constraints

Please feel free to help me phrase my question in a better way. I don't really know what kind of problem this is or what to call it other than its optimization.
The problem is:
For a multiset of ...

**0**

votes

**0**answers

9 views

### Computational complexity of Job Shop Scheduling problem with preemption for min mean flow time

What is the computational complexity of Job Shop Scheduling problem with preemption for the case of min mean flow time (i.e. min average time per job)?

**1**

vote

**1**answer

133 views

### Argmax of weighted sum of binomials

(Writing my thesis, I encountered the following problem. It is secondary to the topic of the thesis and I have the solution that is enough for the purposes of the thesis—but inner perfectionist ...

**0**

votes

**0**answers

27 views

### Algorithms for Balanced Coloring of Complete Symmetric Graphs

Question:
Has this the following problem already been studied:
given a complete, weighted, finite symmetric Graph $G$ with $kn$ vertices, assign to each of the vertices one color from $k$...

**1**

vote

**1**answer

94 views

### An variation of an assignment problem in combinatorics: assign items to customers

Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. ...

**0**

votes

**0**answers

86 views

### Is this Graph Iteration Already Known?

When attempting to set up an ILP formulation for a weight-minimal cubic spanning tree (i.e. one with vertex degrees either 1 or 3) I needed connectivity constraint, but misremembered the contents of ...

**0**

votes

**0**answers

19 views

### Calculation of Vertex Weights for Combinatorial Optimization of Regular Spanners

Vertex Weights are a means to modify the weight of an edge by adding to it the weights of its adjacent vertices. The motivation for adding vertex weights to edge weights is two-fold: the relative ...

**1**

vote

**0**answers

103 views

### Is the partition of bipartite graphs NP-hard?

I wonder if the following problem is NP-hard. Is it?
Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...

**0**

votes

**0**answers

21 views

### Complexity of Minimum Spanning Trees with Lower Degree Bounds

It is known, that the problem of calculating Minimum Spanning Trees with an upper bound on the vertex degrees is NP complete.
Question:
what is the complexity of calculating Minimum ...

**0**

votes

**1**answer

95 views

### Description of Linear Time Algorithm for TSP in Halin Graphs

I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in
"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling ...

**0**

votes

**1**answer

75 views

### Maximum partition of bipartite graph

Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...

**0**

votes

**0**answers

21 views

### Algorithms for Simple Paths with Minimum Cost-to-Time Ratio

This question is related to Graph-theoretic Algorithm for Path with Minimum Average Edge Length, but in this one is about the LP formulation.
Preconditional "facts":
Linear fractional ...

**5**

votes

**2**answers

187 views

### Factoring a positive semidefinite matrix into binary matrices

This question is motivated by a research problem I recently encountered. Consider two sets of random variables $\mathbf{X}$ and $\mathbf{Y}$, where $\mathbf{Y}$ can be expressed as a linear ...

**2**

votes

**2**answers

258 views

### How to label a tree with minimum cost?

Let $T = (V, E)$ be a tree. Let $\Sigma$ be a finite set of labels. Given a label function $\ell : V \to \Sigma$, the cost of $\ell$ is given by
$$\mu(\ell) = \left| \{(u,v) \in E \mid \ell(u) \neq \...

**2**

votes

**0**answers

46 views

### Hamiltonian cycle polytope for the hypercube graph

Let $Q_n$ denote the $n$ dimensional hypercube graph (i.e., graph formed from the vertices and edges of an n-dimensional hypercube). Denote the set of edges and vertices of $Q_n$ by $E_n$ and $V_n$ ...

**4**

votes

**1**answer

74 views

### Improved estimates of $n$ quantities via $n$ measurements

$\newcommand{\de}{\delta}
\newcommand{\De}{\Delta}
\newcommand{\ep}{\epsilon}
\newcommand{\ga}{\gamma}
\newcommand{\Ga}{\Gamma}
\newcommand{\la}{\lambda}
\newcommand{\si}{\sigma}
\newcommand{\Si}{\...

**1**

vote

**0**answers

40 views

### Off-line load in the balls-and-bins problem

In the balls-and-bins problem with $n$ balls thrown into $n$ bins, we seek to minimize the maximum load (i.e., number of balls in any bin). If each ball is given two choices, in the off-line setting ...

**0**

votes

**0**answers

16 views

### Algorithm for computing capacity of channel with additive colored Gaussian noise

I am looking for an algorrithm or Matlab/Python script for computing the capacity of additive colored Gaussian noise channel, according to the formula:
$$C=\frac{1}{n}\sum_{i=1}^{n}{\frac{1}{2}}\log\...

**0**

votes

**0**answers

113 views

### Symmetric Grothendieck inequality

Grothendieck's inequality states that for all $n \times n$ matrices $(a_{ij})$ such that
$$\max_{x \in \{\pm 1\}^n,\, y \in \{\pm 1\}^n} \left|\sum_{ij} a_{ij}\, x_i\, y_j\right| \leq 1,$$
there ...

**3**

votes

**0**answers

138 views

### Partitioning the coupons collected in the classical coupon collector's problem

Suppose that there is an urn containing $n$ different coupons, from which $m$ coupons are being collected, equally likely, with replacement.
Let $C(m)$ be the whole set of the $m$ collected coupons. ...

**5**

votes

**0**answers

79 views

### What is the LP gap of vertex cover in planar graphs?

What is the LP gap of vertex cover in planar graphs?
The LP I refer to is min $\sum_{e \in E } c_e x_e \ \ $ subject to $ \ \ x_v + x_u \geq 1 \ \ \ \forall uv \in E $
$ c_e \geq 0 $ are ...

**2**

votes

**1**answer

117 views

### Maximum rank in a class of $0\,$-$1$ partitioned matrices satisfying combinatorial constraints

We are given a matrix $M \in \{0,1\}^{n\times n}$ satisfying the following property.
The rows and columns of $M$ can be partitioned into $k$ rowgroups and $k$ colgroups respectively, such that in ...

**7**

votes

**2**answers

858 views

### Optimal Talmudic Zigzag

I have a finite sequence of positive real numbers $p_1,\dots, p_n$ and I am looking for a monotonically ascending sequence of indices $z_1,\dots, z_k$ that starts with $z_1 = 1$ and ends with $z_k = n$...

**1**

vote

**0**answers

115 views

### Submodular optimization over independent set

Given a graph $G=(V,E)$ and a submodular function $F:2^V\rightarrow[0,1]$, we seek an independent set $S$ of $G$ that maximizes $F(S)$. Is there any approximation algorithm solving this submodular ...

**0**

votes

**1**answer

73 views

### Average Edge-cost Optimality of MSTs

Are there counter examples to the conjecture, that in a complete, finite and symmetric weighted graph $G\left(V,E,\omega\right),\ E=\lbrace \lbrace i,j\rbrace\subset V\times V\rbrace,\ \omega:E\ni e\...

**4**

votes

**1**answer

379 views

### Combinatorial optimization problem for bipartite graphs

Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote ...

**3**

votes

**1**answer

147 views

### Algorithms for Fixing Sudokus

Suppose someone got stuck solving a Sudoku and asks you to figure out, what went wrong. Unfortunately that person only sends you a copy of the instance, where you neither see which of the numbers ...

**0**

votes

**0**answers

16 views

### Combinatorial Optimization with “Homogenic” Rational Objective Function

This is a followup question to Unconstrained Rational Combinatorial Optimization, where I asked for a solution of
$$\min_{\alpha \in \lbrace0,1\rbrace^n}\frac{\alpha^T w}{\alpha^T m},\quad w \in \...

**7**

votes

**0**answers

206 views

### Which continuous function is optimal for sieving?

In 1968, Barban and Vehov considered [1] the problem of determining for which continuous functions $\rho:\mathbb{R}^+\to [0,1]$ satisfying certain properties ($\rho(t)=1$ for $t\leq U_0$, $\rho(t)=0$ ...

**1**

vote

**1**answer

45 views

### Unconstrained Rational Combinatorial Optimization

When thinking up a new TSP heuristic, I encountered the following rational combinatorial optimization problem:
$$\min_{\alpha \in \lbrace0,1\rbrace^n}\frac{\alpha^T w}{\alpha^T m},\quad w \in \mathbb{...

**0**

votes

**0**answers

63 views

### Discrete primal-duality in optimization

I would like to inquire about the existence of something perhaps similar to the duality theorem in the convex analysis or convex programming in the discrete setting. Here is a concrete example.
Let $...

**5**

votes

**2**answers

161 views

### Determining the Largest Face of a Simplex

This question is in the vein of my former question Fast Comparing of the Volume of Simplices Defined by Sidelengths, but it has a different twist, that may allow for an easier answer:
Questions:
...

**1**

vote

**2**answers

157 views

### A variation of longest paths in directed acyclic graph

Let $D=(V,A)$ be a simple directed acyclic graph, where $A$ is a set of arcs. Let $S$ be a subset of $\{(u,v)| \text{there is a directed path from $u$ to $v$}\}$. The $S$-length of a path $P$ is ...