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

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

来源：评论

学校读者我要写书评

暂无评论

Approximation of MIN COLORING by moderately exponential algorithms

引用

INFORMATION PROCESSING LETTERS 2009年第16期109卷 950-954页

作者： Bourgeois, Nicolas Escoffier, Bruno Paschos, Vangelis Th. LAMSADE CNRS FRE 3234 Paris France Univ Paris 09 F-75775 Paris 16 France

We study in this note approximation algorithms for the problem of coloring the vertices of a graph with as few colors as possible, with moderately exponential running times (and using either polynomial or exponential space), better than those of exact computation. Study of approximation is performed with respect to optimality measures, the minimum number of used colors and the maximum number of unused colors. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Min coloring problem exponential algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

exponential approximation schemata for some network design problems

引用

JOURNAL OF DISCRETE algorithms 2013年 22卷 43-52页

作者： Boria, Nicolas Bourgeois, Nicolas Escoffier, Bruno Paschos, Vangelis Th. Univ Torino Dipartmento Inforrnat Turin Italy Univ Paris Pantheon Sorbonne SAMM Pantheon Sorbonne France Univ Paris 09 PSL Res Univ CNRS UMR 7243 LAMSADE Paris France Inst Univ France Paris France

We study approximation of some well-known network design problems such as the TRAVELING SALESMAN PROBLEM (for both minimization and maximization versions) and the MIN STEINER TREE problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled. (C) 2013 Elsevier B.V. All rights reserved.

关键词： exponential algorithms Approximation algorithms Steiner tree Traveling salesman problem

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Bandwidth and distortion revisited

引用

DISCRETE APPLIED MATHEMATICS 2012年第4-5期160卷 494-504页

作者： Cygan, Marek Pilipczuk, Marcin Univ Warsaw Fac Math Comp Sci & Mech PL-02092 Warsaw Poland

In this paper we merge recent developments on exact algorithms for finding an ordering of vertices of a given graph that minimizes bandwidth (the BANDWIDTH problem) and for finding an embedding of a given graph into a line that minimizes distortion (the DISTORTION problem). For both problems we develop algorithms that work in O(9.363(n)) time and polynomial space. For BANDWIDTH, this improves O*(10(n)) algorithm by Feige and Kilian from 2000, for DISTORTION this is the first polynomial space exact algorithm that works in O(c(n)) time we are aware of. As a byproduct, we enhance the O(5(n+o(n)))-time and O*(2(n))-space algorithm for DISTORTION by Fomin et al. to an algorithm working in O(4.383(n))-time and space. (c) 2011 Elsevier B.V. All rights reserved.

关键词： Bandwidth Distortion Exact algorithms exponential 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

来源：评论

学校读者我要写书评

暂无评论

Capacitated domination faster than O(2ⁿ)

引用

INFORMATION PROCESSING LETTERS 2011年第23-24期111卷 1099-1103页

作者： Cygan, Marek Pilipczuk, Marcin Wojtaszczyk, Jakub Onufry Polish Acad Sci Inst Math PL-00901 Warsaw Poland Univ Warsaw Dept Math Comp Sci & Mech PL-00325 Warsaw Poland

In this paper we consider the CAPACITATED DOMINATING SET problem a generalisation of the DOMINATING SET problem where each vertex v is additionally equipped with a number c(v), which is the number of other vertices this vertex has the capacity to dominate. We provide an algorithm that solves CAPACITATED DOMINATING SET exactly in O(1.89(n)) time and polynomial space. Despite the fact that the CAPACITATED DOMINATING SET problem is quite similar to the DOMINATING SET problem, we are not aware of any published algorithms solving this problem faster than the straightforward O*(2(n)) solution prior to this paper. This was stated as an open problem at Dagstuhl seminar 08431 in 2008 and IWPEC 2008. We also provide an exponential approximation scheme for CAPACITATED DOMINATING SET which is a trade-off between the time complexity and the approximation ratio of the algorithm. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Graph algorithms exponential algorithms Dominating set Capacitated domination

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for MIN INDEPENDENT DOMINATING SET

引用

DISCRETE APPLIED MATHEMATICS 2013年第4-5期161卷 558-572页

作者： Bourgeois, N. Della Croce, F. Escoffier, B. Paschos, V. Th. CNRS LAMSADE F-75700 Paris France Univ Paris 09 F-75775 Paris 16 France Politecn Torino DAI Turin Italy

We first devise a branching algorithm that computes a minimum independent dominating set with running time O*(1.3351(n)) = O*(2(0.417n)) and polynomial space. This improves upon the best state of the art algorithms for this problem. We then study approximation of the problem by moderately exponential time algorithms and show that it can be approximated within ratio 1 + epsilon, for any epsilon > 0, in a time smaller than the one of exact computation and exponentially decreasing with epsilon. We also propose approximation algorithms with better running times for ratios greater than 3 in general graphs and give improved moderately exponential time approximation results in triangle-free and bipartite graphs. These latter results are based upon a new bound on the number of maximal independent sets of a given size in these graphs, which is a result interesting per se. (C) 2012 Elsevier B.V. All rights reserved.

关键词： MIN INDEPENDENT DOMINATING SET exponential algorithms Exact algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：