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

20th IEEE International Conference on Tools with Artificial Intelligence

作者： Segundo, Pablo San Tapia, Cristobal Puente, Julio Rodriguez-Losada, Diego Univ Politecn Madrid Intelligent Control Grp E-28040 Madrid Spain

ISBN: (纸本)9780769534404

This paper presents two new exact general purpose bit-parallel algorithms (BB-SAT and BBP-SAT) for the Boolean satisfiability problem (SAT). Based on the authors' recent successful bit-parallel algorithm for the maximum clique problem, the SAT formula is first reduced to a directed graph which is then bit encoded As a result, search traverses a bit vector graph space. At present the encoding allows for an efficient bitwise computation of graph state transitions as well as unit clause and pure literal evaluation. Experiments carried out on a number of DIAMCS instances are highly encouraging since BBP-SAT is already reasonably competitive employing just basic DPLL tactics with minor refinements. BBP-SAT is afresh approach in an otherwise mature domain. Further additional bit encoded knowledge of the more recent successful SAT algorithms (e.g. bit parallel heuristic variable selection) should make BBP-SAT a competitive general purpose solver.

关键词： SAT bit vector bit-parallelism exact algorithms directed graphs Boolean satisfiability

来源：评论

学校读者我要写书评

暂无评论

Enumerate and expand:: Improved algorithms for connected Vertex Cover and Tree Cover

Enumerate and expand:: Improved algorithms for connected Ver...

引用

International Computer Science Symposium in Russia (CSR 2006)

作者： Moelle, Daniel Richter, Stefan Rossmanith, Peter Univ Aachen Rhein Westfal TH Aachen Dept Comp Sci D-5100 Aachen Germany

ISBN: (纸本)3540341668

We present a new method of solving graph problems related to VERTEX COVER by enumerating and expanding appropriate sets of nodes. As an application, we obtain dramatically improved runtime bounds for two variants of the VERTEX COVER problem. In the case of CONNECTED VERTEX COVER, we take the upper bound from O*(6k) to O*(2.7606(k)) without large hidden factors. For TREE COVER, we show a complexity of O*(3.2361(k)), improving over the previous bound of O*((2k)(k)). In the process, faster algorithms for solving subclasses of the Steiner tree problem on graphs are investigated.

关键词： exact algorithms parameterized complexity enumerate and expand Vertex cover

来源：评论

学校读者我要写书评

暂无评论

An improved exact algorithm for the domatic number problem

引用

INFORMATION PROCESSING LETTERS 2007年第3期101卷 101-106页

