PaperlayerView exact revision on arXiv

Source-linked AI summary

An Improved Approximation for $k$-median, and Positive Correlation in Budgeted Optimization

Jarosław Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, Khoa Trinh

arXiv:1406.2951v4cs.DS

TL;DR

The paper asks whether dependent rounding can retain hard-budget and negative-correlation guarantees while providing near-independence on small subsets. It develops generalized weighted dependent rounding and improved k-median bi-point rounding, obtaining a 2.675+ε approximation and improved ε-dependent runtime, while noting limits to further rounding-factor improvements.

  • Problem

    Existing dependent rounding provides hard constraints and negative correlation, but does not generally address near-independence or positive correlation on small subsets.

  • Method

    The paper combines generalized weighted dependent rounding with a multi-pronged analysis and improved rounding of k-median bi-point solutions.

  • Results

    2.675+ε is the k-median approximation ratio, improving Li and Svensson’s 2.733+ε; the approach also yields Aε with runtime O(n^{O(1/ε)}).

  • Takeaways & Limitations

    The resulting dependent-rounding schemes preserve existing guarantees while adding near-independence for not-too-large subsets, with applications to k-median and budgeted optimization.

  • Takeaways & Limitations

    The paper reports that its current factor-revealing analysis could improve only slightly by adding more nonlinear variables and splitting 1-stars into more classes.

Abstract

from arXiv · show

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to \emph{negative correlation} properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires \emph{positive} correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior - near-independence, which generalizes positive correlation - on "small" subsets of the variables. The recent breakthrough of Li & Svensson for the classical $k$-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for $k$-median from $2.732 + ε$ to $2.675 + ε$ by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter $ε$ from Li-Svensson's $N^{O(1/ε^2)}$ to $N^{O((1/ε) \log(1/ε))}$.

1 Introduction and High-Level Details

The paper combines an improved bi-point rounding algorithm for k-median with generalized dependent rounding that supports near-independence on small variable subsets. These contributions improve both the approximation ratio and runtime dependence on ε, while also yielding results for budgeted satisfiability.

  • Other applications: The paper also develops efficient samplers for generalized dependent-rounding distributions and obtains optimal approximations for certain budgeted satisfiability problems.The budgeted set-cover problem is included as a special case of the budgeted satisfiability results.
  • Dependent rounding: N^{O((1/ε) log(1/ε))} replaces Li and Svensson’s N^{O(1/ε^2)} runtime dependence on ε.The improvement comes from developing dependent rounding with an improved function f(ε), from Θ(1/ε) to Θ(log(1/ε)).
  • The k-median problem: 1.3371+ε is the improved factor obtained by the paper’s bi-point rounding algorithm.The algorithm is designed by analyzing worst-case instances of Li and Svensson’s approach and combining complementary rounding strategies.
  • The k-median problem: The k-median rounding analysis can improve over the center-or-all-leaves star property by closing both centers and leaves of selected long 1-stars.Stars are classified by the ratio between center-to-leaf distance and distance to the nearest leaf of a 2-star.
  • Dependent rounding: The dependent-rounding framework preserves existing hard-constraint and negative-correlation properties while adding near-independence for suitably small subsets.For t = o(α√n), the near-independence parameters β1 and β2 are o(1).

2 Dependent rounding with near-independence on small subsets

The paper develops weighted dependent rounding that preserves almost-integrality, marginal expectations, weighted sums, and negative-correlation properties while achieving near-independence on suitably small subsets. DepRound runs in linear time, and its bounds support dependence among groups as large as O(√n) when α = Θ(1).

  • Algorithm and guarantees: The weighted formulation preserves the weighted sum while leaving at most one variable fractional and maintaining near-independence for suitably small subsets.The target properties are almost-integrality, weighted-sum preservation, and near-independence when weights are not too far apart.
  • Quantitative bounds: Theorem 2.10 gives β1, β2 = O(t2/(nα3)) in its stated regime, while further results permit dependence among groups as large as O(√n) when α = Θ(1).Theorem 2.14 also yields a nontrivial bound for t = O(n/ln n) and a tight bound close to λ for some larger regime.
  • Pairwise rounding primitive: Simplify rounds two fractional values so that at least one becomes integral, the weighted sum is preserved exactly, and both joint-one and joint-zero products satisfy upper bounds.These are properties (B0), (B2), and (B3), which underpin the full DepRound analysis.
  • Algorithm and guarantees: DepRound samples a vector in O(n) time while satisfying properties (A0’), (A1’), (A2’), and (A3’).The construction uses a random permutation and repeatedly processes pairs of fractional variables.
  • Near-independence analysis: Randomly ordering variables is needed for the new near-independence property, although the other dependent-rounding properties hold under any ordering.The analysis compares products of target bits with products of their marginal probabilities, up to the effect of one possible fractional variable.
  • Quantitative bounds: The analysis establishes convergence of the relaxed series for 0 < x < 1 and derives a bound of at least (1 −ϵ)λ in the relevant setting.The falling factorial notation is used in the combinatorial bound leading to the convergent series.

