Séance de cours

FPTAS pour Knapsack

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Dans cours

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer science and cryptography during the past 30 years. ...

Description

Cette séance de cours couvre le Fullly Polynomial-Time Approximation Scheme (FPTAS) pour le problème Knapsack, présentant des algorithmes et des preuves pour obtenir une approximation de (1-ε) fois la solution optimale. L'instructeur explique l'approche dynamique de la programmation, la complexité du temps pseudo-polynôme et le processus de résolution efficace du problème Knapsack. Différents algorithmes d'approximation sont discutés, ainsi que leurs temps de fonctionnement et les preuves théoriques. La séance de cours se termine par l'analyse de la maximisation du profit et de la relation entre la solution obtenue et la solution optimale.

Source officielle

Concepts associés (30)

Problème du sac à dos

En algorithmique, le problème du sac à dos, parfois noté (KP) (de l'anglais Knapsack Problem) est un problème d'optimisation combinatoire. Ce problème classique en informatique et en mathématiques modélise une situation analogue au remplissage d'un sac à dos. Il consiste à trouver la combinaison d'éléments la plus précieuse à inclure dans un sac à dos, étant donné un ensemble d'éléments décrits par leurs poids et valeurs.

Cutting stock problem

In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem in mathematics that arises from applications in industry. In terms of computational complexity, the problem is an NP-hard problem reducible to the knapsack problem. The problem can be formulated as an integer linear programming problem.

Algorithme d'approximation

En informatique théorique, un algorithme d'approximation est une méthode permettant de calculer une solution approchée à un problème algorithmique d'optimisation. Plus précisément, c'est une heuristique garantissant à la qualité de la solution qui fournit un rapport inférieur (si l'on minimise) à une constante, par rapport à la qualité optimale d'une solution, pour toutes les instances possibles du problème.

Approximation-preserving reduction

In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree. Approximation-preserving reductions are a subset of more general reductions in complexity theory; the difference is that approximation-preserving reductions usually make statements on approximation problems or optimization problems, as opposed to decision problems.

Programmation dynamique

En informatique, la programmation dynamique est une méthode algorithmique pour résoudre des problèmes d'optimisation. Le concept a été introduit au début des années 1950 par Richard Bellman. À l'époque, le terme « programmation » signifie planification et ordonnancement. La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires.

Afficher plus

Séances de cours associées (35)

Algorithmes d'approximation

Couvre les algorithmes d'approximation pour les problèmes d'optimisation, la relaxation LP et les techniques d'arrondi aléatoire.

Correspondance et solidité de l'essai Qubit

Explore la justesse et la solidité du test Qubit, en mettant l'accent sur les algorithmes probabilistes, les trappes et l'inversion fonctionnelle.

Optimisation intégrale: Théorie et applications

Couvre les fondamentaux de l'optimisation d'entier, y compris la programmation d'entier, la programmation dynamique et les algorithmes d'approximation.

Groupes fondamentaux

Explore les groupes fondamentaux, les classes d'homotopie et les revêtements dans les variétés connectées.

Optimisation et simulation

Explore l'heuristique gourmande dans l'optimisation, les contraintes d'intégrité, et la comparaison des méthodes d'optimisation.

Afficher plus

Concepts associés (30)

Problème du sac à dos

Cutting stock problem

Algorithme d'approximation

Approximation-preserving reduction

Programmation dynamique

Afficher plus