Dependent rounding in bipartite graphs

Rajiv Gandhi*, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan

*Corresponding author for this work

Research output: Contribution to journalConference article

50 Scopus citations

Abstract

The pipage rounding technique of Ageev & Sviridenko is combined with the recent rounding method developed by Srinivasan. The aim is to develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. A useful feature of the method is that it allows to prove certain (probabilistic) per-user fairness properties.

Original languageEnglish (US)
Pages (from-to)323-332
Number of pages10
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2002
EventThe 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada
Duration: Nov 16 2002Nov 19 2002

ASJC Scopus subject areas

  • Hardware and Architecture

Cite this