**1**

vote

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**3**answers

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

**1**answer

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

**0**answers

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

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

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

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

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**3**answers

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

**2**answers

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

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

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

**0**answers

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

**1**answer

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

**0**answers

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

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

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

**2**answers

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

**1**answer

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

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

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