# Tagged Questions

**3**

votes

**1**answer

76 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

183 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

232 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

195 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

460 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

503 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

315 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

385 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

907 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

629 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

**3**answers

292 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

374 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

293 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

558 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

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

**4**

votes

**3**answers

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