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

20th International Conference on Computing and Combinatorics (COCOON)

作者： Jiang, Minghui Wang, Haitao Utah State Univ Dept Comp Sci Logan UT 84322 USA

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 = 1. We also obtain some interesting results for the general problem SCSI-t. From the negati... 详细信息

ISBN: (纸本)9783319087825

Given a set of n points on a line, where each point has one of k colors, and given an integer si >= 1 for each color i, 1 <= i <= k, the problem SHORTEST COLOR-SPANNING t INTERVALS (SCSI-t) aims at finding t intervals to cover at least si points of each color i, such that the maximum length of the intervals is minimized. Chen and Misiolek introduced the problem SCSI-1, and presented an algorithm running in O(n) time if the input points are sorted. Khanteimouri et al. gave an O (n(2) logn) time algorithm for the special case of SCSI-2 with s(i) = 1 for all colors i. In this paper, we present an improved algorithm with running time of 0(n2) for SCSI-2 with arbitrary si >= 1. We also obtain some interesting results for the general problem SCSI-t. From the negative direction, we show that approximating SCSI-t within any ratio is NP-hard when t is part of the input, is W[2]-hard when t is the parameter, and is W[1]-hard with both t and k as parameters. Moreover, the NP-hardness and the W[2]-hardness with parameter t hold even if si = 1 for all i. From the positive direction, we show that SCSI-t with si = 1 for all i is fixed-parameter tractable with k as the parameter, and admits an exact algorithm running in 0 (2(k)n . max{k, logn}) time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Color-spanning objects Computational geometry exact algorithms Parameterized complexity

来源：评论

学校读者我要写书评

暂无评论

On the Power of Simple Reductions for the Maximum Independent Set Problem 22nd

On the Power of Simple Reductions for the Maximum Independen...

引用

22nd International Computing and Combinatorics Conference (COCOON)

作者： Strash, Darren Karlsruhe Inst Technol Inst Theoret Informat Karlsruhe Germany

ISBN: (纸本)9783319426341;9783319426334

Reductions-rules that reduce input size while maintaining the ability to compute an optimal solution-are critical for developing efficient maximum independent set algorithms in both theory and practice. While several simple reductions have previously been shown to make small domain-specific instances tractable in practice, it was only recently shown that advanced reductions (in a measure-and-conquer approach) can be used to solve real-world networks on millions of vertices [Akiba and Iwata, TCS 2016]. In this paper we compare these state-of-the-art reductions against a small suite of simple reductions, and come to two conclusions: just two simple reductions-vertex folding and isolated vertex removal are sufficient for many real-world instances, and further, the power of the advanced rules comes largely from their initial application (i.e., kernelization), and not their repeated application during branch-and-bound. As a part of our comparison, we give the first experimental evaluation of a reduction based on maximum critical independent sets, and show it is highly effective in practice for medium-sized networks.

关键词： Maximum independent set Minimum vertex cover Kernelization Reductions exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Faster exact and Parameterized Algorithm for Feedback Vertex Set in Tournaments 33

Faster Exact and Parameterized Algorithm for Feedback Vertex...

引用

33rd Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Kumar, Mithilesh Lokshtanov, Daniel Univ Bergen Dept Informat Bergen Norway

ISBN: (纸本)9783959770019

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. In this article we consider the FEEDBACK VERTEX SET problem in tournaments. Here the input is a tournament T and an integer k, and the task is to determine whether T has a feedback vertex set of size at most k. We give a new algorithm for FEEDBACK VERTEX SET IN TOURNAMENTS. The running time of our algorithm is upper-bounded by O(1.6181(k) + n(O(1))) and by O(1.466(n)). Thus our algorithm simultaneously improves over the fastest known parameterized algorithm for the problem by Dom et al. running in time O(2(k)k(O(1)) + n(O(1))), and the fastest known exact exponential-time algorithm by Gaspers and Mnich with running time O(1.674(n)). On the way to proving our main result we prove a strengthening of a special case of a graph partitioning theorem due to Bollobas and Scott. In particular we show that the vertices of any undirected m-edge graph of maximum degree d can be colored white or black in such a way that for each of the two colors, the number of edges with both endpoints of that color is between m/4 - d/2 and m/4+d/2.

