检索结果-内蒙古大学图书馆

Faster exponential-time algorithms for approximately counting independent sets

THEORETICAL COMPUTER SCIENCE 2021年 892卷 48-84页

作者： Goldberg, Leslie Ann Lapinskas, John Richerby, David Univ Oxford Dept Comp Sci Oxford England Univ Bristol Dept Comp Sci Bristol Avon England Univ Essex Sch Comp Sci & Elect Engn Colchester Essex England

Counting the independent sets of a graph is a classical #P-complete problem, even in the bipartite case. We give an exponential-time approximation scheme for this problem which is faster than the best known algorithm for the exact problem. The running time of our algorithm on general graphs with error tolerance epsilon is at most O(2(0.2680n)) times a polynomial in 1/epsilon. On bipartite graphs, the exponential term in the running time is improved to O(2(0.2372n)). Our methods combine techniques from exact exponential algorithms with techniques from approximate counting. Along the way we generalise (to the multivariate case) the FPTAS of Sinclair, Srivastava, Stefankovic and Yin for approximating the hard-core partition function on graphs with bounded connective constant. Also, we obtain an FPTAS for counting independent sets on graphs with no vertices with degree at least 6 whose neighbours' degrees sum to 27 or more. By a result of Sly, there is no FPTAS that applies to all graphs with maximum degree 6 unless P = NP. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Independent sets exponential algorithms Approximate counting

来源：评论

学校读者我要写书评

暂无评论

PPSZ for General k-SAT and CSP-Making Hertli's Analysis Simpler and 3-SAT Faster

引用

COMPUTATIONAL COMPLEXITY 2024年第2期33卷 1-48页

作者： Scheder, Dominik Steinberger, John TU Chemnitz Chemnitz Germany Auki Labs Kowloon Bay Hong Kong Peoples R China

The currently fastest known algorithm for k-SAT is PPSZ, named after its inventors (Paturi et al. in J ACM 52(3):337-364, 2005. http://***/10.1145/1066100.1066101). Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify the analysis of Hertli (in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science-FOCS 2011, Los Alamitos, 2011) for input formulas with multiple satisfying assignments. Second, we show a "lifting result": if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF formulas. In combination this with results by Hansen et al. (in Charikar and Cohen (ed) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019) and Scheder (in 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021), who all prove improved time bounds for Unique-k-SAT, this gives improved bounds for general k-SAT. We also generalize our results to the domain of Constraint Satisfaction Problems, i.e., satisfiability with more than two truth values.

关键词： Boolean satisfiability exponential algorithms Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Stronger Connection between the Asymptotic Rank Conjecture and the Set Cover Conjecture 2024

A Stronger Connection between the Asymptotic Rank Conjecture...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Pratt, Kevin NYU Courant Inst Math Sci New York NY 10012 USA

ISBN: (纸本)9798400703836

We give a short proof that Strassen's asymptotic rank conjecture implies that for every epsilon > 0 there exists a (3/2(2/3) + epsilon)(n) -time algorithm for set cover on a universe of size n with sets of bounded size. This strengthens and simplies a recent result of Bjorklund and Kaski that Strassen's asymptotic rank conjecture implies that the set cover conjecture is false. From another perspective, we show that the set cover conjecture implies that a particular family of tensorsT(n) epsilon C-N circle times C-N circle times C-N has asymptotic rank greater than N-1.08. Furthermore, if one could improve a known upper bound of 8(n) on the tensor rank of T-n to 2/ 9 center dot n 8n for any n, then the set cover conjecture is false.

关键词： Algebraic complexity theory exponential algorithms fine-grained complexity tensor rank

来源：评论

学校读者我要写书评

暂无评论

PPSZ is better than you think 62

PPSZ is better than you think

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Scheder, Dominik Shanghai Jiao Tong Univ Dept Comp Sci Shanghai Peoples R China

ISBN: (纸本)9781665420556

PPSZ, for long time the fastest known algorithm for k-SAT, works by going through the variables of the input formula in random order;each variable is then set randomly to 0 or 1, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution;or being implied by a small set of clauses). We show that PPSZ performs exponentially better than previously known, for all k >= 3. For Unique-3-SAT we bound its running time by O(1.306973(n)), which is somewhat better than the algorithm of Hansen, Kaplan, Zamir, and Zwick. All improvements are achieved without changing the original PPSZ. The core idea is to pretend that PPSZ does not process the variables in uniformly random order, but according to a carefully designed distribution. We write "pretend" since this can be done without any actual change to the algorithm.(1 2)

关键词： exponential algorithms NP-complete problems randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Time-approximation trade-offs for inapproximable problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2018年 92卷 171-180页

作者： Bonnet, Edouard Lampis, Michael Paschos, Vangelis Th. Middlesex Univ Dept Comp Sci London England Univ Paris 09 PSL Res Univ CNRS UMR 7243LAMSADE F-75016 Paris France

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.

关键词： Approximation algorithms exponential algorithms Sub-exponential algorithms Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

PPSZ for k ≥ 5: More Is Better

引用

ACM TRANSACTIONS ON COMPUTATION THEORY 2019年第4期11卷 25-25页

