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.
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 ...
In a variety of fields, in particular those involving imaging and optics, we often measure signals whose phase is missing or has been irremediably distorted. Phase retrieval attempts the recovery of the phase information of a signal from the magnitude of i ...
The reconstruction of a diffusion field, such as temperature, from samples collected by a sensor network is a classical inverse problem and it is known to be ill-conditioned. Previous work considered source models, such as sparse sources, to regularize the ...
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 ...
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 ...
We present a novel method for robust reconstruction of the image of a moving object from incomplete linear measurements. We assume that only few measurements of this object can be acquired at different instants and model the correlation between measurement ...
Recovery of the sparsity pattern (or support) of an unknown sparse vector from a small number of noisy linear mea- surements is an important problem in compressed sensing. In this paper, the high-dimensional setting is considered. It is shown that if the m ...
Institute of Electrical and Electronics Engineers2013
In this paper we construct a deterministic polyno- mial time algorithm for the problem where a set of users is interested in gaining access to a common file, but where each has only partial knowledge of the file. We further assume the existence of another ...
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 ...
Our contribution in this paper is two fold. First, we propose a novel discretization of the forward model for differential phase-contrast imaging that uses B-spline basis functions. The approach yields a fast and accurate algorithm for implementing the for ...
