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

Linear-programming design and analysis of fast algorithms for Max 2-CSP

DISCRETE OPTIMIZATION 2007年第3-4期4卷 260-287页

作者： Scott, Alexander D. Sorkin, Gregory B. IBM Corp Thomas J Watson Res Ctr Dept Math Sci Yorktown Hts NY 10598 USA Univ Oxford Inst Math Oxford OX1 3LB England

The class Max (r, 2)-CSP, or simply Max 2-CSP, consists of constraint satisfaction problems with at most two r-valued variables per clause. For instances with n variables and m binary clauses, we present an O(nr(5+19m/100))-time algorithm which is the fastest polynomial-space algorithm for many problems in the class, including Max Cut. The method also proves a treewidth bound tw(G) <= (13/75 + o(1))m, which gives a faster Max 2-CSP algorithm that uses exponential space: running in time O*(2((13/75+o(1))m)), this is fastest for most problems in Max 2-CSP. Parametrizing in terms of n rather than m, for graphs of average degree d we show a simple algorithm running time a*(2((1-2/d+1)n)), the fastest polynomial-space algorithm known. In combination with "Polynomial CSPs" introduced in a companion paper, these algorithms also allow (with an additional polynomial factor overhead in space and time) counting and sampling, and the solution of problems like Max Bisection that escape the usual CSP framework. Linear programming is key to the design as well as the analysis of the algorithms. (c) 2007 Elsevier B.V. All rights reserved.

关键词： max cut max 2-Sat max 2-CSP exact algorithms linear-programming duality measure and conquer

来源：评论

学校读者我要写书评

暂无评论

Designing and constructing networks under uncertainty in the construction stage: Definition and exact algorithmic approach

引用

COMPUTERS & OPERATIONS RESEARCH 2017年 81卷 178-191页

作者： Alvarez-Miranda, Eduardo Pereira, Jordi Univ Talca Dept Ind Engn Curico Chile Univ Adolfo Ibanez Dept Sci & Engn Vina Del Mar Chile

The present work proposes a novel Network Optimization problem whose core is to combine both network design and network construction scheduling under uncertainty into a single two-stage robust optimization model. The first-stage decisions correspond to those of a classical network design problem, while the second-stage decisions correspond to those of a network construction scheduling problem (NCS) under uncertainty. The resulting problem, which we will refer to as the Two-Stage Robust Network Design and Construction Problem (2SRNDC), aims at providing a modeling framework in which the design decision not only depends on the design costs (e.g., distances) but also on the corresponding construction plan (e.g., time to provide service to costumers). We provide motivations, mixed integer programming formulations, and an exact algorithm for the 2SRNDC. Experimental results on a large set of instances show the effectiveness of the model in providing robust solutions, and the capability of the proposed algorithm to provide good solutions in reasonable running times. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Network design Network construction Two-stage robust optimization exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Interval scheduling: A survey

引用

NAVAL RESEARCH LOGISTICS 2007年第5期54卷 530-543页

作者： Kolen, Antoon W. J. Lenstra, Jan Karel Papadimitriou, Christos H. Spieksma, Frits C. R. Katholieke Univ Leuven Dept Operat Res & Business Stat B-3000 Louvain Belgium Maastricht Univ Dept Quantitat Econ NL-6200 MD Maastricht Netherlands Ctr Math & Comp Sci NL-1090 GB Amsterdam Netherlands Univ Calif Berkeley Div Comp Sci Berkeley CA 94720 USA

In interval scheduling, not only the processing times of the jobs but also their starting times are given. This article surveys the area of interval scheduling and presents proofs of results that have been known within the community for some time. We first review the complexity and approximability of different variants of interval scheduling problems. Next, we motivate the relevance of interval scheduling problems by providing an overview of applications that have appeared in literature. Finally, we focus on algorithmic results for two important variants of interval scheduling problems. In one variant we deal with nonidentical machines: instead of each machine being continuously available, there is a given interval for each machine in which it is available. In another variant, the machines are continuously available but they are ordered, and each job has a given "maximal" machine on which it can be processed. We investigate the complexity of these problems and describe algorithms for their solution. (c) 2007 Wiley Periodicals, Inc.

关键词： analysis of algorithms computational complexity exact algorithms production/scheduling sequencing deterministic interval scheduling

来源：评论

学校读者我要写书评

暂无评论

exact quantum Fourier transforms and discrete logarithm algorithms

引用

INTERNATIONAL JOURNAL OF QUANTUM INFORMATION 2004年第1期2卷 91-100页

作者： Mosca, M Zalka, C Univ Waterloo Dept Phys Waterloo ON N2L 3G1 Canada Univ Waterloo Dept Combinator & Optimizat Waterloo ON N2L 3G1 Canada

