Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.
DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.
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 ...
We propose a method for signal reconstruction in semi-parametric dictionaries. The proposed algorithm estimates both the signal decomposition and the intrinsic parameters of the dictionary during the reconstruction process. Theoretical results about the co ...
The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [1] pro ...
A sensor is a device that detects or measures a physical property and records, indicates, or otherwise responds to it. In other words, a sensor allows us to interact with the surrounding environment, by measuring qualitatively or quantitatively a given phe ...
The polynomial Hirsch conjecture states that the vertex-edge diameter of a d-dimensional polyhedron with n facets is bounded by a polynomial in d and n. For the special case where the polyhedron is defined as the set of points satisfying a system Ax ≤ b of ...
It is known that for a convex body K in R-d of volume one, the expected volume of random simplices in K is minimized if K is an ellipsoid, and for d = 2, maximized if K is a triangle. Here we provide corresponding stability estimates. ...
We extend the domain of application of a method developed recently for joint reconstruction of l images, representing the same scene, from few multi-view measurements. While this method was initially designed for planar scenes, we show here that parametric ...
n this extended abstract, we survey some of the recent results on approximating the traveling salesman problem on graphic metrics.We start by briefly explaining the algorithm of Oveis Gharan et al. [1] that has strong similarities to Christofides’ famo ...
We propose a method for signal reconstruction in semi-parametric dictionaries. The proposed algorithm estimates both the signal decomposition and the intrinsic parameters of the dictionary during the reconstruction process. Theoretical results about the co ...
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 th ...
