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
2 votes
0 answers
132 views
+50

Electricity division and bin packing

In the electricity division problem, there is a powerhouse that supplies $s$ kilowatt of electricity. There are $n$ households. The connection size of household $i$ is $d_i$. The problem is that $s &...
Erel Segal-Halevi's user avatar
2 votes
0 answers
124 views

How to prove this weighted sum inequality with non-increasing sequences?

Problem I have two non-increasing sequences, $X = (x_1, x_3, x_5, \ldots, x_{n-1})$ and $Y = (y_1, y_3, y_5, \ldots, y_{n -1})$, $n$ is an even integer. I want to prove this inequality: $$ \sum_{i=1}^{...
birdlpy's user avatar
  • 29
6 votes
1 answer
309 views

Maximizing a sum minus its maximal summand

This is a followup to a question that appeared on m.SE: Maximize $\displaystyle f(\pi)=\left(\sum_{i=1}^{n}{i\pi_i}\right)-\max_{1\le i\le n}{(i\pi_i)}$ over permutations $\pi\in S_n$. The problem ...
Alexander Burstein's user avatar
1 vote
0 answers
61 views

Maximum trace of powers of symmetric $\{0,1\}$-valued matrix with fixed row and column sums

Maximize $\operatorname{tr}(A^k)$ over binary symmetric $n$ by $n$ matrices subject to $$a_{ii}=0, \sum_{j=1}^n a_{ij}=d, \sum_{i=1}^na_{ij}=d,$$ where $d,k$ are fixed positive integers. I am having ...
ComfySofa's user avatar
0 votes
0 answers
50 views

An $n$-dimensional generalized Hoffman’s circulation theorem?

For a directed graph $G$, a 1-dimensional circulation is a function $f:E(G)\rightarrow \mathbb{R}$ such that for every $v\in V(G)$, $$\sum_{uv\in E(G)}f(uv)=\sum_{vw\in E(G)}f(vw),$$ where $uv$ is an ...
Connor's user avatar
  • 251
0 votes
1 answer
66 views

Graph vertices selection for paths sum minimalization

Let $G = (V, E)$ be a simple, finite, weighted, undirected, connected graph. Let $P = \{p_{ij}, p_{kl}, p_{il}, ... \}$ be a set of paths, where $p_{ij}$ is a path from $i$-th to $j$-th vertex. Is ...
Tomasz Rybotycki's user avatar
1 vote
0 answers
43 views

Hardness of an optimization problem when some variables are fixed

Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed. With the two (related) examples, it is clear that ...
Ro. Cohof's user avatar
2 votes
0 answers
44 views

Size of set of positive integers no sum of two distinct elements giving square

Question: find the size of a maximal subset $A$ of $[n]=\{1,\cdots,n\}$ satisfying that for any distinct elements $x,y\in A$, $x+y$ is not a perfect square. Consider a graph with $n$ vertices: $x$ and ...
Haoran Chen's user avatar
2 votes
1 answer
122 views

Optimization over permutation

The Problem This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
Honglian's user avatar
0 votes
0 answers
56 views

Optimal top-k column subset

Let $V$ be a set of vectors over $\mathbb{R}^l$, $l\ge 1$, $\pi_i(V)$ be the permutation of vectors in $V$ such that they are ordered by their $i$th component (descending) in order for $\pi_i(V)(\...
Eli Bixby's user avatar
  • 101
2 votes
0 answers
81 views

Can we say this nonlinear integer programming problem is NP-hard?

I was wondering if the following nonlinear integer programming problem is NP-hard or not. $$\max_{x_i \in \{0,1\}} \frac{\sum_{i=1}^{n}a_i x_i}{\sqrt{\sum_{i=1}^{n}b_i x_i}}$$ such that $\sum_{i=1}^{n}...
Anson's user avatar
  • 21
2 votes
1 answer
168 views

Discrete maximization of geometric mean - reference request

This is a follow-up to my previous MO question: A discrete optimization problem related to the AM-GM inequality Let $n,k$ be integers such that $1\le k\le n$. Define the quantity $$ P(n,k):=\max\ a_1\...
Abdelmalek Abdesselam's user avatar
0 votes
1 answer
61 views

Optimality of a "shopping" heuristic

Suppose the following situation: we have to buy $n$ goods $g_1,\,\dots,\,g_n$ starting at day 1 and we can't buy more than one good per day. On day $d$ the prices are $p_1^d,\,\dots,\,p_n^d;\quad p_i^...
Manfred Weis's user avatar
  • 12.4k
6 votes
1 answer
327 views

Desargues ten point configuration $D_{10}$ in LaTeX

I want to draw the Desargues configuration $10_3$ in LaTeX using the standard picture environment, which allows only lines with the slopes $n:m$ where $\max\{|n|,|m|\}\le 6$. Is it possible? If not, ...
Taras Banakh's user avatar
  • 40.1k
0 votes
1 answer
48 views

Real-world datasets for testing the maximum edge bi-clique problem

We have proposed a new approach to solve the maximum edge bi-clique problem, however, we couldn't succeed to find real-world datasets (graph or bipartite graph datasets) to test our approach. Does ...
Salma Omer's user avatar
2 votes
0 answers
66 views

What is an efficient non-adaptive group testing scheme if the number of defectives, $d$, grows proportionally to the number of items, $n$?

Suppose that for some $p \in \left(0, 1\right)$ and some $n \in \mathbb{N}$, we have $n$ independent Bernoulli random variables, $X_{1}, X_{2}, \dots, X_{n}$, each with mean $p$. We shall call $X_{1}, ...
Matthew Barber's user avatar
3 votes
1 answer
125 views

How to turn $\{-1, 0, 1\}$-valued optimization problem into integer program?

For an $n \times n$ matrix $M$, the $\infty\to 1$ and cut norms are given by $$\|M\|_{\infty \to 1} := \max\limits_{x, y \in \{\pm 1\}^n} \sum\limits_{i, j} m_{i, j} x_i y_j, \qquad \|M\|_{\square} :=...
Display name's user avatar
0 votes
0 answers
20 views

LP formulation of $k$-opt moves

Question: what is known about formulating $k$-opt moves that strive for improving the length of Hamilton cycles by means of exchanging $k$ of the tour edges with $k$ non-tour edges? Specifically: are ...
Manfred Weis's user avatar
  • 12.4k
1 vote
0 answers
100 views

On determinant and permanent of certain homotopy defined simple matrices

Let $A_1,A_2,B_1,B_2$ be four $n\times n$ $0/1$ square matrices where $$\det(A_1)=\det(A_2)=per(A_1)=per(A_2)=1$$ $$\det(B_1)=\det(B_2)=per(B_1)=per(B_2)=0$$ hold ($per$ refers to permanent). I. What ...
Turbo's user avatar
  • 13.5k
2 votes
0 answers
47 views

Properties of the "girth function" of a matroid

Given an independent set representation of a matroid $M=(E,\mathcal{F})$ its ``rank function'' $r$ defined on the powerset of $E$ is: $$ \forall X \subseteq E, \quad r(X) = \max_{Y \subseteq X}\{|Y|, ...
Felix Goldberg's user avatar
0 votes
1 answer
135 views

A variation of Set Cover

Suppose we have $n$ sets $\{S_i\}_{i=1}^n$, each containing exactly $k$ of the numbers from $1,...,n$. The union of all these sets will cover $1,...,n$. We know $i \in S_i$ for all $i$. We need to ...
Jackson's user avatar
1 vote
0 answers
48 views

Knotted Traveling Salesperson route

Let us consider fixed points in space, if we apply the well-known Traveling Salesperson Problem algorithm, we get the shortest route. It can give a nontrivial knot in the three-space. The question is ...
knotMJ's user avatar
  • 71
1 vote
0 answers
40 views

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following

How to embed an arbitrary graph into (k,d)-kautz space (like multidimensional scaling of non-normed space)? See details in the following. Given a graph $G = \{V,E\}$, we have a distance matrix (the ...
Yichuan_Sun's user avatar
2 votes
0 answers
116 views

How to solve $\min_{\mathbf{x}\in \{\pm 1\}^N} \lVert \operatorname{sign}(\mathbf{Wx}) - \mathbf{y} \rVert_2^2$ where $\mathbf{y}\in \{\pm 1\}^N$?

Given the matrix $\mathbf{W} \in \mathbb{R}^{N \times N}$ and the vector $\mathbf{y} \in \{\pm 1\}^N$, how to solve $$\min_{\mathbf{x}\in \{\pm 1\}^N} \left\| \operatorname{sign}(\mathbf{Wx}) - \...
user3750444's user avatar
1 vote
2 answers
114 views

How to solve the optimization problem $\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$?

I am looking for an algorithm to solve the following optimization problem $$\max_{\mathbf{w}}\sum_i\text{sign}(\mathbf{w}^T \mathbf{x}_i)$$ where $\mathbf{w}$ and each $\mathbf{x}_i\in\mathbb{R}^d$. ...
user3750444's user avatar
11 votes
2 answers
588 views

A discrete optimization problem related to the AM-GM inequality

Let $k\in\mathbb{Z}_{>0}$, and $s\in\mathbb{N}$, and for $m_1,\ldots,m_k$ some nonnegative integers, consider the problem of maximizing the product $$ (1+m_1)(1+m_2)\cdots(1+m_k) $$ under the ...
Abdelmalek Abdesselam's user avatar
11 votes
0 answers
430 views

What sequence maximizes the final distance?

This problem was created by professor Ronaldo Garcia from Universidade Federal de Goiás (UFG) and he showed it to me at an event in my university. This problem has a lot of history and he told me he ...
Arthur Queiroz Moura's user avatar
0 votes
0 answers
13 views

Counterexample to non-optimal symmetric edge detection heuristic

The undirected TSP problem allows for the efficient detection of Nonoptimal Edges for the Symmetric Traveling Salesman Problem It is also known that the edges that constitute to the heaviest perfect ...
Manfred Weis's user avatar
  • 12.4k
0 votes
0 answers
52 views

Greedy algorithm for color-balanced spanning tree

Given a graph $G = (V, E)$, we can partition $E$ to $p$ disjoint colors, i.e., $E = S_1 \cup S_2 \cup \cdots \cup S_p $. The goal of color-balanced spanning tree problem is to find a spanning tree $T$...
Honglian's user avatar
4 votes
0 answers
217 views

What does the best die look like?

Intransitive dice have attracted a lot of attention - especially in the context of recreational math - since their introduction by Efron in the 1960s. More recently, there has been work studying ...
Sam Hopkins's user avatar
  • 21.5k
0 votes
0 answers
114 views

On the absolute difference of the Laplacian eigenvalues of an unbalanced signed graph and its underlying graph

Let $\Sigma=(G,\sigma)$ be an unbalanced signed graph with the underlying connected graph $G=(V,E)$ and $\sigma:E\rightarrow \{-1,1\}$, the signing function. Let the Laplacian eigenvalues of $\Sigma$ ...
shahulhameed's user avatar
0 votes
0 answers
18 views

ILP formulations for tour-improvements

Question: what is known about the problem of formulating tour-improvement as an integer linear problem (ILP)? To be specific: what are necessary and/or sufficient constraints, besides the degree-...
Manfred Weis's user avatar
  • 12.4k
0 votes
0 answers
52 views

Maximum number of h-dimensional hyper-edges without forming any (h+1) complete subgraph

This is about graph theory. Define an h-dimensional hyperedge as a set that contains h vertices. A graph of (h+1) vertices is h-complete if any h combination (or any subset with size h) is an h-...
TanG's user avatar
  • 23
1 vote
0 answers
51 views

A multi-layer version of Menger's theorem

Menger's theorem says that the maximum number of pairwise disjoint paths between two vertex sets $L,R$ of a graph G equals the minimum size of an $L$-$R$ separator. Below is a generalisation with more ...
Agelos's user avatar
  • 1,854
2 votes
1 answer
167 views

Can information theory characterise a (topological) space?

Consider an objective function f: $\mathbb{R}^n\rightarrow\mathbb{R}$, with a vector of variables $\theta$, i.e. $f(\theta)$, $\theta \in \mathbb{R}^n$. Depending on $f$, there can be interesting ...
Tessa van der Heiden's user avatar
2 votes
1 answer
89 views

How to prove the local search algorithm can find the maximum weight independent set in a matroid with cardinality constraint?

I am trying to prove a simple local search algorithm could solve exactly this problem: $\underset{S \in I(M), |S|=k}{max} c(S)$ where $M$ is a matroid, and $ I(M)$ is the set of all independent set, $...
Honglian's user avatar
1 vote
1 answer
90 views

Minimum set of numbers which covers all the values of all digits

Introduction Let's consider binary numbers for simplification and let's consider 4 bits numbers. Sets which answer my problem are: ...
user496620's user avatar
0 votes
1 answer
108 views

Traveling salesperson problem algorithm [closed]

I was wondering something, let's say in a symmetric distance matrix of a sample of TSP, there was a sure algorithm that could remove between 30% to 80% of the values (distances) that wouldn't ...
Ehsan Javanbakht's user avatar
3 votes
1 answer
279 views

How to find the maximum of a sum of squares of sums?

Is there any better than a brute force method for finding the maximum $$\max\limits_{ (d_{1},\dots,d_{n}) \in \mathbb Z_{m}^{n}} \sum_{j=0}^{m-1} \left(\sum_{i=1}^{n}v_{i,(j+d_{i})\bmod m}\right)^{2}$$...
user avatar
3 votes
0 answers
97 views

The matrix representation of an interval graph

It is well-known that many classes of graphs have matrix representations that can be written concisely. For example, The set of all directed acyclic graphs consists of binary matrices $x_{ij} \in \{...
Tom Solberg's user avatar
  • 3,868
3 votes
1 answer
135 views

Algorithm for finding a minimum weight circuit in a weighted binary matroid

For a given weighted graph $G = (V, E)$, there is a simple algorithm for finding the minimum weight circuit by running Dijkstra's algorithm $|E|$ times. Also for a matroid $M = (E, I)$ one can use the ...
Patrik Pavic's user avatar
0 votes
0 answers
114 views

Conjecture on the unsolvability of the $\{3 \times 3 \times \cdots \times 3\} \subseteq \mathbb{R}^k$ dots problem starting from the central point

In 2020 (see Solving the $106$ years old $3^k$ points problem with the clockwise-algorithm, JFMA, 3(2), p. 96), I conjectured that, in the Euclidean space $\mathbb{R}^k$, we can cover any given set of ...
Marco Ripà's user avatar
3 votes
0 answers
188 views

Probabilistic optimization problem on tree vertex selection without replacement proportional to the degree

We are given a tree $T(V,E)$ with $|V|=n$ vertices, where $V=\{v_1,v_2,\ldots, v_n\}$. We denote by $d_i$ the degree of vertex $v_i$ for all $i\in\{1,2,\ldots,n\}$. In a sequential fashion, we select ...
Penelope Benenati's user avatar
0 votes
0 answers
84 views

Boolean operation on n dimensional polyhedron

A polyhedron in $R^n$ is defined by a set of half-planes: $P = \{x \in R^n \mid Ax - b \le 0\}$. Given a set of polyhedra in $R^n$, $ P_1, P_2, \dotsc, P_k$, is there an algorithm/implementation that ...
Robin Lee's user avatar
2 votes
0 answers
99 views

Optimization problem on randomly selecting subintervals from a given interval with combinatorial constraints

We select uniformly at random $k$ pairwise disjoint intervals from a given interval $[0,s]$ with length respectively equal to $\ell_1, \ell_2, \ldots, \ell_k\ $, i.e., we select uniformly at random $k$...
Penelope Benenati's user avatar
1 vote
1 answer
482 views

Finding an optimal covering trail for the set $\{0,1,2,3\}\times\{0,1,2,3\}\times\{0,1,2,3\}$

Here is a key question (i.e., Question 2 below) that, if correctly answered, would let me support a very general conjecture on a wide class of related problems, a conjecture that I have never shared ...
Marco Ripà's user avatar
0 votes
1 answer
57 views

Dual equivalence of minimum feedback-vertex sets and cycle packing

it is known that the duals of feedback-set problems are set-packing problems; in the context of digraphs the feedback set are either a minimal set of vertices or edges that hit every oriented cycle; ...
Manfred Weis's user avatar
  • 12.4k
1 vote
2 answers
91 views

Choosing $k$ different assignments of binary variables in order to capture the largest volume of the joint probability distribution

Assume you have $n$ independent binary variables $\{x_1,\dots,x_n\}$ and for each variable $x_i$ you know that its value is equal to $1$ with a probability $p_i$. I would like to enumerate the joint ...
JanHula's user avatar
  • 13
2 votes
1 answer
149 views

Optimal prefix-free code design with a complex objective function

We have a long message $m$ to encode. The message is composed of a set of symbols $\{s_i\}$. Let $p_i$ denote the number of appearance of $s_i$ in $m$. We seek to find a prefix-free code for each $s_i$...
lchen's user avatar
  • 459
1 vote
0 answers
39 views

Compute 01-vectors in the orbit of a given vector wrt a finitely-generated abelian subgroup of SL(n,ℤ)

Given a vector $v\in\mathbb Z^n$ and pairwise commutative matrices $M_1,\dotsc,M_k\in \operatorname{SL}(n,\mathbb Z)$, how to compute all 01-vectors in the orbit of $v$ with respect to multiplication ...
Max Alekseyev's user avatar

1
2 3 4 5
9