On Generalizations of Network Design Problems with Degree Bounds - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




On Generalizations of Network Design Problems with Degree Bounds - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Iterative rounding and relaxation have arguably become the method of choicein dealing with unconstrained and constrained network design problems. In thispaper we extend the scope of the iterative relaxation method in two directions:1 by handling more complex degree constraints in the minimum spanning treeproblem namely, laminar crossing spanning tree, and 2 by incorporating`degree bounds- in other combinatorial optimization problems such as matroidintersection and lattice polyhedra. We give new or improved approximationalgorithms, hardness results, and integrality gaps for these problems.



Autor: Nikhil Bansal, Rohit Khandekar, Jochen Konemann, Viswanath Nagarajan, Britta Peis

Fuente: https://arxiv.org/







Documentos relacionados