We show how the Quantum Fast Fourier Transform (QFFT) can be made exact for arbitrary orders (first showing it for large primes). Most quantum algorithms only need a good approximation of the quantum Fourier transform of order 2(n) to succeed with high probability, and this QFFT can in fact be done exactly. Kitaev(1) showed how to approximate the Fourier transform for any order. Here we show how his construction can be made exact by using the technique known as "amplitude amplification". Although unlikely to be of any practical use, this construction allows one to make Shor's discrete logarithm quantum algorithm exact. Thus we have the first example of an exact non black box fast quantum algorithm, thereby giving more evidence that "quantum" need not be probabilistic. We also show that in a certain sense the family of circuits for the exact QFFT is uniform. Namely, the parameters of the gates can be approximated efficiently.

关键词： quantum algorithms exact algorithms quantum Fourier transformation discrete logarithm problem

来源：评论

学校读者我要写书评

暂无评论

Formulation of four Katsevich algorithms in native geometry

引用

IEEE TRANSACTIONS ON MEDICAL IMAGING 2006年第7期25卷 855-868页

作者： Katsevich, Alexander Taguchi, Katsuyuki Zamyatin, Alexander A. Univ Cent Florida Dept Math Orlando FL 32816 USA

We derive formulations of the four exact helical Katsevich algorithms in the native cylindrical detector geometry, which allow efficient implementation in modern computed tomography scanners with wide cone beam apertu... 详细信息

关键词： computed tomography (CT) cone beam reconstruction exact algorithms shift-invariant filtering

来源：评论

学校读者我要写书评

暂无评论

Counting models for 2_SAT and 3_SAT formulae

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期332卷 265-291页

作者： Dahllöf, V Jonsson, P Wahström, M Linkoping Univ Dept Comp & Informat Sci SE-58183 Linkoping Sweden

We here present algorithms for counting models and max-weight models for 2SAT and 3SAT formulae. They use polynomial space and run in O(1.2561(n)) and O(1.6737(n)) time, respectively, where n is the number of variables. This is faster than the previously best algorithms for counting nonweighted models for 2SAT and 3SAT, which run in O(1.3247(n)) and O(1.6894(n)) time, respectively. In order to prove these time bounds, we develop new measures of formula complexity, allowing us to conveniently analyze the effects of certain factors with a large impact on the total running time. We also provide an algorithm for the restricted case of separable 2SAT formulae, with fast running times for well-studied input classes. For all three algorithms we present interesting applications, such as computing the permanent of sparse 0/1 matrices. (c) 2004 Elsevier B.V. All rights reserved.

关键词： counting models satisfiability exponential-time algorithms exact algorithms upper bounds

来源：评论

学校读者我要写书评

暂无评论

Speeding Up Dynamic Programming with Representative Sets: An Experimental Evaluation of algorithms for Steiner Tree on Tree Decompositions

引用

ALGORITHMICA 2015年第3期71卷 636-660页

作者： Fafianie, Stefan Bodlaender, Hans L. Nederlof, Jesper Univ Utrecht Utrecht Netherlands

Dynamic programming on tree decompositions is a frequently used approach to solve otherwise intractable problems on instances of small treewidth. In recent work by Bodlaender et al. (Proceedings of the 40th international colloquium on automata, languages and programming, ICALP 2013, part I, volume 7965 of Lecture Notes in Computer Science. Springer, Berlin, pp 196-207, 2013), it was shown that for many connectivity problems, there exist algorithms that use time linear in the number of vertices and single exponential in the width of the tree decomposition that is used. The central idea is that it suffices to compute representative sets, and that these can be computed efficiently with help of Gaussian elimination. In this paper, we give an experimental evaluation of this technique for the Steiner Tree problem. Our comparison of the classic dynamic programming algorithm and the improved dynamic programming algorithm that employs table reduction shows that the new approach gives significant improvements on the running time of the algorithm and the size of the tables computed by the dynamic programming algorithm. Thus, the rank-based approach from Bodlaender et al. (2013) does not only give significant theoretical improvements but also is a viable approach in a practical setting, and showcases the potential of exploiting the idea of representative sets for speeding up dynamic programming algorithms. Furthermore, we propose an alternative representation of partial solutions using weighted bit strings in order to circumvent a part of the reduction step that is computationally expensive in practice. In the experimental evaluation we find that this representation yields further significant improvements. We show that the representation can also be used for the other problems fitting in the framework of Bodlaender et al. (2013).

关键词： Experimental evaluation Algorithm engineering Steiner tree Treewidth Dynamic programming exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing Optimal Steiner Trees in Polynomial Space

引用

ALGORITHMICA 2013年第3期65卷 584-604页

