# Tagged Questions

**3**

votes

**0**answers

58 views

### Containing a “fuzzy” ellipsoid within an ordinary ellipsoid

Consider the ellipsoid described by the inequality $(x - x_c)^T P^{-1} (x - x_c) \leq 1$, where the vector $x_c \in \mathbb{R}^n$ denotes the center of the ellipsoid and the symmetric positive ...

**1**

vote

**2**answers

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

**2**

votes

**4**answers

260 views

### Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...

**1**

vote

**0**answers

19 views

### Minimal rectangular confidence regions

For a given multivariate pdf $f$ (mainly the gaussian one) I'm looking to compute a minimal rectangular confidence region for a given level $\alpha$. For example, I would like to solve problems of the ...

**3**

votes

**1**answer

110 views

### A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not.
The new problem is this. There is a tourist who has a having the following ...

**2**

votes

**1**answer

198 views

### An optimization problem, non complete bipartite graph and hungarian algorithm

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like the rows in reference dataset with the ...

**1**

vote

**3**answers

1k views

### How to get the largest subset of a set of sets of intervals with no overlapping intervals

Given: Set of Set of Intervals. Example {{(1,2), (3,4)}, {(1, 3)}, {(13,14)}}
Wanted Result: Largest Subset, in which no Interval overlaps with another from every Set pairwise.
Example:
Input ...

**10**

votes

**1**answer

244 views

### Network flows with capacities on pairs of edges

Take a standard network flow problem: a directed graph with nonnegative capacities on each edge, a source $s$, a sink $t$. We all know how to find the maximum flow from $s$ to $t$.
Now add edge-pair ...

**2**

votes

**1**answer

202 views

### Nearest trio of neighbours for non-intersecting ellipses

Hi,
I'm working on a problem which is to find the closest trio of neighbours for a set of arbitrarily placed non-intersecting ellipses. As a new user I'm not allowed to include image tags but I've ...

**4**

votes

**2**answers

488 views

### Algorithm for the intersection of a vector subspace with a cone of non-negative vectors

Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...

**10**

votes

**1**answer

522 views

### Complexity of a weirdo two-dimensional sorting problem

Please forgive me if this is easy for some reason.
Suppose given $S$, a set of $n^2$ points in $\mathbb{R}^2$.
I want to choose a bijective map $f$ from $S$ to the set of lattice points in $\lbrace ...

**3**

votes

**1**answer

317 views

### Mathematical Programming with other Algebras than Linear

Linear Programming is strongly entwined with linear algebra, as are many of its generalizations under the heading of mathematical programming / convex optimization.
What analogies are there for ...

**0**

votes

**0**answers

413 views

### Decomposing max-convolution of sum of functions ?

Hello.
$R, F_1, F_2, F_3$ are random (not-convex, not-concave) 2D matrices of size 100x100.
$R$ is a linear combination of $F_1, F_2, F_3$.
Explicitly, $R = w_1 F_1 + w_2 F_2 + w_3 F_3$
where ...

**13**

votes

**2**answers

916 views

### Seeking proof for linear algebra constraint problem.

Given a symmetric real matrix with a zero diagonal $M$, I am trying to find a diagonal matrix $D$, such that the matrix $M + D$ is positive definite, and $(M+D)^{-1}$ has a diagonal consisting of all ...

**5**

votes

**3**answers

654 views

### SDP Feasibility

I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to ...

**1**

vote

**2**answers

1k views

### Greedy approach to 0-1 Knapsack problem in specific instances

The 0-1 knapsack problem is known to be NP-complete, and the greedy approach by Dantzig (based on choosing on the basis of density or value/weight) can be shown to be suboptimal using counterexamples. ...

**4**

votes

**4**answers

307 views

### Linear complementarity problem - Tridiagonal and Convex Case

I need an algorithm for the following LCP:
$\mathbf{Mz}+\mathbf{q} \ge \mathbf{0}$
$\mathbf{z} \ge \mathbf{0}$
$\mathbf{z}^{\mathrm{T}}(\mathbf{Mz}+\mathbf{q}) = 0$
Here, $\mathbf{M}$, is a ...

**0**

votes

**1**answer

429 views

### definition of “exact neighborhood” [optimization]

I find a definition of "exact neighborhood" (the book is online (*1) Definition 1.5 on p.10) confusing.
Do I understand it right that neighborhood that contains the global optimum and no other local ...

**4**

votes

**0**answers

298 views

### Can the Littlewood-Richardson cone be used for combinatorial optimization?

The Littlewood-Richardson cone $LR_{n, k}$ consists of all $k-$tuples $(a_1, a_2, \dots, a_k)$ of real $n-$vectors with monotonically decreasing entries such that there exist $k$ $n \times ...

**3**

votes

**1**answer

585 views

### Is quadratic programming still NP-hard if you have bounds and a feasible point?

The reason I am wondering this is that all of the reductions from 3-SAT => quadratic programming (or similar NP-hard reductions) involve encoding the underlying NP-hard problem into feasibility ...

**2**

votes

**1**answer

629 views

### Condition number for Ellipsoid method matrix

Hello,
When using the ellipsoid method (for solving a linear program for example), the volume of the ellipsoid at each iteration is proven to decrease, and do so by at least a factor of $e^{1/2n}$.
...

**2**

votes

**3**answers

2k views

### Optimization over permutation?

Say that we are given a set of variables, $X=\lbrace X_1,X_2,...,X_n \rbrace$. Their order $\Pi$ is an index array living in a permutation space $Perm(n)$. There is a positive function $f(X,\Pi) > ...

**5**

votes

**2**answers

335 views

### Heaviest Convex Polygon

Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...

**5**

votes

**3**answers

722 views

### Simplex method for SDP?

I know the interior point method works both for Linear Programming (LP) and semidefinite programming (SDP). My question is, can the other popular method for solving LP, namely the simplex method, be ...