1,721,361 research outputs found
Fast reoptimization for the minimum spanning tree problem
Full text linkAbstractWe study reoptimization versions of the minimum spanning tree problem. The reoptimization setting can generally be formulated as follows: given an instance of the problem for which we already know some optimal solution, and given some “small” perturbations on this instance, is it possible to compute a new (optimal or at least near-optimal) solution for the modified instance without ex nihilo computation? We focus on two kinds of modifications: node-insertions and node-deletions. When k new nodes are inserted together with their incident edges, we mainly propose a fast strategy with complexity O(kn) which provides a max{2,3−(2/(k−1))}-approximation ratio, in complete metric graphs and another one that is optimal with complexity O(nlogn). On the other hand, when k nodes are deleted, we devise a strategy which in O(n) achieves approximation ratio bounded above by 2⌈|Lmax|/2⌉ in complete metric graphs, where Lmax is the longest deleted path and |Lmax| is the number of its edges. For any of the approximation strategies, we also provide lower bounds on their approximation ratios
Quand l'optimisation fait du beau jeu : une vision algorithmique de la théorie des jeux
No full textou
On the max min vertex cover problem
No full textInternational audienceWe address the max min vertex cover problem, which is the maximization version of the well studied MIN INDEPENDENT DOMINATING SET problem, known to be NP-hard and highly inapproximable in polynomial time. We present tight approximation results for this problem on general graphs, namely a polynomial approximation algorithm which guarantees an approximation ratio, while showing that unless P = NP, the problem is inapproximable within ratio for any strictly positive. We also analyze the problem on various restricted classes of graph, on which we show polynomiality or constant-approximability of the problem. Finally, we show that the problem is fixed-parameter tractable with respect to the size of an optimal solution, to tree-width and to the size of a maximum matching
NP-Hard problems : moderately exponential approximation and parameterized complexity
No full textNous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte.We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality
- …
