Submodularity and combinatorial representations for the multicommodity network design problem

Abstract

Presentamos una nueva representación combinatoria para el problema de diseño de redes multiproducto (MUND), tal que su función objetivo satisface la propiedad de submodularidad. Gracias a la propiedad de submodularidad es posible establecer heurísticas, para dos variantes del problema, tales que dichas heurísticas sean algoritmos de aproximación que corren en tiempo polinomial y para los cuales es posible establecer cotas del peor caso de 1/e para grandes instancias.