Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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