关键词： Parameterized algorithms exact algorithms Feedback vertex set Tournaments Graph partitions

来源：评论

学校读者我要写书评

暂无评论

Foundational factorization algorithms for the efficient roundoff-error-free solution of optimization problems

Foundational factorization algorithms for the efficient roun...

引用

作者： Escobedo, Adolfo Raphael Texas A&M University

学位级别：Ph.D.

LU and Cholesky factorizations play a central role in solving linear and mixed-integer programs. In many documented cases, the round-off errors accrued during the construction and implementation of these factorizations cause the misclassification of suboptimal solutions as optimal and infeasible problems as feasible and vice versa. Such erroneous outputs bring the reliability of optimization solvers into question and, therefore, it is imperative to eliminate these round off errors altogether and to do so efficiently to ensure practicality. Firstly, this work introduces two round off-error-free factorizations (REF) constructed exclusively in integer arithmetic: the REF LU and Cholesky factorizations. Additionally, it develops supplementary integer-preserving substitution algorithms, thereby providing a complete tool set for solving systems of linear equations (SLEs) exactly and efficiently. An inherent property of the REF factorization algorithms is that their entries' bit-length— i.e., the number of bits required for expression— is bounded polynomially. Unlike the exact rational arithmetic methods used in practice, however, the algorithms herein presented do not require any greatest common divisor operations to guarantee this pivotal property. Secondly, this work derives various useful theoretical results and details computational tests to demonstrate that the REF factorization framework is considerably superior to the rational arithmetic LU factorization approach in computational performance and storage requirements. This is significant because the latter approach is the solution validation tool of choice of state-of-the-art exact linear programming solvers due to its ability to handle both numerically difficult and intricate problems. An additional theoretical contribution and further computational tests also demonstrate the predominance of the featured framework over Q-matrices, which comprise an alternative integer-preserving approach relying on the basis adjunc

关键词： exact mathematical programming exact algorithms matrix factorizations roundoff errors solving linear systems factorization update algorithms. Thesis

来源：评论

学校读者我要写书评

暂无评论

Computing Tree-Depth Faster Than 2ⁿ

引用

ALGORITHMICA 2015年第1期73卷 202-216页

作者： Fomin, Fedor V. Giannopoulou, Archontia C. Pilipczuk, Michal Univ Bergen Dept Informat N-5020 Bergen Norway

A connected graph has tree-depth at most if it is a subgraph of the closure of a rooted tree whose height is at most . We give an algorithm which for a given -vertex graph , in time computes the tree-depth of . Our al... 详细信息

关键词： exact algorithms Tree-depth 2(n) Barrier

来源：评论

学校读者我要写书评

暂无评论

On soft predicates in subdivision motion planning

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2015年第8期48卷 589-605页

作者： Wang, Cong Chiang, Yi-Jen Yap, Chee NYU Polytech Sch Engn Dept Comp Sci & Engn Brooklyn NY 11201 USA NYU Dept Comp Sci New York NY USA

We propose to design new algorithms for motion planning problems using the well-known Domain Subdivision paradigm, coupled with "soft" predicates. Unlike the traditional exact predicates in computational geometry, our primitives are only exact in the limit. We introduce the notion of resolution-exact algorithms in motion planning: such an algorithm has an "accuracy" constant K > 1, and takes an arbitrary input "resolution" parameter epsilon > 0 such that: if there is a path with clearance K epsilon, it will output a path with clearance epsilon/K;if there are no paths with clearance epsilon/K, it reports "NO PATH". Besides the focus on soft predicates, our framework also admits a variety of global search strategies including forms of the A* search and probabilistic search. Our algorithms are theoretically sound, practical, easy to implement, without implementation gaps, and have adaptive complexity. Our deterministic and probabilistic strategies avoid the Halting Problem of current probabilistically complete algorithms. We develop the first provably resolution-exact algorithms for motion-planning problems in SE(2) = R-2 x S-1. To validate this approach, we implement our algorithms and the experiments demonstrate the efficiency of our approach, even compared to probabilistic algorithms. (C) 2015 Elsevier B.V. All rights reserved.

