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

exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期39卷 764-775页

作者： T'kindt, Vincent Shang, Lei Della Croce, Federico Univ Tours CNRS 7002 Lab Fundamental & Appl Comp Sci ERLEA 6300 64 Ave Jean Portalis F-37200 Tours France Politecn Torino DIGEP Corso Duca Abruzzi 24 I-10129 Turin Italy CNR IEIIT Turin Italy

This paper focuses on the solution, by exact exponential-time algorithms, of just-in-time scheduling problems when jobs have symmetric earliness/tardiness weights and share a non restrictive common due date. For the single machine problem, a Sort & Search algorithm is proposed with worst-case time and space complexities in O*(1.4143n) This algorithm relies on an original modeling of the problem. For the case of parallel machines, an algorithm integrating a dynamic programming algorithm across subsets and machines and the above Sort & Search algorithm is proposed with worst-case time and space complexities in O*(3n) To the best of our knowledge, these are the first worst-case complexity results obtained for non regular criteria in scheduling.

关键词： Single machine Parallel machines Just-in-time exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximation of MAX INDEPENDENT SET, MIN VERTEX COVER and related problems by moderately exponential algorithms

引用

DISCRETE APPLIED MATHEMATICS 2011年第17期159卷 1954-1970页

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

Using ideas and results from polynomial time approximation and exact computation we design approximation algorithms for several NP-hard combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular two paradigmatic problems, MAX INDEPENDENT SET and MIN VERTEX COVER. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Approximation algorithms exponential time algorithms Maximum independent set Minimum vertex cover

来源：评论

学校读者我要写书评

暂无评论

Approximating MAX SAT by moderately exponential and parameterized algorithms

引用

THEORETICAL COMPUTER SCIENCE 2014年第Part2期560卷 147-157页

作者： Escoffier, Bruno Paschos, Vangelis Th. Tourniaire, Emeric Univ Paris 04 UPMC LIP6 F-75005 Paris France CNRS UMR 7606 LIP6 F-75005 Paris France PSL Res Univ Univ Paris 09 LAMSADE CNRSUMR 7243 Paris France Inst Univ France Paris France

We study approximation of the MAX SAT problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time. We develop several approximation techniques that can be applied to MAX SAT in order to get approximation ratios arbitrarily close to 1. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Maximum satisfiability exponential time algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

New Tools and Connections for exponential-time Approximation

引用

ALGORITHMICA 2019年第10期81卷 3993-4009页

作者： Bansal, Nikhil Chalermsook, Parinya Laekhanukit, Bundit Nanongkai, Danupon Nederlof, Jesper Eindhoven Univ Technol Eindhoven Netherlands Aalto Univ Helsinki Finland Shanghai Univ Finance & Econ Shanghai Peoples R China Royal Inst Technol KTH Stockholm Sweden

In this paper, we develop new tools and connections for exponential time approximation. In this setting, we are given a problem instance and an integer r > 1, and the goal is to design an approximation algorithm with the fastest possible running time. We give randomized algorithms that establish an approximation ratio of 1. r for maximum independent set in O*(exp((O) over tilde (n/r log(2) r + r log(2) r))) time, 2. r for chromatic number in O*(exp((O) over tilde (n/r log r + r log(2) r))) time, 3. (2 - 1/r) for minimum vertex cover in O*(exp(n/r(Omega(r)))) time, and 4. (k - 1/r) for minimum k-hypergraph vertex cover in O*(exp(n/(kr)(Omega(kr)))) time. (Throughout, (O) over tilde and O* omit polyloglog(r) and factors polynomial in the input size, respectively.) The best known time bounds for all problems were O*(2n/r) (Bourgeois et al. in Discret Appl Math 159(17): 1954-1970, 2011;Cygan et al. in exponential-time approximation of hard problems, 2008). For maximum independent set and chromatic number, these bounds were complemented by exp(n(1-o(1))/r(1+o(1))) lower bounds (under the exponential time Hypothesis (ETH)) (Chalermsook et al. in Foundations of computer science, FOCS, pp. 370-379, 2013;Laekhanukit in Inapproximability of combinatorial problems in subexponential-time. Ph.D. thesis, 2014). Our results show that the naturally-looking O*(2n/r) bounds are not tight for all these problems. The key to these results is a sparsification procedure that reduces a problem to a bounded-degree variant, allowing the use of approximation algorithms for bounded-degree graphs. To obtain the first two results, we introduce a new randomized branching rule. Finally, we show a connection between PCP parameters and exponential-time approximation algorithms. This connection together with our independent set algorithm refute the possibility to overly reduce the size of Chan's PCP (Chan in J. ACM 63(3): 27: 1-27: 32, 2016). It also implies that a (significant) improvement over our

