Titlebook: Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques; Third International Dorit S. Hochbaum,Klaus Janse

Humble

否认

Guaff豪情痛饮

Improved Bounds for Sampling Contingency Tables. We give an approximation algorithm which runs in polynomial time provided that the row and column sums satisfy .. =Ω (... log(.)), and .. =Ω (... log(.)). Our algorithm is based on a reduction to continuous sampling from a convex set. This is an approach which was taken by Dyer, Kannan and Mount i

right-atrium

Addictive

ureter

几何学家

ALT

Scheduling with Machine Coste scheduling problems with the modification that initially the algorithm possesses no machines, but that at any point additional machines may be purchased. Upper and lower bounds on the competitive ratio are shown for both problems.

FAST

HUMP

Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Familiesm form . statisfies....We show connections of such families with ., and give explicit constructions of such families . of size . for . = 1 / .., improving upon the previously best-known bound of Indyk [4]. We also present polynomial-size constructions when the min-wise condition is required only for ., with ..