Programación lineal para combinatoria/teoría de grafos

Question

Ayer fui a una charla de teoría de grafos que hablaba sobre varios parámetros fraccionarios de grafos (pero centrándose en uno). Estos fueron definidos usando programación lineal. Se hizo una pregunta, "¿Cómo podemos aprender más sobre esta técnica?" La respuesta dada fue, "Realmente no hay un buen recurso para programación lineal en combinatoria/teoría de grafos." Dijo que Schrijver (¿cómo se escribe?) tiene un libro pero tendrías que pasar por mucha información para obtener lo más importante para la teoría de grafos/combinatoria.

Entonces, ¿alguno de ustedes conoce alguna referencia buena específicamente orientada hacia teoría de grafos/combinatoria? Podría ser un libro, un capítulo de un libro, un artículo, lo que sea. ¡Gracias por cualquier ayuda!

Answer 1

Me gusta este libro Understanding and Using Linear Programming de Bernd Gärtner y Jiří Matoušek, y creo que la mayoría del material tiene un sabor combinatorio (publicado en 2006, ¡este libro es bastante reciente!). Sin embargo, es en su mayoría material básico (dirigido a principiantes). Si echas un vistazo a lo que el coautor Jiří Matoušek ha publicado, también encontrarás un libro con el título Using the Borsuk-Ulam theorem. A primera vista, parecerá que no tiene nada que ver con la programación lineal, sin embargo, hay al menos una intersección: el teorema de Borsuk-Ulam es muy general (puedes derivar el teorema del punto fijo de Brouwer, por ejemplo), pero también puedes derivar cosas 'claramente combinatorias' como el teorema del sándwich de jamón. Este teorema aparece en la variante 2D del algoritmo más rápido para 'las desviaciones absolutas mínimas', descrito en este artículo de William Steiger, que es casi equivalente a la programación lineal (me refiero a que 'las desviaciones absolutas mínimas' son casi equivalentes a la programación lineal, pero no conozco un algoritmo más allá de 2D para LAD que utilice efectivamente el teorema del sándwich de jamón, lo cual, por supuesto, no dice mucho).

Answer 2

Optimización combinatoria: Teoría y algoritmos (Algorithms and Combinatorics) (ISBN-13: 978-3642244872) y Optimización combinatoria: Poliedros y eficiencia (Algorithms and Combinatorics) (ISBN-13: 978-3540443896)

El primero como introducción general y suficiente para la mayoría de los casos, el segundo como material de referencia que cubre básicamente todo el tema