关键词： exact algorithms Subdivision algorithms Motion planning Soft predicates Resolution-exact algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Some Reduction Procedure for Computing Pathwidth of Undirected Graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2015年第3期E98D卷 503-511页

作者： Ikeda, Masataka Nagamochi, Hiroshi Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan

Computing an invariant of a graph such as treewidth and pathwidth is one of the fundamental problems in graph algorithms. In general, determining the pathwidth of a graph is NP-hard. In this paper, we propose several reduction methods for decreasing the instance size without changing the pathwidth, and implemented the methods together with an exact algorithm for computing pathwidth of graphs. Our experimental results show that the number of vertices in all chemical graphs in NCI database decreases by our reduction methods by 53.81% in average.

关键词： pathwidth exact algorithms graphs chemical graphs

来源：评论

学校读者我要写书评

暂无评论

The production routing problem: A review of formulations and solution algorithms

引用

COMPUTERS & OPERATIONS RESEARCH 2015年 55卷 141-152页

作者： Adulyasak, Yossiri Cordeau, Jean-Francois Jans, Raf HEC Montreal Montreal PQ H3T 2A7 Canada CIRRELT Montreal PQ H3T 2A7 Canada

The production routing problem (PRP) combines the lot-sizing problem and the vehicle routing problem, two classical problems that have been extensively studied for more than half a century. The PRP is solved in an attempt to jointly optimize production, inventory, distribution and routing decisions and is thus a generalization of the inventory routing problem (IRP). Although the PRP has a complicated structure, there has been a growing interest in this problem during the past decade in both academia and industry. This article provides a comprehensive review of various solution techniques that have been proposed to solve the PRP. We attempt to provide an in-depth summary and discussion of different formulation schemes and of algorithmic and computational issues. Finally, we point out interesting research directions for further developments in production routing. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： Integrated supply chain planning Production routing Inventory routing exact algorithms Heuristics Review

来源：评论

学校读者我要写书评

暂无评论

Roundoff-Error-Free algorithms for Solving Linear Systems via Cholesky and LU Factorizations

引用

INFORMS JOURNAL ON COMPUTING 2015年第4期27卷 677-689页

作者： Escobedo, Adolfo R. Moreno-Centeno, Erick Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA

LU and Cholesky factorizations are computational tools for efficiently solving linear systems that play a central role in solving linear programs and several other classes of mathematical programs. In many documented cases, however, the roundoff errors accrued during the construction and implementation of these factorizations lead to the misclassification of feasible problems as infeasible and vice versa. Hence, reducing these roundoff errors or eliminating them altogether is imperative to guarantee the correctness of the solutions provided by optimization solvers. To achieve this goal without having to use rational arithmetic, we introduce two roundoff-error-free factorizations that require storing the same number of individual elements and performing a similar number of operations as the traditional LU and Cholesky factorizations. Additionally, we present supplementary roundoff-error-free forward and backward substitution algorithms, thereby providing a complete tool set for solving systems of linear equations exactly and efficiently. An important property shared by the featured factorizations and substitution algorithms is that their individual coefficients' maximum word length-i.e., the maximum number of digits required for expression-is bounded polynomially. Unlike the rational arithmetic methods used in practice to solve linear systems exactly, however, the algorithms herein presented do not require any gcd calculations to bound the entries' word length. We also derive various other related theoretical results, including the total computational complexity of all the roundoff-error-free processes herein presented.

关键词： exact mathematical programming exact algorithms matrix factorizations roundoff errors solving linear systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：