关键词： Approximation algorithms PCP's exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

Gate elimination: Circuit size lower bounds and #SAT upper bounds

引用

THEORETICAL COMPUTER SCIENCE 2018年 719卷 46-63页

作者： Golovnev, Alexander Kulikov, Alexander S. Smal, Alexander V. Tamaki, Suguru NYU New York NY 10003 USA Russian Acad Sci Steklov Inst Math St Petersburg Dept St Petersburg Russia Kyoto Univ Kyoto Japan

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the known case analyses can also be used to prove average case circuit lower bounds, that is, lower bounds on the size of approximations of an explicit function. In this paper, we provide a general framework for proving worst/average case lower bounds for circuits and upper bounds for #SAT that is built on ideas of Chen and Kabanets. A proof in such a framework goes as follows. One starts by fixing three parameters: a class of circuits, a circuit complexity measure, and a set of allowed substitutions. The main ingredient of a proof goes as follows: by going through a number of cases, one shows that for any circuit from the given class, one can find an allowed substitution such that the given measure of the circuit reduces by a sufficient amount. This case analysis immediately implies an upper bound for #SAT. To obtain worst/average case circuit complexity lower bounds one needs to present an explicit construction of a function that is a disperser/extractor for the class of sources defined by the set of substitutions under consideration. We show that many known proofs (of circuit size lower bounds and upper bounds for #SAT) fall into this framework. Using this framework, we prove the following new bounds: average case lower bounds of 3.24n and 2.59n for circuits over U-2 and B-2, respectively (though the lower bound for the basis B-2 is given for a quadratic disperser whose explicit construction is not currently known), and faster than 2(n) #SAT-algorithms for circuits over U-2 and B-2 of size at most 3.24n and 2.99n, respectively. Here by B-2 we mean the set of all bivariate Boolean functions, and by U-2 the set of all bivariate Boolean functions except for parity

关键词： Circuit complexity Lower bounds exponential time algorithms Satisfiability

来源：评论

学校读者我要写书评

暂无评论

A Note on Exact algorithms for Vertex Ordering Problems on Graphs

引用

THEORY OF COMPUTING SYSTEMS 2012年第3期50卷 420-432页

作者： Bodlaender, Hans L. Fomin, Fedor V. Koster, Arie M. C. A. Kratsch, Dieter Thilikos, Dimitrios M. Univ Utrecht Dept Informat & Comp Sci NL-3508 TB Utrecht Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway Rhein Westfal TH Aachen Lehrstuhl Math 2 D-52062 Aachen Germany Univ Metz LITA F-507045 Metz 01 France Univ Athens Dept Math Athens 15784 Greece

In this note, we give a proof that several vertex ordering problems can be solved in O (au)(2 (n) ) time and O (au)(2 (n) ) space, or in O (au)(4 (n) ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196-210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486-502, 1987). We survey a number of vertex ordering problems to which the results apply.

关键词： Graphs algorithms exponential time algorithms Exact algorithms Vertex ordering problems

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for Edge Domination

引用

ALGORITHMICA 2012年第4期64卷 535-563页

作者： van Rooij, Johan M. M. Bodlaender, Hans L. Univ Utrecht Inst Informat & Comp Sci NL-3508 TB Utrecht Netherlands

An edge dominating set in a graph G=(V,E) is a subset of the edges DaS dagger E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is NP-hard. We present a faster exact exponential time algorithm for this problem. Our algorithm uses O(1.3226 (n) ) time and polynomial space. The algorithm combines an enumeration approach of minimal vertex covers in the input graph with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwisely. In each of these refinement steps, the worst cases in the measure and conquer analysis of the current algorithm are reconsidered and a new branching strategy is proposed on one of these worst cases. In this way a series of algorithms appears, each one slightly faster than the previous one, ending in the O(1.3226 (n) ) time algorithm. For each algorithm in the series, we also give a lower bound on its running time. We also show that the related problems: minimum weight edge dominating set, minimum maximal matching and minimum weight maximal matching can be solved in O(1.3226 (n) ) time and polynomial space using modifications of the algorithm for edge dominating set. In addition, we consider the matrix dominating set problem which we solve in O(1.3226 (n+m) ) time and polynomial space for nxm matrices, and the parametrised minimum weight maximal matching problem for which we obtain an O (au)(2.4179 (k) ) time and space algorithm.

