Probabilistic Construction of Deterministic Algorithms

Raghavan, P. (1988). Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs. Journal of Computer and System Sciences, 37(2).

Type

Journal article

Intellectual base

Primary research

Year

1988

DOI

10.1016/0022-0000(88)90003-7

Link

https://doi.org/10.1016/0022-0000(88)90003-7

Cited by

1 citation across 1 artifact.

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

Domain-specific

• Randomized Rounding
  • If conditional expectations or pessimistic estimators can be computed, the random choices can often be fixed deterministically without worsening the guarantee.

    This sourceThe primary paper develops deterministic algorithms that mimic randomized-rounding existence proofs through conditional-probability machinery.

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.

Registry ID ref:12f22130eac8 · see in the full table