3 Improved bi-point rounding algorithm

The paper improves bi-point rounding for k-median by analyzing worst-case instances and designing algorithms that control connection cost, facility-budget violations, and positive correlation. The resulting rounding guarantee is 1.3371+η with only O(log(1/η)) extra facilities, supporting a 2.675+ε approximation or a slower 2+ε alternative.

  • Lower-bound instances: A symmetric family of bi-point instances characterizes solutions by the proportions of facilities opened in F1 and F2.The construction uses facility sets of sizes f1k and f2k, clients associated with facility pairs, and solutions opening exactly k facilities.
  • Lower-bound instances: The new algorithm improves on Li and Svensson by considering solutions that open no facilities in F1 in the analyzed instance.Li and Svensson’s proportions are either (a, b) or (1, 0), whereas the new choice is crucial for obtaining an improved factor.
  • Main algorithm: Positive correlation within star groups is handled using varying-size geometric groups, reducing extra facilities from O(1/η) per grouping scheme to O(log(1/η)).Dependent-rounding properties support both varying star sizes and bounds on positive correlation.
  • Approximation guarantee: The nine parameterized algorithms achieve expected cost at most (1+η)·1.3371 times the bi-point cost across the analyzed parameter regimes.The central nonlinear-program case has optimum X* in [1.3370, 1.3371], while the remaining cases are covered by separate lemmas.
  • Budget control: The rounding procedure opens at most k + O(log(1/η)) facilities while maintaining the stated group-level opening bounds.The analysis bounds each group’s openings and shows the number of small-star groups and their per-group overhead are constant-bounded for fixed parameters.
  • Dichotomy result: The resulting dichotomy offers a randomized (2.675+ε)-approximation in O(n^O(1/ε)) time or a (2+ε)-approximation in O(n^O(poly(1/ε))) time.The faster algorithm succeeds with constant probability.

4 Discussion

The discussion identifies modest additional gains in bi-point rounding, while noting that these gains increase algorithmic and analytical complexity. It also points to broader applications of the dependent-rounding framework beyond k-median.

  • A three-class split of 1-stars yields a factor in [1.332, 1.3371), improving slightly over 1.3371.The refinement uses multiple size-to-distance thresholds and adds nonlinear variables to the factor-revealing program.
  • The potential improvement comes at the cost of greater algorithm and analysis complexity.
  • Fixing r1A exactly large enough to close and open all big leaves simplifies the algorithms but may not be optimal.The authors suggest that r1A could instead depend on other instance variables, although this would create more cases.
  • The paper speculates that probabilistic methods for bipartite graphs may help satisfy capacity constraints with probability one while retaining desired correlation properties.

A Proofs for Section 3: DepRound

The DepRound proof verifies its case-based rounding properties by checking output probabilities, preservation of weighted mass, and pairwise correlation bounds.

  • Case I sets one of γ1 or γ2 to zero while defining the other to preserve the required marginal relation.
  • The proof establishes the first correlation bound from E[γ1γ2] = 0 ≤ β1β2.

B Proofs: Bounding the number of opened facilities

These proofs bound the number of facilities opened across the algorithm’s cases, including direct-opening branches and the Round2Stars subroutine, and show feasibility relative to k.

  • Round2Stars is called only in A1 through A6; A7 and A8 use a different line instead.
  • The direct-opening lines contribute bounds based on p0|C0| + 1, p1A|C1A| + q1A|C1A| + 2, and p1B|C1B| + q1B|C1B| + 2.
  • If line 5 executes, the number opened is at most p2|C2| + q2|L2| + 1.
  • When Round2Stars is called, its line-1 count is at most p2|C′2| + q2|L′2| + 1.
  • The proof concludes that the total number of opened facilities is bounded by k + 1 across the cases.For A1, the expression simplifies exactly to k; A7 and A8 are handled separately, and A9 is the Li-Svensson algorithm.
  • A9 opens an expected-count expression a|C0| + a|C1| + b|L1| + a|C2| + b|L2|.

