Concept
Schéma d'approximation en temps polynomial
Publications associées (278)
A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing
In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...
Society for Industrial and Applied Mathematics2016Convergence 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” ...
2016On Verifying Causal Consistency
Causal consistency is one of the most adopted consistency criteria for distributed implementations of data structures. It ensures that operations are executed at all sites according to their causal precedence. We address the issue of verifying automaticall ...
2016Approximation algorithms for geometric dispersion
Alfonso Bolívar Cevallos Manzano
The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...
EPFL2016Submodular Stochastic Probing on Matroids
Justin Dean Ward, Marek Adamczyk
In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Mo ...
INFORMS2016APPROXIMATING k-MEDIAN VIA PSEUDO-APPROXIMATION
We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + root 3 + epsilon, improving upon the decade-old ratio of 3 + epsilon. Our improved approximation ratio is achieved by exploiting the power of pseudo-app ...
Siam Publications2016From Massive Parallelization to Quantum Computing: Seven Novel Approaches to Query Optimization
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 ...
EPFL2016Fast recovery and approximation of hidden Cauchy structure
We derive an algorithm of optimal complexity which determines whether a given matrix is a Cauchy matrix, and which exactly recovers the Cauchy points defining a Cauchy matrix from the matrix entries. Moreover, we study how to approximate a given matrix by ...
Elsevier Science Inc2016Induced Matchings In Graphs Of Degree At Most 4
For a graph G, let nu(s)(G) be the strong matching number of G. We prove the sharp bound nu(s)(G) >= n(G)/9 for every graph G of maximum degree at most 4 and without isolated vertices that does not contain a certain blown-up 5-cycle as a component. This re ...
Siam Publications2016Randomized Single-View Algorithms for Low-Rank Matrix Approximation
This paper develops a suite of algorithms for constructing low-rank approximations of an input matrix from a random linear image of the matrix, called a sketch. These methods can preserve structural properties of the input matrix, such as positive-semideni ...
Under review2016