Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Fully polynomial-time approximation scheme

Related publications (32)

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson

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. [2012] ...

Assoc Computing Machinery2016

Convergence of quasi-optimal sparse-grid approximation of Hilbert-space-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 sparse-grids stochastic collocation method we presented in a previous work: “On the optimal polynomial approximation of stochastic PDEs by Galerkin and collocation methods” ...

Springer2016

From Massive Parallelization to Quantum Computing: Seven Novel Approaches to Query Optimization

Immanuel Trummer

The goal of query optimization is to map a declarative query (describing data to generate) to a query plan (describing how to generate the data) with optimal execution cost. Query optimization is required to support declarative query interfaces. It is a co ...

EPFL2016

Distributed wireless video caching placement for dynamic adaptive streaming

Pascal Frossard

Caching at edge servers can smooth the temporal traffic variability and reduce the service load of base stations in wireless streaming. However, the assignment of the cached content for possibly multiple versions of different video sequences is still a cha ...

2016

Local discontinuous Galerkin methods for fractional ordinary differential equations

Jan Sickmann Hesthaven

This paper discusses the upwinded local discontinuous Galerkin methods for the one-term/multi-term fractional ordinary differential equations (FODEs). The natural upwind choice of the numerical fluxes for the initial value problem for FODEs ensures stabili ...

2015

On the configuration LP for maximum budgeted allocation

Ola Nils Anders Svensson, Christos Kalaitzis, Aleksander Madry

We study the maximum budgeted allocation problem, i.e., the problem of selling a set of m indivisible goods to n players, each with a separate budget, such that we maximize the collected revenue. Since the natural assignment LP is known to have an integral ...

Springer Heidelberg2015

Anchor View Allocation for Collaborative Free Viewpoint Video Streaming

Pascal Frossard

In free viewpoint video, a viewer can choose at will any camera angle or the so-called "virtual view" to observe a dynamic 3-D scene, enhancing his/her depth perception. The virtual view is synthesized using texture and depth videos of two anchor camera vi ...

2015

Dynamic stability of displacement-based atomistic/continuum coupling methods

Jean-François Molinari, Guillaume Anciaux, Till Junge

We show that concurrent atomistic/continuum displacement-coupling methods are inherently unstable in the context of fully dynamic problems at finite temperature. The fundamental origin of the instability is the displacement coupling of two material descrip ...

Elsevier2015

Sparse Group Covers and Greedy Tree Approximations

Volkan Cevher, Luca Baldassarre

We consider the problem of finding a K-sparse approximation of a signal, such that the support of the approximation is the union of sets from a given collection, a.k.a. group structure. This problem subsumes the one of finding K-sparse tree approximations. ...

2015

Centrality of trees for capacitated -center

Ola Nils Anders Svensson

We consider the capacitated -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) locations (called centers) and assign each ...

Springer Heidelberg2015

Multi-Objective Quality-Driven Service Selection-A Fully Polynomial Time Approximation Scheme

Boi Faltings, Immanuel Trummer

The goal of multi-objective quality-driven service selection (QDSS) is to find service selections for a workflow whose quality-of-service (QoS) values are Pareto-optimal. We consider multiple QoS attributes such as response time, cost, and reliability. A s ...

Institute of Electrical and Electronics Engineers2014

Node-weighted network design and maximum sub-determinants

Carsten Moldenhauer

We consider the Node-weighted Steiner Forest problem on planar graphs. Demaine et al. showed that a generic primal-dual algorithm gives a 6-approximation. We present two different proofs of an approximation factor of~

3

. Then, we draw a connection to Goem ...

EPFL2014

Related publications (32)

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson

Assoc Computing Machinery2016

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

Fabio Nobile, Lorenzo Tamellini

Springer2016

3

. Then, we draw a connection to Goem ...

EPFL2014