Schéma d'approximation en temps entièrement polynomial
Publications associées (72)
Graph Chatbot
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.
We present the first fully dynamic algorithm for maintaining a minimum spanning forest in time o(sqrt(n)) per operation. To be precise, the algorithm uses O(n1/3 log n) amortized time per update operation. The algorithm is fairly simple and deterministic. ...
Failure location in transparent optical networks is difficult because of the large amount of alarms that a failure can trigger and because of corrupted alarms. One problem that network operators often face is how to set the thresholds in monitoring devices ...
This dissertation focuses on disassembly scheduling, which is the problem of determining the quantity and timing of disassembling used or end-of-life products while satisfying the demand of their parts/components over a given planning horizon. The objectiv ...
In this work we present the concept of Uncertainty Feature Optimization (UFO), an optimization framework to handle problems due to noisy data. We show that UFO is an extension of standard methods as robust optimization and stochastic optimization and we sh ...
This paper addresses a multiprocessor generalization of the preemptive open-shop scheduling problem. The set of processors is partitioned into two groups and the operations of the jobs may require either single processors in either group or simultaneously ...
We consider the problem of listing faces of the Minkowski sum of several V-polytopes in R^d. An algorithm for listing all faces of dimension up to j is presented, for any given 0
In this work we present the concept of Uncertainty Feature Optimization (UFO), an optimization framework to handle problems due to noisy data. We show that UFO is an extension of standard methods as robust optimization and stochastic optimization and we sh ...
Simultaneous link failures are common in IP networks \cite{Markopoulou04}. In this paper, we develop a technique for locating multiple failures in Service Provider or Enterprise IP networks using active measurement. We propose a two-phased approach that mi ...
We consider the problem of listing faces of the Minkowski sum of several V-polytopes in R^d. An algorithm for listing all faces of dimension up to j is presented, for any given 0
Unconstrained zero-one quadratic maximization problems can be solved in polynomial time when the symmetric matrix describing the objective function is positive semidefinite of fixed rank with known spectral decomposition. ...