作者： Riege, Tobias Rothe, Joerg Spakowski, Holger Yamamoto, Masaki Univ Dusseldorf Inst Informat D-4000 Dusseldorf Germany Tokyo Inst Technol Dept Math & Comp Sci Tokyo 152 Japan

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695(n) (up to polynomial factors) and in polynomial space. This result improves the previous bound of 2.8805(n), which is due to Bjorklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta (G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta (G) >= 5. Our new randomized algorithm employs Schoning's approach to constraint satisfaction problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： graph algorithms exact algorithms randomized algorithms domatic number problem

来源：评论

学校读者我要写书评

暂无评论

An exact approach for the vehicle routing problem with two-dimensional loading constraints

引用

TRANSPORTATION SCIENCE 2007年第2期41卷 253-264页

作者： Iori, Manuel Salazar-Gonzalez, Juan-Jose Vigo, Daniele Univ Bologna DEIS I-40136 Bologna Italy Univ Laguna DEIOC San Cristobal la Laguna 38271 Spain

W e consider a special case of the symmetric capacitated vehicle routing problem, in which a fleet of K identical vehicles must serve n customers, each with a given demand consisting in a set of rectangular two-dimensional weighted items. The vehicles have a two-dimensional loading surface and a maximum weight capacity. The aim is to find a partition of the customers into routes of minimum total cost such that, for each vehicle, the weight capacity is taken into account and a feasible two-dimensional allocation of the items into the loading surface exists. The problem has several practical applications in freight transportation, and it is NP-hard in the strong sense. We propose an exact approach, based on a branch-and-cut algorithm, for the minimization of the routing cost that iteratively calls a branch-and-bound algorithm for checking the feasibility of the loadings. Heuristics are also used to improve the overall performance of the algorithm. The effectiveness of the approach is shown by means of computational results.

关键词： vehicle routing packing exact algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 algorithms for unconstrained three-dimensional cutting problems: a comparative study

引用

COMPUTERS & OPERATIONS RESEARCH 2004年第5期31卷 657-674页

作者： Hifi, M Univ Picardie Lab Rech Informat Amiens LaRIA F-80000 Amiens France

In this paper we propose two exact algorithms for solving the three-dimensional cutting (3DC) problem. We study the two cases of the unconstrained 3DC problem: (i) only one large pallet is considered, denoted U_3DC, and (ii) the general version, denoted U_G3DC, in which different large pallets are considered. For both cases of the problem, we consider that there is unlimited quantity of each type of pieces to cut, and that all cuts are of guillotine type. We propose a first exact algorithm for the U_3DC problem. The algorithm is an adaptation of Gilmore and Gomory's approach (Oper. Res. 14 (1966) 1045) initially proposed for solving the unconstrained two-dimensional guillotine cutting problem. We then present a second algorithm for the same problem. This algorithm is mainly based upon a graph search procedure using a depth-first search strategy. This algorithm is a straightforward extension of the two-dimensional guillotine cutting approach proposed in (Eur. J. Oper. Res. 91 (1996) 553). We later show how we can extend the dynamic programming based algorithm for exactly solving the U_G3DC problem. Finally, we undertake an extensive experimental study with a large number of problem instances extracted from the literature and compare the performances of both algorithms.

关键词： combinatorial optimization cutting problems exact algorithms knapsack function

来源：评论

学校读者我要写书评

暂无评论

An improved solution algorithm for the constrained shortest path problem

引用

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2007年第7期41卷 756-771页

作者： Santos, Luis Coutinho-Rodrigues, Joao Current, John R. Ohio State Univ Fisher Coll Business Dept Management Sci Columbus OH 43210 USA Super Inst Bissaya Barreto P-3040 Coimbra Portugal Univ Coimbra Fac Sci & Technol Dept Civil Engn P-3030 Coimbra Portugal

The shortest path problem is one of the classic network problems. The objective of this problem is to identify the least cost path through a network from a pre-determined starting node to a pre-determined terminus node. It has many practical applications and can be solved optimally via efficient algorithms. Numerous modifications of the problem exist. In general, these are more difficult to solve. One of these modified versions includes an additional constraint that establishes an upper limit on the sum of some other arc cost (e.g., travel time) for the path. In this paper, a new optimal algorithm for this constrained shortest path problem is introduced. Extensive computational tests are presented which compare the algorithm to the two most commonly used algorithms to solve it. The results indicate that the new algorithm can solve optimally very large problem instances and is generally superior to the previous ones in terms of solution time and computer memory requirements. This is particularly true for the problem instances that are most difficult to solve. That is, those on large networks and/or where the additional constraint is most constraining. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： network routing constrained shortest path problem exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithm 864: General and robot-packable variants of the three-dimensional bin packing problem

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2007年第1期33卷 7.1-7.12页

作者： Martello, Silvano Pisinger, David Vigo, Daniele Den Boef, Edgar Korst, Jan Univ Copenhagen DIKU DK-2100 Copenhagen Denmark Philips Res Labs Eindhoven NL-5656 AA Eindhoven Netherlands

We consider the problem of orthogonally packing a given set of rectangular-shaped boxes into the minimum number of three-dimensional rectangular bins. The problem is NP-hard in the strong sense and extremely difficult to solve in practice. We characterize relevant subclasses of packing and present an algorithm which is able to solve moderately large instances to optimality. Extensive computational experiments compare the algorithm for the three-dimensional bin packing when solving general orthogonal packings and when restricted to robot packings.

关键词： algorithms experimentation bin packing exact algorithms constraint programming branch-and-bound

来源：评论

学校读者我要写书评

暂无评论

Fast and practical algorithms for planted (l, d) motif search

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2007年第4期4卷 544-552页

作者： Davila, Jaime Balla, Sudha Rajasekaran, Sanguthevar Univ Connecticut Dept Comp Sci & Engn Storrs CT 06269 USA

We consider the planted (l,d) motif search problem, which consists of finding a substring of length l that occurs in a set of input sequences {s(1),...,s(n)} with up to d errors, a problem that arises from the need to find transcription factor-binding sites in genomic information. We propose a sequence of practical algorithms, which start based on the ideas considered in PMS1. These algorithms are exact, have little space requirements, and are able to tackle challenging instances with bigger d, taking less time in the instances reported solved by exact algorithms. In particular, one of the proposed algorithms, PMSprune, is able to solve the challenging instances, such as (17, 6) and (19, 7), which were not previously reported as solved in the literature.

关键词： planted motif search problem challenging instances exact algorithms branch and bound algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：