No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

We study the super-resolution (SR) problem of recovering point sources consisting of a collection of isolated and suitably separated spikes from only the low frequency measurements. If the peak separation is above a factor in $(1, 2)$ of the Rayleigh length (physical resolution limit), L1 minimization is guaranteed to recover such sparse signals. However, below such critical length scale, especially the Rayleigh length, the $L_1$ certificate no longer exists. We show several local properties (local minimum, directional stationarity, and sparsity) of the limit points of minimizing two $L_1$ based nonconvex penalties, the difference of $L_1$ and $L_2$ norms $(L_{1-2})$ and capped $L_1 (CL_1)$, subject to the measurement constraints. In one and two dimensional numerical SR examples,the local optimal solutions from dierence of convex function algorithms outperform the global L1 solutions near or below Rayleigh length scales either in the accuracy of ground truth recovery or in nding a sparse solution satisfying the constraints more accurately.

We introduce a parallel machine scheduling problem in which the processing times of jobs are not given in advance but are determined by a system of linear constraints. The objective is to minimize the makespan, i.e., the maximum job completion time among all feasible choices. This novel problem is motivated by various real-world application scenarios. We discuss the computational complexity and algorithms for various settings of this problem. In particular, we show that if there is only one machine with an arbitrary number of linear constraints, or there is an arbitrary number of machines with no more than two linear constraints, or both the number of machines and the number of linear constraints are fixed constants, then the problem is polynomial-time solvable via solving a series of linear programming problems. If both the number of machines and the number of constraints are inputs of the problem instance, then the problem is NP-Hard. We further propose several approximation algorithms for the latter case.