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.

learn more… | top users | synonyms

1
vote
0answers
84 views

Optimization on Binomial coefficients

Suppose we are given integers $1\leq r\leq N$, we want to study the following $$ \max_{m_0+m_1=N,m_0,m_1\geq 1}\max_j \tbinom {m_0}{j}\tbinom {m_1}{r-j}. $$ $N$ is very large, for instance $N\geq ...
0
votes
0answers
12 views

Approximation preserving reductions

I've seen in the following document https://hal.archives-ouvertes.fr/hal-00958028/document A definition of the $\leq_{S}$ reduction defined specifically for minimisation problems at the bottom of ...
0
votes
0answers
20 views

Correct definition of submodularity

I am currently looking at a paper whose submodularity definition is different from whatever I thought I knew. In this paper, the authors consider a function $\Pi_2(q;a^r)$, where $q$ is composed of ...
0
votes
0answers
41 views

Inapproximability of Combinatorial Optimization Problems

I've been reading the "Inapproximability of Combinatorial Optimization Problems" by Luca Trevisan (see: link). On pages 3-4 it mentions that a polynomial time algorithm for 3SAT would exist if there ...
1
vote
1answer
72 views

$0/1$ programming multiple quadratic constraints

If we have an $n$-variable rank $n$-linear system it is clear we can find whether there exists a $0/1$ solution in polynomial time. If we have an $n$-variable degree $2$ system how many constraints ...
3
votes
1answer
111 views

Can we say that this problem is NP-hard?

I have an optimization problem of the form: \begin{align} &\text{maximize}\quad f(\mathbf{x}) = \dfrac{\sum\limits_{n=1}^{N}x_na_n}{1+\sum\limits_{n=1}^{N}x_nb_n}\\ & \text{subject to}\quad ...
3
votes
2answers
149 views

Bellman-Ford for Matching Problems?

I am looking for a simple way of calculating minimum-weight perfect matchings in complete graphs with an even number of vertices. I know that there are implementations that are based on Edmond's ...
0
votes
0answers
22 views

A new Class of Matching-based Divide and Conquer Heuristics for TSP?

Under the assumption that $G=:G_0$ is a complete graph with $2^n$ vertices and arbitrary edge weights, the essential idea to construct the shortest Hamilton cycle is to proceed as follows: i := 0 ...
4
votes
1answer
110 views

Closest point to a dual lattice point (in particular for root lattices!)

Given a lattice $\Lambda\subset \mathbb{R}^n$ and a point $p\in\mathbb{R}^n$ outside the lattice, then I known it is a hard question to determine the set $S\subset \Lambda$ of all lattice points with ...
4
votes
0answers
70 views

max-min optimization problem

I'm curious if there is any nice way to approach solving the following kind of optimization problem. Given a $n \times m$ matrix $A = (a_{ij})$, I want to solve \begin{align*} & \max_{c}\min_{1 ...
1
vote
0answers
99 views

Lower bound on the value $\textbf{1}^Tx$ such as $Ax\geq b$

The problem may be formulated as follows: We are given a set of $m$ positive numbers $\{b_1,...,b_m\}$ and a set of $n$ positive numbers $\{v_1,...,v_n\}$. We have $v_j\leq K$, $j=1,...,n$, for a ...
2
votes
0answers
64 views

Shortest paths stepping on rational points of height $h$

Q. Do shortest paths walking between rational points of height $h$ ever properly cross themselves? Explaining this question takes a bit of definitional exposition. First, I copy definitions ...
1
vote
0answers
59 views

Characterization of certain families of functions

For $R$ equal $\mathbb{R}$ or $\mathbb{Z}$, let $D^+_R:=\{(x,y)\in R^2\colon x<y\}$. For each natural $n$, let $F_{n,R}$ denote the set of all Borel-measurable functions $f\colon ...
1
vote
2answers
99 views

A combinatorial optimization problem [closed]

A seller wants to sell $N$ goods to $M$ buyers. To that end, the seller collects the prices offered by each buyer $m$ on each good $i$ ($m=1,\cdots,M$, $i=1,\cdots,N$) $p_{mi}$. Given $\{p_{mi}\}$, I ...
1
vote
2answers
56 views

Maximum subgraph edge distance greater than given number

I have a weighted graph G with approximately 75000 nodes. I would like to find subgraph G' induced on a subset of nodes, such that all edge weights in G' are greater than a given constant C and the ...
1
vote
0answers
221 views

Reduction to some physical interpretation of this formula

