Optimization over integers with robustness in cost and few constraints

Kai Simon Goetzmann*, Sebastian Stiller, Claudio Telha

*Autor correspondiente de este trabajo

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

13 Citas (Scopus)

Resumen

We consider robust counterparts of integer programs and combinatorial optimization problems (summarized as integer problems in the following), i.e., seek solutions that stay feasible if at most Γ-many parameters change within a given range. While there is an elaborate machinery for continuous robust optimization problems, results on robust integer problems are still rare and hardly general. We show several optimization and approximation results for the robust (with respect to cost, or few constraints) counterpart of an integer problem under the condition that one can optimize or approximate the original integer problem with respect to a piecewise linear objective (respectively piecewise linear constraints). For example, if there is a ρ-approximation for a minimization problem with non-negative costs and non-negative and bounded variables for piecewise linear objectives, then the cost robust counterpart can be ρ(1+ε)-approximated. We demonstrate the applicability of our approach on two classes of integer programs, namely, totally unimodular integer programs and integer programs with two variables per inequality. Further, for combinatorial optimization problems our method yields polynomial time approximations and pseudopolynomial, exact algorithms for Robust Unbounded Knapsack Problems.

Idioma originalInglés
Título de la publicación alojadaApproximation and Online Algorithms - 9th International Workshop, WAOA 2011, Revised Selected Papers
Páginas89-101
Número de páginas13
DOI
EstadoPublicada - 2012
Publicado de forma externa
Evento9th International Workshop on Approximation and Online Algorithms, WAOA 2011 - Saarbrucken, Alemania
Duración: 8 sept. 20119 sept. 2011

Serie de la publicación

NombreLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen7164 LNCS
ISSN (versión impresa)0302-9743
ISSN (versión digital)1611-3349

Conferencia

Conferencia9th International Workshop on Approximation and Online Algorithms, WAOA 2011
País/TerritorioAlemania
CiudadSaarbrucken
Período8/09/119/09/11

Huella

Profundice en los temas de investigación de 'Optimization over integers with robustness in cost and few constraints'. En conjunto forman una huella única.

Citar esto