The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree @math , an additional set of edges @math disjoint from @math called , and a cost vector @math , WTAP asks to find a minimum-cost set @math with the property that @math is @math -edge connected. The special case where @math for all @math is called the Tree Augmentation Problem (TAP). Both problems are known to be NP-hard. For the class of bounded cost vectors, we present a first improved approximation algorithm for WTAP since more than three decades. Concretely, for any @math and @math we present an LP based @math -approximation for WTAP restricted to cost vectors @math in @math for @math . For the special case of TAP we improve this factor to @math . Our results rely on a new LP, that significantly differs from existing LPs achieving improved bounds for TAP. We round a fractional solution in two phases. The first phase uses the fractional solution to decompose the tree and its fractional solution into so-called @math -simple pairs losing only an @math -factor in the objective function. We then show how to use the additional constraints in our LP combined with the @math -simple structure to round a fractional solution in each part of the decomposition.
The bundle LP differs from all existing LPs that were recently proved to have integrality gap better than @math . Indeed, most existing such LPs include, on top of the constraints of the natural LP, constraints that exploit structural properties of feasible, or optimal solutions restricted to very specific structures, such as etc. (see @cite_8 for formal definitions of these and other related notions). In contrast, as we discussed before, the bundle LP attempts to uniformly cut off fractional solutions that have low cost due to sufficiently simple obstructions which have large integrality gap.
@cite_8
1806207712 2150285483 2107698341 2112788936
Recent work has shown that the classical framework of solving optimization problems by obtaining a fractional solution to a linear program (LP) and rounding it to an integer solution can be extended to the online setting using primal-dual techniques. The success of this new framework for online optimization can be gauged from the fact that it has led to progress in several longstanding open questions. However, to the best of our knowledge, this framework has previously been applied to LPs containing only packing or only covering constraints, or minor variants of these. We extend this framework in a fundamental way by demonstrating that it can be used to solve mixed packing and covering LPs online, where packing constraints are given offline and covering constraints are received online. The objective is to minimize the maximum multiplicative factor by which any packing constraint is violated, while satisfying the covering constraints. Our results represent the first algorithm that obtains a polylogarithmic competitive ratio for solving mixed LPs online. We then consider two canonical examples of mixed LPs: unrelated machine scheduling with startup costs, and capacity constrained facility location. We use ideas generated from our result for mixed packing and covering to obtain polylogarithmic-competitive algorithms for these problems. We also give lower bounds to show that the competitive ratios of our algorithms are nearly tight. We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n1 2-ϵ)-approximations for CLIQUE require LPs of size 2nΩ(ϵ). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov’s [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix. Motivated by online advertisement and exchange settings, greedy randomized algorithms for the maximum matching problem have been studied, in which the algorithm makes (random) decisions that are essentially oblivious to the input graph. Any greedy algorithm can achieve performance ratio 0.5, which is the expected number of matched nodes to the number of nodes in a maximum matching. Since Aronson, Dyer, Frieze and Suen proved that the Modified Randomized Greedy algorithm achieves performance ratio 0.5 + e (where e = 1 400000) on arbitrary graphs in the mid-nineties, no further attempts in the literature have been made to improve this theoretical ratio for arbitrary graphs until two papers were published in FOCS 2012. In this paper, we revisit the Ranking algorithm using the LP framework. Special care is given to analyze the structural properties of the Ranking algorithm in order to derive the LP constraints, of which one known as the boundary constraint requires totally new analysis and is crucial to the success of our LP. We use continuous LP relaxation to analyze the limiting behavior as the finite LP grows. Of particular interest are new duality and complementary slackness characterizations that can handle the monotone and the boundary constraints in continuous LP. Our work achieves the currently best theoretical performance ratio of [EQUATION] on arbitrary graphs. Moreover, experiments suggest that Ranking cannot perform better than 0.724 in general. We consider packing LP's with m rows where all constraint coefficients are normalized to be in the unit interval. The n columns arrive in random order and the goal is to set the corresponding decision variables irrevocably when they arrive to obtain a feasible solution maximizing the expected reward. Previous (1−e)-competitive algorithms require the right-hand side of the LP to be @math , a bound that worsens with the number of columns and rows. However, the dependence on the number of columns is not required in the single-row case and known lower bounds for the general case are also independent of n. Our goal is to understand whether the dependence on n is required in the multi-row case, making it fundamentally harder than the single-row version. We refute this by exhibiting an algorithm which is (1−e)-competitive as long as the right-hand sides are @math . Our techniques refine previous PAC-learning based approaches which interpret the online decisions as linear classifications of the columns based on sampled dual prices. The key ingredient of our improvement comes from a non-standard covering argument together with the realization that only when the columns of the LP belong to few 1-d subspaces we can obtain small such covers; bounding the size of the cover constructed also relies on the geometry of linear classifiers. General packing LP's are handled by perturbing the input columns, which can be seen as making the learning problem more robust.