Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

On the Equivalence between the Primal-Dual Schema and the Local-Ratio Technique

Reuven Bar-YehudaContact Information and Dror RawitzContact Information

(8)  Department of Computer Science, Technion, Haifa, 32000, Israel
Abstract
We discuss two approximation approaches, the primal-dual schema and the local-ratio technique. We present two relatively simple frameworks, one for each approach, which extend known frameworks for covering problems. We show that the two are equivalent, and conclude that the integrality gap of an integer program serves as a bound to the approximation ratio when working with the local-ratio technique.

Contact Information Reuven Bar-Yehuda
Email: reuven@cs.technion.ac.il

Contact Information Dror Rawitz
Email: rawitz@cs.technion.ac.il
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb07
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)