Problem Given N 3-dimensional points which are {$p_1,p_2,..,p_n$} where $p_i = (x_i,y_i,z_i) $ . I have to find the value of the formula $$ \sum \limits_{i=0}^n \sum \limits_{j=i+1}^n \frac{ \mid ...
3
votes
0answers
270 views

Maximizing sum of matrices

Over the last few months, I've been trying to find the solution to a research-related problem I'm having. However, my research is not in mathematics, and my progress toward reaching a solution has ...
2
votes
0answers
31 views

s-arc transitivity and the Moore bound

Given a vertex $x$ of a graph, call the subgraph induced by all vertices of distance $\le n$ from $x$ the $n$-neighbourhood of $x$, denoted $N_n(x)$. Let $G$ be a regular graph of diameter $n+1$. For ...
9
votes
3answers
355 views

“Most Similar Vector Problem” on an Integer Lattice?

I am currently working on problem that I think could be expressed as an integer lattice problem. Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$ I would like ...
9
votes
1answer
433 views

Is this (funny) combinatorial optimization problem NP-hard ? (cutting numbers and placing them in urns)

The parameters of the problem are $m$ numbers which are integers (these numbers are denoted $b_i$), $n$ urns and in each urn, we can place $C$ numbers. We assume $nC \geq m$ so that the problem is ...
1
vote
0answers
153 views

Complexity of reordering a matrix which consists independent sub matrices

Introduction: Given a matrix A of a $k$ regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $A_x$ is the symmetric matrix of the graph $(G-x)$, ...
1
vote
1answer
44 views

rank minimization over vector subsets

Let $S$ be a set of $n$ vectors from $\mathbb{Q}^d$. For every $k=1,2,\dots,n$, define $$r_k = \min_{T\subset S, |T|=k} \mathrm{rank}(T),$$ where $\mathrm{rank}(T)$ is the rank of a matrix formed by ...
1
vote
1answer
65 views

Given $M$, minimize $|Mx|_0$

Given a matrix $M \in \mathbb{R}^{n \times m}$, I would like to find $\min_{x \in \mathbb{R}^m} \|Mx\|_0$ such that $x \neq 0^m$, where the $\ell_0$ "norm" is measured by simply counting the number ...
4
votes
0answers
152 views

What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
0
votes
0answers
34 views

Complexity of optimizing a bi-objective function with integer constraints

I have two different objective functions, each of which can be solved optimally in polynomial time. Does this mean, I can optimize a linear combination of these objective functions in polynomial time ...
2
votes
1answer
125 views

Optimization over symmetric polynomials

Consider the following constraint satisfaction problem: Let $\alpha_1 , \ldots, \alpha_k \in \mathbb{R}$ be given as well as an error parameter $\epsilon$. Find $p_1, \ldots, p_n$ such that (i) $0 ...
2
votes
1answer
133 views

Network flows with shared capacities

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as: $$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$ where $f(1, 2)$ denotes the flow through arc $(1, ...
2
votes
0answers
74 views

Limit shape for oil-shaped stack in the max overhang problem

In the Maximum Overhang paper, the authors mention an oil-shaped configuration (ref. page 19) What is known about the curve that limits this shape?
2
votes
0answers
170 views

Solution of a linearly constrained quadratic programming problem [closed]

What is the solution of the following optimization problem: \begin{align} &\min{\mathbf{p}^\mathrm{T} \mathbf{B} \mathbf{p}}\\ &\text{subject to}: \mathbf{0}\leq{\mathbf{p}}\leq \mathbf{1}. ...
13
votes
1answer
361 views

How to roll a $p$

Let $p$ be a positive integer (which is not a power of $2$), and suppose we want to generate a number uniformly randomly in the set $\{ 0, 1, \dots , p-1 \}$ (to emulate a dice roll). We are given ...
4
votes
2answers
214 views

Complexity of finding the maximum sum divided by product

What is the complexity of the following optimization problem? Problem. Given $n$ pairs of positive reals $(a_i,b_i)_{i=1}^n$, choose a subset $S \subseteq [n]$ to maximize $$ \frac{\sum_{i\in S} ...
1
vote
1answer
74 views

Maximizing a certain concave function over a non-convex set

I have been working on a problem which involves maximizing a concave function over a non convex constraint set. The problem is the following $$max. \frac{1}{2}x^TBx\\ s.t.\ x_i(1-x_i)=0,\ \ ...
2
votes
0answers
204 views

Minimizing $\{0,1\}$-sequence permutations

Explanation: For a given bit sequence $f$, reposition the bits as to minimize $G$ which can be thought of as a measure of how poorly proportional $f$ is to each of its subsequences. Let $p \in ...
1
vote
0answers
135 views

current status of combinatorial optimization solvers [closed]

What is the current status of the solvers in combinatorial optimization? For example, what is the "usual feasible size" for a traveller sale's man problem, say, how many nodes and edges are "usually ...
1
vote
2answers
155 views

Combinatorial optimization problem involving infinite spin system

In material science research, I am developing an algorithm to solve an infinite combinatorial optimization problem which I believe is the most natural problem when the system size goes to infinity. ...
3
votes
1answer
132 views

A difficult combinatorial optimization problem

Let $\mathcal{J}$ be a closed, bounded, compact, convex set in $\mathbb{R}^L$. (Notations: vector $\mathbf{x}$ is denoted in bold letters and its $i^{th}$ co-ordinate is denoted as $x_i$. ...
4
votes
0answers
83 views

Nice minimal embeddings of large finite groups into compact Riemannian manifolds

The initial motivation for this question is a very practical problem: I need to find the absolute minimum of a function on a very large symmetric group $\Sigma_N$ (with $N$ 10000 or more). So if ...
4
votes
3answers
234 views

Can anyone suggest a text on polyhedral theory?

Can anyone suggest a text on polyhedral theory? Particularly on increasing the number of faces under projections. 0,1 polytopes
0
votes
2answers
305 views

Mixed integer programming formulation for Ising model

I want to implement a minimisation on a 2D spin Ising model with 30x30 grid. The spin variables is 0,1 and the objective is to minimize the sum of products of spins. For simplicity, I only include NN ...
1
vote
1answer
102 views

A certain instance of the Set Covering problem

Is there any useful structure associated with the following instance of the Set Covering problem? Let $G$ be a weighted graph and let $\mathcal{P}$ denote the set of all shortest paths between all ...
0
votes
0answers
67 views

Sufficient optimality condition for a non-smooth quasiconvex problem

The result of relaxing to an integer program is the following optimization problem: $$\min_{\textbf{x}} \sum_{i=1}^n \alpha_i h(x_i)\quad subject \; to \quad A\textbf{x} = \textbf{0}$$ where ...
0
votes
0answers
101 views

Ref request: If an affine subspace $V$ of $\mathbb R^n$ meets an $n$-dimensional polytope $P$, then it meets $P$ in a face of dimension $\le n-\dim V$

Let $P$ and $V$ be, respectively, a bounded full-dimensional polytope and an $m$-dimensional affine subspace of $\mathbb R^n$, and assume $P \cap V$ is non-empty. Q1. Could you provide me with a ...
3
votes
1answer
416 views

Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality

The original problem of Domino Tiling and Wang Tile has great theoretical interest on computability theory... However, the great emerging problem on application of Wang Tile in material science and ...
1
vote
0answers
73 views

integrality of a linear program — binary equality constaints

Consider the following linear program: $\left\{ \begin{array}{l} \underset{x}{max} \;\;c^Tx\\ [I, \;B]x = \mathbf{1}\\ x\geq 0 \end{array} \right.$ where $c$ is a vector ...
1
vote
0answers
64 views

Are there any known bounds on the value of solutions of linear integer programming?

Given a linear objective function and a system of linear constraints; are there any known bounds on the values of (positive) integral solutions in terms of the coefficient matrix of the constraints? ...
0
votes
2answers
401 views

Supermodular Minimization

I need to minimize a supermodular function and I am well aware of the fact that minimizing supermodular functions is equivalent to maximize submodular functions and that there are many good ...
3
votes
2answers
159 views

Minimize the length of intersection of the set of intervals

Consider the following problem: given a finite set $S$ of intervals on the line and a number $k$. We need to colour this set in $k$ colours so that the measure of the set of points, which are ...
6
votes
1answer
598 views

Best ranking in tournament: polynomial time algorithm?

This question was posed by my colleague Torbjörn Lundh in his paper Which Ball is the Roundest? A Suggested Tournament Stability Index, Journal of Quantitative Analysis in Sports 2(3), 2006. We have ...
1
vote
1answer
205 views

Is this Graph parameter known?

Let $\lambda(G)$ denote the edge-connectivity of $G$. Consider the following parameter: $\rho(G) = \max_{X \subset V(G)} \min(\lambda(G[X]), \lambda(G[V(G) - X]))$ Has this parameter been studied? ...
2
votes
2answers
223 views

Survey on Compared Running Time: Ellipsoid Method vs. Simplex Method

If you look through papers on the Ellipsoid Method, there is a large agreement, that the Ellipsoid Method, although theoretically polynomial, is in practice way slower than the Simplex Method. ...