Concept

Polynomial-time approximation scheme

Related publications (278)

Extendability of Continuous Maps Is Undecidable

We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity. The extension problem is the following: Given topological space ...

Springer2014

Sensing the real world

Juri Ranieri

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 ...

EPFL2014

Centrality of Trees for Capacitated k-Center

Ola Nils Anders Svensson, Hyung Chan An, Aditya Bhaskara

We consider the capacitated k-center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) k locations (called centers) and assign e ...

Springer2014

MATHICSE Technical Report : Convergence of quasi-optimal sparse grid approximation of Hilbert-valued functions: application to random elliptic PDEs

Fabio Nobile, Lorenzo Tamellini

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 ...

MATHICSE2014

Fast and accurate CMB computations in non-flat FLRW universes

Julien Lesgourgues

We present a new method for calculating CMB anisotropies in a non-flat Friedmann universe, relying on a very stable algorithm for the calculation of hyperspherical Bessel functions, that can be pushed to arbitrary precision levels. We also introduce a new ...

Iop Publishing Ltd2014

Deciding Conditional Termination

We address the problem of conditional termination, which is that of defining the set of initial configurations from which a given program always terminates. First we define the dual set, of initial configurations from which a non-terminating execution exis ...

Tech Univ Braunschweig2014

Wire Mesh Design

Mark Pauly, Bailin Deng, Akash Garg

We present a computational approach for designing wire meshes, i.e., freeform surfaces composed of woven wires arranged in a regular grid. To facilitate shape exploration, we map material properties of wire meshes to the geometric model of Chebyshev nets. ...

Association for Computing Machinery2014

Approximation schemes for many-objective query optimization

Christoph Koch, Immanuel Trummer

The goal of multi-objective query optimization (MOQO) is to find query plans that realize a good compromise between conicting objectives such as minimizing execution time and minimizing monetary fees in a Cloud scenario. A previously proposed exhaustive MO ...

ACM Press2014

LP-Based Algorithms for Capacitated Facility Location

Ola Nils Anders Svensson, Hyung Chan An

Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodo ...

IEEE2014

Approximation algorithms for regret minimization in vehicle routing problems

Adrian Aloysius Bock

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 ...

EPFL2014

Graph Chatbot

Chat with Graph Search

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.