Publication
New Results on Optimizing Rooted Triplets Consistency
Publications associées (55)
Fixed-Rank Rayleigh Quotient Maximization by an MPSK Sequence
Certain optimization problems in communication systems, such as limited-feedback constant-envelope beamforming or noncoherent M-ary phase-shift keying (MPSK) sequence detection, result in the maximization of a fixed-rank positive semidefinite quadratic for ...
Institute of Electrical and Electronics Engineers2014Node-weighted network design and maximum sub-determinants
We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~. Then, we draw a connection to Goem ...
EPFL2014Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing
We prove that for an arbitrarily small constant < 0, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor 2log1-en, under the assumption that NP ⊈ SIZE(2logO(1/e)n). © 2014 Soc ...
Society for Industrial and Applied Mathematics2014Single machine scheduling with scenarios
In the field of robust optimization, the goal is to provide solutions to combinatorial problems that hedge against variations of the numerical parameters. This constitutes an effort to design algorithms that are applicable in the presence of uncertainty in ...
2013Santa Claus Schedules Jobs On Unrelated Machines
One of the classic results in scheduling theory is the 2-approximation algorithm by Lenstra, Shmoys, and Tardos for the problem of scheduling jobs to minimize makespan on unrelated machines; i.e., job j requires time p(ij) if processed on machine i. More t ...
Siam Publications2012