𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Domination analysis of combinatorial optimization problems

✍ Scribed by Gregory Gutin; Alek Vainshtein; Anders Yeo

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
141 KB
Volume
129
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

We use the notion of domination ratio introduced by Glover and Punnen in 1997 to present a new classiΓΏcation of combinatorial optimization (CO) problems: DOM-easy and DOM-hard problems. It follows from results already proved in the 1970s that min TSP (both symmetric and asymmetric versions) is DOM-easy. We prove that several CO problems are DOM-easy including weighted max k-SAT and max cut. We show that some other problems, such as max clique and min vertex cover, are DOM-hard unless P = NP.

πŸ“œ SIMILAR VOLUMES

On simple combinatorial optimization pro
On simple combinatorial optimization problems
✍ A.J. Hoffman πŸ“‚ Article πŸ“… 1992 πŸ› Elsevier Science 🌐 English βš– 228 KB

We characterize (0,l) linear programming matrices for which a greedy algorithm and its dual solve certain covering and packing problems. Special cases are shortest path and minimum spanning tree algorithms.

Combinatorial optimization problems in t
Combinatorial optimization problems in the analysis and design of probabilistic networks
✍ D. Bauer; F. Boesch; C. Suffel; R. Tindell πŸ“‚ Article πŸ“… 1985 πŸ› John Wiley and Sons 🌐 English βš– 668 KB

This paper presents some results regarding the design of reliable networks. The problem under consideration involves networks which are undirected graphs having equal and independent edge failure probabilities. The index of reliability is the probability that the network fails (becomes disconnected)