# Tagged Questions

The tag has no wiki summary.

1answer
45 views

### submatrix of a given size with maximum frobenius norm

Let $I\subset \{1,2,\ldots,n\}$, and let $|I|$ denote its cardinality. Now given a Hermitian matrix $\mathbf{A}\in\mathbf{C}^{n\times n}$. I am interested in finding the subset $I$ that maximizes the ...
0answers
24 views

### departure time/overlap algorithm [on hold]

i'm looking for "departure time/overlap algorithm" or any other idea. Suppose you have n trains and each one has a performance profile(how much electricity they need at the current time while driving ...
4answers
334 views

### Efficient algorithm for finding the minima of a piecewise linear function

Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by $f(x) = \max_i ( a_i + b_i x )$ We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two ...
1answer
247 views

### eigen-decomposition solution? is it unique?

Assume an N*N covariance matrix (Q) which is a positive definite matrix. The decoder X is assumed to be N*s, where s<=N. X is calculated to be s eigenvectors corresponding to s minimum eigenvalues. ...
1answer
23 views

### optimization of inverse matrix with constraint on matrix elements

everyone! I have this optimization problem with constraint. D and T are symmetric matrice, where T is known and D is the unknown parameter. x and v are two known p-dimensional vectors. The objective ...
2answers
746 views

### An Interesting Optimization Problem

You are given n non-negative integers $a_1, a_2 ,, a_n$. In a single operation, you take any two integers out of these integers and replace them with a new integer having value equal to difference ...
0answers
31 views

### Maximize minimum optimization using linear integer programming [closed]

I am trying to solve a maximize minimum optimization. I have four different items that each of them has 10 values of Rates and for each value it has a corresponding weight. Then I have a free table ...
2answers
108 views

0answers
93 views

### Variant of orthogonal Procrustes problem

The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...
2answers
150 views

0answers
96 views

### Matrix Minimax problem

I have the equation $\Sigma_k(M_k{p_k})V=EV$, where the $M_k$ are n*n real Hermitian matrices, $V$ is a n*n eigenvector matrix, $E$ a dim-n energy eigenvector and the $p_k$ scalar parameters. The ...
1answer
195 views

### Approximate Set Cover Problem by Rounding

Here is the simple algorithm for approximating set cover problem using rounding: Algorithm 14.1 (Set cover via LP-rounding) Find an optimal solution to the LP-relaxation. Pick all sets ...
1answer
420 views

### Finding linearly independent columns of a large sparse rectangular matrix

I have a problem that necessitates solving a large non-negative least-squares problem. My matrix A is large, sparse, highly rectangular (num rows >> num cols) and nearly binary. However, A is not ...
2answers
207 views

### Bounding the minimal maximum norm of a solution of a linear system.

I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...
1answer
2k views

### Linear program to maximize the minimum absolute value of linear functions ?

I'd like to compute $\max_{x,t} t$ such that $\forall i$, $t < a_i + |x - b_i|$. where $a_i,\ldots, a_n$ and $b_1,\ldots,b_n$ are fixed and $x \in [0,1]$. Can this be solved with a linear ...