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.
We consider the Minimum Linear Arrangement problem and the (Uniform) Sparsest Cut problem. So far, these two notorious NP-hard graph problems have resisted all attempts to prove inapproximability results. We show that they have no polynomial time approxima ...
Society for Industrial and Applied Mathematics2011
In genome rearrangement, given a set of genomes G and a distance measure d, the median problem asks for another genome q that minimizes the total distance Sigma(g is an element of G d(q, g)). This is a key problem in genome rearrangement based phylogenetic ...
In this thesis, we present new approximation algorithms as well as hardness of approximation results for NP-hard vehicle routing problems related to public transportation. We consider two different problem classes that also occur frequently in areas such a ...
In this work we focus on the numerical approximation of the solution u of a linear elliptic PDE with stochastic coefficients. The problem is rewritten as a parametric PDE and the functional dependence of the solution on the parameters is approximated by mu ...
The longevity of wireless sensor networks (WSNs) is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged ...
In this work we provide a convergence analysis for the quasi-optimal version of the Stochastic Sparse Grid Collocation method we had presented in our previous work \On the optimal polynomial approximation of Stochastic PDEs by Galerkin and Collocation meth ...
We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the ...
We consider the problem of testing whether the maximum integrality gap of a family of integer programs in standard form is bounded by a given constant. This can be viewed as a generalization of the integer rounding property, which can be tested in polynomi ...
The efficient synthesis of circuits is a well-studied problem. Due to the NP-hardness of the problem, no optimal algorithm has been presented so far. However, the heuristics presented by several researchers in the past, which are also adopted by commercial ...
This paper considers a production planning problem in disassembly systems, which is the problem of determining the quantity and timing of disassembling end-of-use/life products in order to satisfy the demand of their parts or components over a planning hor ...
