Dependent Rounding and Its Applications to Approximation Algorithms

Gandhi, R., Khuller, S., Parthasarathy, S., & Srinivasan, A. (2006). Dependent Rounding and Its Applications to Approximation Algorithms. Journal of the ACM, 53(3).

Type

Journal article

Intellectual base

Primary research

Year

2006

DOI

10.1145/1147954.1147956

Link

https://doi.org/10.1145/1147954.1147956

Cited by

1 citation across 1 artifact.

Each citation links to the sentence it supports in the citing article.

Domain-specific

• Randomized Rounding
  • Dependent rounding handles constraints that independent choices would disrupt by coupling variables while preserving marginals and tightly controlling sums.

    This sourceThe primary paper verifies marginal preservation, degree preservation, negative-correlation properties, and multiple approximation-algorithm applications.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 1 other way.

• https://crab.rutgers.edu/users/rajivg/publications/journal/jacm06.pdf ×1

Registry ID ref:fe7a1f7699ee · see in the full table