C Proofs: Bounding client connection cost

The connection-cost proofs derive upper bounds by selecting fallback facilities and using star structure, triangle inequalities, and the rounding relationships among candidate facilities.

  • When i1 ≠ i3, connecting through i3 gives d(j,i3) ≤ d1 + 2d2.The bound follows from the star construction and the triangle inequality.
  • Connecting first to i2, then i1, then i3 yields d2 + Pr[¯i2](d1 − d2) + 2Pr[¯i1¯i2]d2.
  • The alternative connection order through i1, i2, and i3 provides an equally valid bound.
  • If i1 = i3, at least one of i1 or i2 is always open, so the proof compares fallback orders without needing i4 or i5.
  • For cases where i1, i2, and i3 may all be closed, i4 and its center i5 provide additional fallback facilities.The proof bounds d(i3,i4) and uses the fact that closing i4 forces i5 to be open.
  • For a 1-star, the parameter gi relates center-leaf distance to the nearest relevant L2 distance and enters the two candidate connection-cost bounds.
  • The inequality d2 ≤ d1 + g(d1 + d2) ensures the coefficient d1 − d2 + g(d1 + d2) is nonnegative.

D Interval relaxation: Bounding the NLP

The authors bound the factor-revealing nonlinear program using interval relaxations that become linear after fixing four variables. Recursive subdivision and interval arithmetic yield a systematic upper bound of 1.3371.

  • Interval relaxation: Fixing four variables renders the nonlinear program linear, enabling efficient solution of a relaxed linear program.The original program is nonconvex, so local search does not guarantee global optimality.
  • Certified bound: 1.3371 is the systematically proved upper bound on the nonlinear program obtained through interval arithmetic.The calculation solved roughly 8 million intervals in about 7 hours on an Intel Core i7 2.9GHz machine.
  • Interval relaxation: Each constraint is relaxed by maximizing its variable-dependent function over a small interval, producing a valid upper bound.The relaxation can be loose because terms are maximized independently, but sufficiently small intervals provide arbitrary precision.
  • Search procedure: Intervals whose bounds exceed the target are recursively divided into 16 subintervals before resolving the relaxed program.The implementation starts from several large intervals and subdivides each variable by halves.
  • Implementation: The implementation reduces variables by applying the P/N class division only to selected client classes and using bounds for the others.It also adds a constraint based on Li and Svensson’s relaxed formula.

D.1 Tight example

A constructed solution achieves 1.3370 in the factor-revealing program, matching the reported upper bound closely. This demonstrates that the nonlinear-program bound is tight.

  • Tight example: 1.3370 is achieved by an explicit solution of the factor-revealing nonlinear program.The authors note that multiple solutions are possible because some D-type variables have freedom.
  • Tight example: The example shows that the upper bound on the nonlinear program is tight.The achieved value is only 0.0001 below the reported upper bound of 1.3371.

E Proofs: Algorithms for edge cases

The edge-case analysis combines several rounding algorithms, knapsack procedures, and interval searches to maintain a factor near 1.337 across parameter regimes. The algorithms use only a small additive number of extra facilities.

  • Ratio bounds: 4/3 is achieved when b ≥5/6 using a knapsack algorithm that opens at most k + 2 facilities.The ratio is bounded by 1 + 2a ≤4/3 when a ≤1/6.
  • Ratio bounds: 1.337 is the claimed approximation ratio for the remaining edge cases after separating parameter regimes.For specified ranges of b and rD, elementary calculus directly bounds the relevant ratio by 1.337.
  • Knapsack procedures: The two edge-case algorithms open at most k + 2 facilities, using a knapsack LP and a greedy treatment of its single fractional value.The randomized rounding of that fractional value achieves expected savings at least equal to the LP optimum.
  • Algorithm combination: The authors run the two edge-case algorithms together with A′ and use the best of the three solutions.Interval search over the specified ranges gives an upper bound of 1.3371 on the factor-revealing NLP.

F.1 Case 1