关键词： Edge dominating set Minimum maximal matching Exact algorithms exponential time algorithms Measure and conquer

来源：评论

学校读者我要写书评

暂无评论

algorithms for dominating clique problems

引用

THEORETICAL COMPUTER SCIENCE 2012年 459卷 77-88页

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

We handle in this paper three dominating clique problems, namely, the decision problem to detect whether a graph has a dominating clique and two optimization versions asking to compute a maximum- and a minimum-size dominating clique of a graph G, if G has a dominating clique. For the three problems we propose exact moderately exponential algorithms with worst-case running time upper bounds improving those by Kratsch and Liedloff [D. Kratsch, M. Liedloff, An exact algorithm for the minimum dominating clique problem, Theoret. Comput. Sci. 385 (1-3) (2007) 226-240]. We then study the three problems in sparse and dense graphs also providing improved running time upper bounds. Finally, we propose some exponential time approximation algorithms for the optimization versions. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Dominating clique exponential time algorithms Exact and approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Iterative compression and exact algorithms

引用

THEORETICAL COMPUTER SCIENCE 2010年第7-9期411卷 1045-1053页

作者： Fomin, Fedor V. Gaspers, Serge Kratsch, Dieter Liedloff, Mathieu Saurabh, Saket Univ Orleans Lab Informat Fondamentale Orleans F-45067 Orleans 2 France Univ Bergen Dept Informat N-5020 Bergen Norway Univ Chile Ctr Modelamiento Matemat Santiago 8370459 Chile Univ Paul Verlaine Metz Lab Informat Theor & Appl F-57045 Metz 01 France CIT Campus Inst Math Sci Madras 600113 Tamil Nadu India

Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the MAXIMUM INDEPENDENT SET problem, a parameterized and a counting version of d-HITTING SET and the MAXIMUM INDUCED CLUSTER SUBGRAPH problem. (C) 2009 Elsevier B.V. All rights reserved.

关键词： exponential time algorithms Graph algorithms Independent set Hitting set Induced cluster Fixed parameter algorithms Iterative compression

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for the general exact satisfiability problem

引用

THEORETICAL COMPUTER SCIENCE 2021年 889卷 60-84页

作者： Hoi, Gordon Stephan, Frank Natl Univ Singapore Sch Comp 13 Comp DrBlock COM1 Singapore 117417 Singapore Natl Univ Singapore Dept Math 10 Lower Kent Ridge RdBlock S17 Singapore 119076 Singapore Natl Univ Singapore Sch Comp 10 Lower Kent Ridge RdBlock S17 Singapore 119076 Singapore

The Exact Satisfiability problem asks if we can find a satisfying assignment to each clause such that exactly one literal in each clause is assigned 1, while the rest are all assigned 0. We can generalise this problem further by defining that a C-j clause is solved iff exactly j of the literals in the clause are 1 and all others are 0. We now introduce the family of Generalised Exact Satisfiability problems called GiXSAT as the problem to check whether a given instance consisting of C-j clauses with j is an element of{0, 1,..., i} for each clause has a satisfying assignment. In this paper, we present faster exact polynomial space algorithms, using a nonstandard measure, to solve GiXSAT, for i is an element of{2, 3, 4}, in O(1.3674(n)) time, O(1.5687(n)) time and O(1.6545(n)) time, respectively, using polynomial space, where nis the number of variables. This improves the current state of the art for polynomial space algorithms from O(1.4203(n)) time for G2XSAT by Zhou, Jiang and Y in and from O(1.6202(n)) time for G3XSAT by Dahllof and from O(1.6844(n)) time for G4XSAT which was by Dahllof as well. In addition, we present faster exact algorithms solving G2XSAT, G3XSAT and G4XSAT in O(1.3188(n)) time, O(1.3407(n)) time and O(1.3536(n)) time respectively at the expense of using exponential space. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Measure and conquer DPLL exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：