作者： Scheder, Dominik Shanghai Jiao Tong Univ 800 Dongchuan Rd Shanghai 200240 Peoples R China

We show that for k >= 5, the PPSZ algorithm for k-SAT runs exponentially faster if there is an exponential number of satisfying assignments. More precisely, we show that for every k >= 5, there is a strictly increasing function f : [0, 1] -> R with f (0) = 0 that has the following property. If F is a k-CNF formula over n variables and vertical bar sat(F)vertical bar = 2(delta n) solutions, then PPSZ finds a satisfying assignment with probability at least 2(-ck n-o(n) + f(delta)n).Here, 2(-ck n-o(n)) is the success probability proved by Paturi et al. [11] for k-CNF formulas with a unique satisfying assignment. Our proof rests on a combinatorial lemma: given a set S subset of {0.1}(n), we can partition {0.1}(n) into subcubes such that each subcube B contains exactly one element of S. Such a partition B induces a distribution on itself, via Pr[B] = vertical bar B vertical bar/2(n) for each B is an element of B. We are interested in partitions that induce a distribution of high entropy. We show that, in a certain sense, the worst case (min(S:vertical bar S vertical bar =s) max(B) H(B)) is achieved if S is a Hamming ball. This lemma implies that every set S of exponential size allows a partition of linear entropy. This in turn leads to an exponential improvement of the success probability of PPSZ.

关键词： Boolean satisfiability exponential algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster 32

PPSZ for General <i>k</i>-SAT - Making Hertli's Analysis Sim...

引用

32nd Computational Complexity Conference (CCC)

作者： Scheder, Dominik Steinberger, John P. Shanghai Jiao Tong Univ Dept Comp Sci & Engn Shanghai Peoples R China Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing Peoples R China

ISBN: (纸本)9783959770408

The currently fastest known algorithm for k-SAT is PPSZ named after its inventors Paturi, Pudlak, Saks, and Zane [7]. Analyzing its running time is much easier for input formulas with a unique satisfying assignment. In this paper, we achieve three goals. First, we simplify Hertli's 2011 analysis [1] for input formulas with multiple satisfying assignments. Second, we show a "translation result": if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF formulas. Combining this with a result by Hertli from 2014 [2], in which he gives an algorithm for Unique-3-SAT slightly beating PPSZ, we obtain an algorithm beating PPSZ for general 3-SAT, thus obtaining the so far best known worst-case bounds for 3-SAT.

关键词： Boolean satisfiability exponential algorithms randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs

引用

ALGORITHMICA 2016年第1期75卷 84-117页

作者： Bruner, Marie-Louise Lackner, Martin Vienna Univ Technol Inst Discrete Math & Geometry A-1040 Vienna Austria Vienna Univ Technol Inst Informat Syst A-1040 Vienna Austria

The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of , where denotes the number of alternating runs of T. This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since , this can be seen as a algorithm which is the first to beat the exponential runtime of brute-force search. Furthermore, we prove that under standard complexity theoretic assumptions such a fixed-parameter tractability result is not possible for run(P).

关键词： Permutation patterns Parameterized complexity Pattern matching Fixed-parameter tractability exponential algorithms Combinatorics

来源：评论

学校读者我要写书评

暂无评论

PPSZ for general k-SAT: making Hertli's analysis simpler and 3-SAT faster 17

PPSZ for general k-SAT: making Hertli's analysis simpler and...

引用

Proceedings of the 32nd Computational Complexity Conference

作者： Dominik Scheder John P. Steinberger Shanghai Jiaotong University Shanghai China Tsinghua University Beijing China

ISBN: (纸本)9783959770408

In this paper, we achieve three goals. First, we simplify Hertli's 2011 analysis [1] for input formulas with multiple satisfying assignments. Second, we show a "translation result": if you improve PPSZ for k-CNF formulas with a unique satisfying assignment, you will immediately get a (weaker) improvement for general k-CNF *** this with a result by Hertli from 2014 [2], in which he gives an algorithm for Unique-3-SAT slightly beating PPSZ, we obtain an algorithm beating PPSZ for general 3-SAT, thus obtaining the so far best known worst-case bounds for 3-SAT.

关键词： randomized algorithms exponential algorithms boolean satisfiability

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation of MIN SET COVER by moderately exponential algorithms

引用

THEORETICAL COMPUTER SCIENCE 2009年第21-23期410卷 2184-2195页

作者： Bourgeois, N. Escoffier, B. Paschos, V. Th. LAMSADE CNRS UMR 7024 F-75775 Paris France Univ Paris 09 F-75775 Paris 16 France

We study the approximation Of MIN SET COVER combining ideas and results from polynomial approximation and from exact computation (with non-trivial worst case complexity upper bounds) for NP-hard problems. We design approximation algorithms for MIN SET COVER achieving ratios that cannot be achieved in polynomial time (unless problems in NP could be solved by slightly super-polynomial algorithms) with worst-case complexity much lower (though super-polynomial) than those of an exact computation. (C) 2009 Elsevier B.V. All rights reserved.

关键词： exponential algorithms Approximation algorithms MIN SET COVER

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：