Concept
Randomized rounding
Publications associées (49)
Tensor-Based Numerical Method For Stochastic Homogenization
This paper addresses the complexity reduction of stochastic homogenization of a class of random materials for a stationary diffusion equation. A cost-efficient approximation of the correctors is obtained using a method designed to exploit quasi-periodicity ...
SIAM PUBLICATIONS2022A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine
Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release time ...
ASSOC COMPUTING MACHINERY2021No Small Linear Program Approximates Vertex Cover Within a Factor 2-epsilon
Ola Nils Anders Svensson, Abbas Bazzi
The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev [Khot S, Regev O (2008) Vertex cover might be hard to approximate to within 2 - epsilon. J. Comput. System Sci. 74(3): 335-349 ...
INFORMS2019