**0**

votes

**0**answers

19 views

### Relaxation of the following Binary Optimization

I have the following feasibility Boolean optimization problem:
$$\frac{d}{d \beta} {\rm{trace}}\big[M \ G(x_i,y_i,\beta)\big] = {\rm{trace}}\big[ G_1 (x_i,y_i,\beta) \ G_2 (x_i,y_i,\beta) \big] \leq ...

**0**

votes

**0**answers

14 views

### Under which conditions discretization of convex\concave function is submodular?

Say, I have $f(x)$ with $x \in [0,1]$, then by discretization I mean $f(x_h)$ with $x_h \in \{0, h, 2h, \dots, 1\}$.
I know about Lovasz extension, but it works in other way: given discrete function ...

**0**

votes

**0**answers

20 views

### Is budget-additive function a modular set function?

We know that budget-additive function
$$
f(S) = \min\{B,\sum_{i \in S}w_i\}
$$
where $w_i$ is positive constant and $B \ge 0$ is called additive budget.
Is it also a modular set function?

**0**

votes

**0**answers

35 views

### max-flow at max-cost

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...

**0**

votes

**1**answer

79 views

### Does general case of following function exist?

Suppose we have the following: $m_1 m_2 m_3$
Where $m_1$, $m_2$, $m_3$ are constants $> 0$
I'm looking for a function $f$ such that:
$m_1 m_2 m_3 = 1.0 + f(m_1,m_2,m_3) + f(m_2,m_1,m_3) + f(m_3,...

**3**

votes

**1**answer

89 views

### A modified bipartite assignment problem

Consider the following optimization problem. I have $n$ advisors and $dn$ students. I want to assign each student an advisor so that each advisor has exactly $d$ students. Each advisor/student pair ...

**4**

votes

**0**answers

79 views

### Designing Character Other Than Temperature for Simulated Annealing on Combinatorial Optimization

Many research on designing temperature for simulated annealing is carried out. We wonder if there is any research on designing general feature of the Hamiltonian used in Simulated Annealing.
For ...

**1**

vote

**1**answer

150 views

### Averaged geometric series with floor function

Given a value $p\in[0,1]$ (a probability of occurrence), I would like to bound the following expression:
$$ s\frac{1-(1-p)^{k+1}}{p(k+1)} + (1-s)\frac{1-(1-p)^{k}}{pk},\ \ \ \text{where $k=\lfloor 1/...

**0**

votes

**0**answers

46 views

### Approximation to colouring for bounded degree graphs

I have already asked one question on colouring, this question is more specific.
Given a bounded degree graph $G$ with $\Delta(G)=2d$, is there a well know algorithm to achieve an approximation ratio ...

**1**

vote

**1**answer

76 views

### Graph colouring for bounded degree graphs

I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...

**0**

votes

**0**answers

31 views

### Distribution of zeros and ones over matrix

I have the following problem:
Given a matrix with n rows and m columns. Some elements of the matrix are unavailable.
For each column, you have a set containing a number of zeros and ones which must ...

**2**

votes

**0**answers

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

**1**

vote

**1**answer

102 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

126 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

198 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

24 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

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

**5**

votes

**0**answers

86 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

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

60 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 D^+_R\to\mathbb{R}$...

**1**

vote

**2**answers

102 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

67 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

235 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

288 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

32 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

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

**10**

votes

**1**answer

467 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

160 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

66 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

154 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

35 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

133 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

143 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)$....

**2**

votes

**0**answers

76 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

224 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

373 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

222 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} a_i}{...

**1**

vote

**1**answer

89 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,\ \ i=1,\cdots,...

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

140 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

158 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

136 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$. $\mid\...

**4**

votes

**0**answers

86 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

237 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

314 views

### Mixed integer programming formulation for Ising model [closed]

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

106 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

75 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 $\textbf{...

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