The Parsimonious Property of Cut Covering Problems and Its Applications (Classic Reprint): January, 1994: January, 1994 (Classic Reprint) - Softcover

Inhaltsangabe

Unlock a unifying view of how certain optimization problems stay simple at their core. This book reveals the parsimonious property and shows how it explains the behavior of LP relaxations across classic problems.

From survivable network design to the T-join, matching, and beyond, the text develops a framework that links structural conditions to strong, sometimes surprising, results. It presents proofs, monotonicity insights, and a new proof technique that leads to approachable approximation methods.

• Understand how the parsimonious property reduces complexity in the LP relaxation.


• See why certain problems stay integral or become easier to approximate.


• Explore conditions under which the property holds and where it fails.


• Learn a practical proof approach that informs algorithm design.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.