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