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

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

来源：评论

学校读者我要写书评

暂无评论

Faster Graph Coloring in Polynomial Space

引用

ALGORITHMICA 2023年第2期85卷 584-609页

作者： Gaspers, Serge Lee, Edward J. UNSW Sydney Sydney NSW Australia

We present a polynomial-space algorithm that computes the number of independent sets of any input graph in time O(1.1389(n)) for graphs with maximum degree 3 and in time O(1.2356(n)) for general graphs, where n is the number of vertices in the input graph. Together with the inclusion-exclusion approach of Bjorklund, Husfeldt, and Koivisto [SIAM J. Comput. 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time O(2.2356(n)) as well as an exponential-space O(1.2330(n)) time algorithm for counting independent sets. Our main algorithm counts independent sets in graphs with maximum degree at most 3 and no vertex with three neighbors of degree 3. This polynomial-space algorithm is designed and analyzed using the recently introduced Separate, Measure and Conquer approach [Gaspers & Sorkin, ICALP 2015]. Using Wahlstrom's compound measure approach, this improvement in running time for small degree graphs is then bootstrapped to larger degrees, giving the improvement for general graphs. Combining both approaches leads to some inflexibility in choosing vertices to branch on for the small-degree cases, which we counter by structural graph properties.

关键词： Graph coloring exponential time algorithms Analysis of algorithms Branching algorithms Counting independent sets

来源：评论

学校读者我要写书评

暂无评论

A Bisection Approach to Subcubic Maximum Induced Matching 1

引用

18th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Hoi, Gordon Jain, Sanjay Sabili, Ammar Fathin Stephan, Frank Temasek Polytech Sch Informat & IT 21 Tampines Ave 1 Singapore 529757 Singapore Natl Univ Singapore Sch Comp 13 Comp Dr Singapore 117417 Singapore Natl Univ Singapore Dept Math 10 Lower Kent Ridge Rd Singapore 119076 Singapore

ISBN: (数字)9789819705665

ISBN: (纸本)9789819705658;9789819705665

In this paper, we present a faster exact algorithm which solves the Maximum Induced Matching problem for subcubic graphs. Here let n be the overall number of vertices and k be the number of those vertices of degree 3 where all neighbours have also at least degree 2. Then the runtime is at most O(1.2335(k)) center dot Poly(n), giving an FPT bound for the time used by the algorithm;the algorithm uses the result of Monien and Preis combined with a bound obtained by applying the measure and conquer technique where the number k replaces n as the measure used;note that k <= n.

关键词： Branch and Bound exponential time algorithms Graph Theory Measure and Conquer Fixed Parameter Tractable Problems

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Bipartite TSP in O(1.9999ⁿ) time, Assuming Quadratic time Matrix Multiplication 52

Bipartite TSP in O(1.9999<SUP>n</SUP>) Time, Assuming Quadra...

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Nederlof, Jesper Univ Utrecht Utrecht Netherlands Eindhoven Univ Technol Eindhoven Netherlands

ISBN: (纸本)9781450369794

The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n(2)2(n)) time. Since then it has been a notorious problem to improve the runtime to O((2-epsilon)(n)) for some constant epsilon > 0. In this work we establish the following progress: If (sx s)-matrices can be multiplied in s(2+o(1)) time, than all instances of TSP in bipartite graphs can be solved in O(1.9999(n)) time by a randomized algorithm with constant error probability. We also indicate how our methods may be useful to solve TSP in non-bipartite graphs. On a high level, our approach is via a new problem called MINHAMPAIR: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MINHAMPAIR based on a new sparse cut-based factorization of the 'matchings connectivity matrix', introduced by Cygan et al. [JACM'18].

关键词： Traveling Salesman Problem exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication 2020

Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time m...

引用

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

作者： Jesper Nederlof Utrecht University Netherlands

ISBN: (纸本)9781450369794

The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n 22 n ) time. Since then it has been a notorious problem to improve the runtime to O((2−є) n ) for some constant є>0. In this work we establish the following progress: If (s× s)-matrices can be multiplied in s 2+o(1) time, than all instances of TSP in bipartite graphs can be solved in O(1.9999 n ) time by a randomized algorithm with constant error probability. We also indicate how our methods may be useful to solve TSP in non-bipartite graphs. On a high level, our approach is via a new problem called MinHamPair: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MinHamPair based on a new sparse cut-based factorization of the ‘matchings connectivity matrix’, introduced by Cygan et al. [JACM’18].

关键词： exponential time algorithms Traveling Salesman Problem

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

FASTER SPACE-EFFICIENT algorithms FOR SUBSET SUM, k-SUM, AND RELATED PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2018年第5期47卷 1755-1777页

作者： Bansal, Nikhil Garg, Shashwat Nederlof, Jesper Vyas, Nikhil Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 AB Eindhoven Netherlands MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA

We present randomized algorithms that solve subset sum and knapsack instances with n items in O*((20.86n)) time, where the O* (.) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve binary integer programming on n variables with few constraints in a similar running time. We also show that for any constant k >= 2, random instances of k-sum can be solved using O(n(k-0.5) polylog(n)) time and O(log n) space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(log n) space significantly faster than the trivial O(n(2)) time algorithm if no value occurs too often in the same list.

关键词： space-efficient algorithms k-sum subset sum exact exponential time algorithms fine-grained complexity space-time trade-off exponential time algorithms

来源：评论

学校读者我要写书评

暂无评论

Simple Paths and Cycles Avoiding Forbidden Paths 44th

Simple Paths and Cycles Avoiding Forbidden Paths

引用

44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)

作者： Momege, Benjamin Inria Lille Nord Europe Villeneuve Dascq France

ISBN: (纸本)9783319731179;9783319731162

A graph with forbidden paths is a pair (G, F) where G is a graph and F is a subset of the set of paths in G. A simple path avoiding forbidden paths in (G, F) is a simple path in G such that each subpath is not in F. It is shown in [S. Szeider, Finding paths in graphs avoiding forbidden transitions, DAM 126] that the problem of deciding the existence of a simple path avoiding forbidden paths in a graph with forbidden paths is Np-complete even when the forbidden paths are restricted to be transitions, i.e., of length two. We give an exact exponential time algorithm that decides in O(2(n)n(2k+O(1))) time and O(n(k+O(1))) space whether there exists a simple path between two vertices of a given n-vertex graph where k is the length of the longest forbidden path. We also obtain an exact O(2(n) n(2k+O(1))) time and O(n(k+O(1))) space algorithm to check the existence of a Hamiltonian path avoiding forbidden paths and for the graphs with forbidden transitions an exact O * (2(n)) time and polynomial space algorithm to check the existence of a Hamiltonian cycle avoiding forbidden transitions. In the last section, we present a new sufficient condition for graphs to have a Hamiltonian cycle, which gives us some interesting corollaries for graphs with forbidden paths.

关键词： exponential time algorithms Exact algorithms Graph algorithms Forbidden paths Hamiltonian cycles

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：