In Case 1, the rounding analysis controls both connection cost and the number of extra facilities through randomized choices on small stars. With suitable f, it obtains the desired bound with constant positive probability.

  • Randomized rounding: The algorithm independently sets each small-star indicator Xi to 1 with probability (1 −η)q2.The indicators determine whether a star is opened and its center is closed.
  • Facility-count control: Chernoff’s bound controls the number of facilities opened in small stars.The analysis introduces random variables Yi and bounds their aggregate using the fact that small stars have at least two leaves.
  • Connection cost: 1.337 is the expected connection-cost factor relative to the bipoint solution.The result is stated as a corollary for the solution returned by the algorithm.
  • Facility-count control: At most 4 additional facilities are opened when the relevant class size exceeds a polynomial threshold f(1/η).The threshold satisfies f = O(poly(1/η)).
  • Combined guarantee: The algorithm achieves connection cost at most 1.3371(1 + η) times the bipoint cost with constant positive probability.The probability is a positive function of η and is strictly positive for sufficiently small η.

F.3 Case 3

Case 3 completes the rounding analysis by handling the remaining star configuration and obtaining a bounded-extra-facility solution with a 1.337-dependent cost guarantee. The resulting k-median algorithm runs in O(n^O(4/ϵ)) time.

  • Case 3 handles instances where neither Case 1 nor Case 2 applies.
  • The construction controls large-star centers and leaves through a budget allocation and probability q2(1 − c1η) for opening leaves.
  • The algorithm opens at most 4 additional facilities and has expected connection cost at most 1.337 · (1 + (1 − β)η/β)(1 + η) times the bi-point cost.
  • The proof sets c0 = 2 and c1 = 1, with no extra facilities opened in C′′2 ∪ L′′2.
  • The resulting approximation algorithm runs in O(n^O(4/ϵ)) time for k-median.

G A simple approach to the budgeted MAX-SAT problem

This section gives a simple LP-based approach to budgeted MAX-SAT: scale an optimal fractional solution before independent rounding, using brute force when the budget is small. The method achieves the stated approximation and high-probability feasibility guarantees.

  • The LP uses yj for whether variable xj is True and zi for whether clause i is satisfied, subject to the budget and clause-satisfaction constraints.
  • For k ≤ 1/ϵ^3, the algorithm finds an optimal solution by brute force; otherwise, it scales y*j by 1 − ϵ before independent rounding.
  • When k ≥ 1/ϵ^3, the algorithm produces a feasible budgeted MAX-SAT solution with probability at least 1 − exp(…).
  • The expected number of satisfied clauses is at least (1 − 1/e − ϵ)OPT.
  • The analysis uses scaled LP variables and concavity to establish the expected-satisfaction guarantee.

H JMS with scaling

This section introduces a scaled variant of the JMS algorithm for UFL and explains its intended analysis. The algorithm scales contributions from unconnected clients by γ while retaining the JMS event structure.

  • The standard JMS algorithm models client budgets, facility-opening contributions, and reconnections to newly opened closer facilities.
  • The algorithm increases client budgets until either a facility receives enough total offers to open or an unconnected client reaches an open facility’s distance.
  • The JMS approximation factor is bounded through a factor-revealing LP whose objective values are at most 1.61 for every positive integer k.
  • The paper presents a new JMS variant and emphasizes how it differs from standard JMS.
  • The intended modification combines a tax on savings from switching facilities with scaled contributions from unconnected clients.
  • JMS′(γ) is a variant of the JMS algorithm that scales each yet-unconnected client’s real contribution by γ.

H.3 Our incorrect analysis

The section identifies an incorrect factor-revealing-LP analysis of JMS′ and gives counterexamples showing why the claimed bound underestimates the algorithm’s cost. The problematic variable interpretation breaks a key inequality and yields an asymptotic ratio of 1 + γ.

  • The earlier analysis interpreted rj,i as the connection cost precisely when client i first connects, but this interpretation can invalidate a required inequality.
  • A counterexample uses one client connected at distance 1 while its budget parameter satisfies α1 = r1,1 = 2(k − 1) + 1.
  • The remaining clients connect at distance 0 but have αi = ri,i = 2 because they contribute toward opening facility f.
  • Because ri,i can exceed ci despite having a negative objective coefficient, the LP underestimates the algorithm’s actual cost.
  • The counterexample’s asymptotic cost ratio approaches 1 + γ as k tends to infinity.
  • Combining 2k copies sharing the problematic facility f′ produces an instance with uniform facility costs on which JMS′(γ) opens all facilities.
Loading 1406.2951v4…