Heuristics for unequal weight delivery problems with a fixed error guarantee

A polynomial time heuristic for certain

A polynomial time heuristic for certain subgraph optimization problems with guaranteed worst case bound

✍ Svatopluk Poljak; Daniel Turzík 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 340 KB

We introduce a notion of ).-extendible property of graphs and prove: If P is a ).-extendible property (0<).<1), then for a connected graph G = (V, E) and an objective function c: E---\*R + one can construct a spanning subgraph H= (V, F) which has the property P and satisfies c(F) = ~. c(E) + ½