The combinatorial-optimizatio tag has no usage guidance.

**0**

votes

**0**answers

18 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

**1**answer

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

**3**

votes

**0**answers

59 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

**0**answers

95 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

**0**answers

60 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

**0**answers

57 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

**2**answers

97 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

**2**answers

50 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

**0**answers

218 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

**0**answers

263 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

**0**answers

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

**8**

votes

**3**answers

329 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

**1**answer

414 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

**0**answers

152 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

**1**answer

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

**1**answer

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

**0**answers

151 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

**0**answers

32 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

**1**answer

121 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

**1**answer

125 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

**0**answers

73 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

**0**answers

156 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

**1**answer

357 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

**2**answers

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

**1**answer

71 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

**0**answers

202 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

**0**answers

132 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

**2**answers

152 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

**1**answer

128 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

**0**answers

81 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

**3**answers

231 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

**2**answers

302 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

**1**answer

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

**0**answers

63 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

**0**answers

97 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

**1**answer

412 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

**0**answers

69 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

**0**answers

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

**2**answers

359 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

**2**answers

158 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

**1**answer

474 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

**1**answer

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

**2**answers

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

**2**

votes

**1**answer

191 views

### Upper bounds on the worst-case traveling salesman tours in the unit square

The paper [1] proves that, if we place $N$ points in the unit square, then the length $\ell$ of the euclidean TSP tour of those points must satisfy $$\ell \leq \sqrt{2N} + 7/4~~.$$ I'm wondering, can ...

**7**

votes

**2**answers

371 views

### Quickly finding optimal subset of pairs of numerator and denominator terms for special objective functions

Given a multi-set of pairs $((a_i,b_i))_{i \in Y}$ of positive numerator and denominator terms (i.e. each pair has one numerator term and one denominator term), my general problem is to find the ...

**-1**

votes

**1**answer

58 views

### Effect of a Specific Restriction on the Integrality of Min-cost Flow Solutions

I want to model the following situation: there is one production site (modelled by the source), a collection of depots (modelled by nodes without demand) and, of course many more customers (modelled ...

**2**

votes

**0**answers

67 views

### Optimization over a variable domain defined as a convex hull of given points [closed]

I have an optimization problem:
$\max_{\bf{x}} Z(\bf{x})$,
s.t. $\bf{x} \in conv(\bf{S})$
where $\bf{x}$ is an $n$-dimensional vector, $Z(\bf{x})$ is a non-linear function. The domain of $\bf{x}$ ...

**1**

vote

**1**answer

123 views

### Deducing Linear Inequalities

Let $X_1,X_2,\ldots,X_n $ be indeterminates. Denote by $S$ the set of all linear inequalities of the form
$X_{i_1}+X_{i_2}+\ldots+X_{i_k} \geq k,$
with $k \in \{ 1,2,\ldots,n \}$ and $1 \leq i_1< ...

**3**

votes

**1**answer

234 views

### Optimization problem - maximizing number of satisfied linear inequalities subject to a quadratic constraint

I am wondering what is known about optimization problems of the following type.
Our control x is a unit vector in $\mathbb{R}^n$. We are given a finite number of linear inequalities
$$Az≥b,$$
and we ...

**1**

vote

**1**answer

96 views

### Finding a sub-matrix from a fat matrix with the best condition number.

Given a m-by-n matrix with $n>>m$ and with a known rank of $k\leq m$, what would be a computationally effective way of finding out $k$ columns, such that the matrix formed using these $k$ ...