作者： Fomin, Fedor V. Grandoni, Fabrizio Kratsch, Dieter Lokshtanov, Daniel Saurabh, Saket Univ Bergen Dept Informat N-5020 Bergen Norway Univ Italian Switzerland IDSIA CH-6928 Manno Switzerland Univ Paul Verlaine Metz LITA F-57045 Metz 01 France Inst Math Sci Madras 600113 Tamil Nadu India

Given an n-node edge-weighted graph and a subset of k terminal nodes, the NP-hard (weighted) Steiner tree problem is to compute a minimum-weight tree which spans the terminals. All the known algorithms for this problem which improve on trivial O(1.62 (n) )-time enumeration are based on dynamic programming, and require exponential space. Motivated by the fact that exponential-space algorithms are typically impractical, in this paper we address the problem of designing faster polynomial-space algorithms. Our first contribution is a simple O((27/4) (k) n (O(logk)))-time polynomial-space algorithm for the problem. This algorithm is based on a variant of the classical tree-separator theorem: every Steiner tree has a node whose removal partitions the tree in two forests, containing at most 2k/3 terminals each. Exploiting separators of logarithmic size which evenly partition the terminals, we are able to reduce the running time to . This improves on trivial enumeration for roughly k < n/3, which covers most of the cases of practical interest. Combining the latter algorithm (for small k) with trivial enumeration (for large k) we obtain a O(1.59 (n) )-time polynomial-space algorithm for the weighted Steiner tree problem. As a second contribution of this paper, we present a O(1.55 (n) )-time polynomial-space algorithm for the cardinality version of the problem, where all edge weights are one. This result is based on a improved branching strategy. The refined branching is based on a charging mechanism which shows that, for large values of k, convenient local configurations of terminals and non-terminals exist. The analysis of the algorithm relies on the Measure & Conquer approach: the non-standard measure used here is a linear combination of the number of nodes and number of non-terminals. Using a recent result in Nederlof (International colloquium on automata, languages and programming (ICALP), pp. 713-725, 2009), the running time can be reduced to O(1.36 (n) ). The previous

关键词： Steiner tree exact algorithms Space complexity

来源：评论

学校读者我要写书评

暂无评论

Fast algorithms for max independent set

引用

ALGORITHMICA 2012年第1-2期62卷 382-415页

作者： Bourgeois, Nicolas Escoffier, Bruno Paschos, Vangelis T. van Rooij, Johan M. M. Univ Paris 09 LAMSADE F-75775 Paris 16 France Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands

We first propose a method, called "bottom-up method" that, informally, "propagates" improvement of the worst-case complexity for "sparse" instances to "denser" ones and we show ... 详细信息

We first propose a method, called "bottom-up method" that, informally, "propagates" improvement of the worst-case complexity for "sparse" instances to "denser" ones and we show an easy though non-trivial application of it to the min set cover problem. We then tackle max independent set. Here, we propagate improvements of worst-case complexity from graphs of average degree d to graphs of average degree greater than d. Indeed, using algorithms for max independent set in graphs of average degree 3, we successively solve max independent set in graphs of average degree 4, 5 and 6. Then, we combine the bottom-up technique with measure and conquer techniques to get improved running times for graphs of maximum degree 5 and 6 but also for general graphs. The computation bounds obtained for max independent set are O (au)(1.1571 (n) ), O (au)(1.1895 (n) ) and O (au)(1.2050 (n) ), for graphs of maximum (or more generally average) degree 4, 5 and 6 respectively, and O (au)(1.2114 (n) ) for general graphs. These results improve upon the best known results for these cases for polynomial space algorithms.

关键词： Bottom-up method Max independent set exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Fixed-parameter algorithms for CLOSEST STRING and related problems

引用

ALGORITHMICA 2003年第1期37卷 25-42页

作者： Gramm, J Niedermeier, R Rossmanith, P Univ Tubingen Wilhelm Schickard Inst Informat D-72076 Tubingen Germany Rhein Westfal TH Aachen Lehrgebiet Theoret Informat D-52056 Aachen Germany

CLOSEST STRING is one of the core problems in the field of consensus word analysis with particular importance for computational biology. Given k strings of the same length and a nonnegative integer d, find a "center string" s such that none of the given strings has the Hamming distance greater than d from s. CLOSEST STRING is NP-complete. In biological applications, however, d is usually,very small. We show how to solve CLOSEST STRING in linear time for fixed d-the exponential growth in d is bounded by O(d(d)). We extend this result to the closely related problems d-MISMATCH and DISTINGUISHING STRING SELECTION. Moreover, we also show that CLOSEST STRING is solvable in linear time when k is fixed and d is arbitrary. In summary, this means that CLOSEST STRING is fixed-parameter tractable with respect to parameter d and with respect to parameter k. Finally, the practical usefulness of our findings is substantiated by some experimental results.

关键词： consensus word analysis NP-complete exact algorithms fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：