**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Concept# Continuous knapsack problem

Résumé

In theoretical computer science, the continuous knapsack problem (also known as the fractional knapsack problem) is an algorithmic problem in combinatorial optimization in which the goal is to fill a container (the "knapsack") with fractional amounts of different materials chosen to maximize the value of the selected materials. It resembles the classic knapsack problem, in which the items to be placed in the container are indivisible; however, the continuous knapsack problem may be solved in polynomial time whereas the classic knapsack problem is NP-hard. It is a classic example of how a seemingly small change in the formulation of a problem can have a large impact on its computational complexity.
Problem definition
An instance of either the continuous or classic knapsack problems may be specified by the numerical capacity W of the knapsack, together with a collection of materials, each of which has two numbers associated with it: the weight wi o

Source officielle

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

Personnes associées

Aucun résultat

Publications associées (3)

Unités associées

Aucun résultat

Chargement

Chargement

Chargement

Concepts associés

Aucun résultat

Mikhail Kapralov, Amir Zandieh

Reconstructing continuous signals based on a small number of discrete samples is a fundamental problem across science and engineering. We are often interested in signals with "simple" Fourier structure - e.g., those involving frequencies within a bounded range, a small number of frequencies, or a few blocks of frequencies i.e., bandlimited, sparse, and multiband signals, respectively. More broadly, any prior knowledge on a signal's Fourier power spectrum can constrain its complexity. Intuitively, signals with more highly constrained Fourier structure require fewer samples to reconstruct. We formalize this intuition by showing that, roughly, a continuous signal from a given class can be approximately reconstructed using a number of samples proportional to the statistical dimension of the allowed power spectrum of that class. We prove that, in nearly all settings, this natural measure tightly characterizes the sample complexity of signal reconstruction. Surprisingly, we also show that, up to log factors, a universal non-uniform sampling strategy can achieve this optimal complexity for any class of signals. We present an efficient and general algorithm for recovering a signal from the samples taken. For bandlimited and sparse signals, our method matches the state-of-the-art, while providing the the first computationally and sample efficient solution to a broader range of problems, including multiband signal reconstruction and Gaussian process regression tasks in one dimension. Our work is based on a novel connection between randomized linear algebra and the problem of reconstructing signals with constrained Fourier structure. We extend tools based on statistical leverage score sampling and column-based matrix reconstruction to the approximation of continuous linear operators that arise in the signal reconstruction problem. We believe these extensions are of independent interest and serve as a foundation for tackling a broad range of continuous time problems using randomized methods.

Cours associés (1)

MATH-451: Numerical approximation of PDEs

The course is about the derivation, theoretical analysis and implementation of the finite element method for the numerical approximation of partial differential equations in one and two space dimensions.

Marco Discacciati, Alfio Quarteroni

In the present work a general theoretical framework for coupled dimensionally-heterogeneous partial differential equations is developed. This is done by recasting the variational formulation in terms of coupling interface variables. In such a general setting we analyze existence and uniqueness of solutions for both the continuous problem and its finite dimensional approximation. This approach also allows the development of different iterative substructuring solutionmethodologies involving dimensionally-homogeneous subproblems. Numerical experiments are carried out to test our theoretical results.

We consider the numerical approximation of a two-dimensional magnetohydrodynamic problem by standard finite element techniques. The numerical analysis is made for the case of regular solutions of the continuous problem. Error estimates are derived for the selected numerical method.

1996Séances de cours associées (1)