We study the applicability of lift-and-project methods to the SET COVER and KNAPSACK problems. Inspired by recent work of Karlin et al. (IPCO 2011), who examined this connection for KNAPSACK, we consider the applicabi...
详细信息
We study the applicability of lift-and-project methods to the SET COVER and KNAPSACK problems. Inspired by recent work of Karlin et al. (IPCO 2011), who examined this connection for KNAPSACK, we consider the applicability and limitations of these methods for SET COVER, as well as extend the existing results for Knapsack. For the SET COVER problem, Cygan et al. (IPL 2009) gave sub-exponential-time approximation algorithms with approximation ratios better than ln n. We present a very simple combinatorial algorithm which has nearly the same time-approximation tradeoff as the algorithm of Cygan et al. We then adapt this to an LP-based algorithm using the LP hierarchy of Lovasz and Schrijver. However, our approach involves the trick of "lifting the objective function". We show that this trick is essential, by demonstrating an integrality gap of (1 - epsilon) ln n at level Omega (n) of the stronger LP hierarchy of Sherali and Adams (when the objective function is not lifted). Finally, we show that the SDP hierarchy of Lovasz and Schrijver (LS+) reduces the integrality gap for KNAPSACK to (1 + epsilon) at level O(1). This stands in contrast to SET COVER (where the work of Aleknovich et al. (STOC 2005) rules out any improvement using LS+), and extends the work of Karlin et al., who demonstrated such an improvement only for the more powerful SDP hierarchy of Lasserre. Our LS+-based rounding and analysis are quite different from theirs (in particular, not relying on the decomposition theorem they prove for the Lasserre hierarchy), and to the best of our knowledge represents the first explicit demonstration of such a reduction in the integrality gap of LS+ relaxations after a constant number of rounds.
In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves is the allowed running time is gradually increased from polynomial to (sub-)exponential. We t...
详细信息
In this paper we focus on problems inapproximable in polynomial time and explore how quickly their approximability improves is the allowed running time is gradually increased from polynomial to (sub-)exponential. We tackle a number of problems: For MIN INDEPENDENT DOMINATING SET, MAX INDUCED PATH, FOREST and TREE, for any r(n), a simple, known scheme gives an approximation ratio of r in time roughly r(n/r). We show that, if this running time could be significantly improved, the ETH would fail. For MAX MINIMAL VERTEX COVER we give a root r-approximation in time 2(n/r). We match this with a similarly tight result. We also give a log r-approximation for MIN ATSP in time 2(n/r) and an r-approximation for MAX GRUNDY COLORING in time r(n/r). Finally, we investigate the approximability of MIN SET COVER, when measuring the running time as a function of the number of sets in the input. (C) 2017 Elsevier Inc. All rights reserved.
The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an arbitrary distribution, we would like to produce ...
详细信息
ISBN:
(纸本)9781605580470
The motivating problem is agnostically learning parity functions, i.e., parity with arbitrary or adversarial noise. Specifically, given random labeled examples from an arbitrary distribution, we would like to produce art hypothesis whose accuracy nearly matches the accuracy of the best;parity function. Our algorithm runs in time 2(O(n/log n)), which matches the best known for the easier cases of learning parities with random classification noise (Blum et al, 2003) and for agnostically learning parities over the uniform distribution oil inputs (Feldman et al, 2006). Our approach is as follows. We give an agnostic boosting theorem that is capable of nearly achieving optimal accuracy, improving upon earlier studies (starting with Bell David et al, 2001). To achieve this, we circumvent previous lower bounds by altering the boosting model. We then show that the (random noise) parity learning algorithm of Blum et al (2000) fits our new model of agnostic weak learner. Our agnostic boosting framework is completely general and may be applied to other agnostic learning problems. Hence, it also sheds light on the actual difficulty of agnostic learning by showing that full agnostic boosting is indeed possible.
暂无评论