𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A bounded approximation for the minimum cost 2-sat problem

✍ Scribed by Dan Gusfield; Leonard Pitt

Publisher
Springer
Year
1992
Tongue
English
Weight
969 KB
Volume
8
Category
Article
ISSN
0178-4617

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A deterministic annealing algorithm for
A deterministic annealing algorithm for the minimum concave cost network flow problem
✍ Chuangyin Dang; Yabin Sun; Yuping Wang; Yang Yang πŸ“‚ Article πŸ“… 2011 πŸ› Elsevier Science 🌐 English βš– 292 KB

The existing algorithms for the minimum concave cost network flow problems mainly focus on the singlesource problems. To handle both the single-source and the multiple-source problem in the same way, especially the problems with dense arcs, a deterministic annealing algorithm is proposed in this pap

A logarithmic approximation algorithm fo
A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem
✍ Ioannis Caragiannis; Christos Kaklamanis; Panagiotis Kanellopoulos πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 123 KB

Motivated by the problem of supporting energy-efficient broadcasting in ad hoc wireless networks, we study the Minimum Energy Consumption Broadcast Subgraph (MECBS) problem. We present the first logarithmic approximation algorithm for the problem which uses an interesting reduction to Node-Weighted