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

THEORETICAL COMPUTER SCIENCE 2010年第40-42期411卷 3701-3713页

作者： Cygan, Marek Pilipczuk, Marcin Univ Warsaw Dept Math Comp Sci & Mech PL-02097 Warsaw Poland

In this paper we gather several improvements in the field of exact and approximate exponential time algorithms for the BANDWIDTH problem. For graphs with treewidth t we present an O(n(0(t))2(n)) exact algorithm. Moreover, for any two positive integers k >= 2, r >= 1, we present a (2kr - 1)-approximation algorithm that solves BANDWIDTH for an arbitrary input graph in O*(k(n/(k-1)r)) time and polynomial space where by O* we denote the standard big O notation but omitting polynomial factors. Finally, we improve the currently best known exact algorithm for arbitrary graphs with an O(4.383(n)) time and space algorithm. In the algorithms for the small treewidth we develop a technique based on the Fast Fourier Transform, parallel to the Fast Subset Convolution techniques introduced by Bjorklund et al. This technique can be also used as a simple method of finding a chromatic number of all subgraphs of a given graph in O*(2(n)) time and space, what matches the best known results. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Bandwidth Exponential algorithm exact algorithm Approximate algorithm Graph

来源：评论

学校读者我要写书评

暂无评论

Computing minimum 2-edge-connected Steiner networks in the Euclidean plane

引用

NETWORKS 2019年第1期73卷 89-103页

作者： Brazil, Marcus Volz, Marcus Zachariasen, Martin Ras, Charl Thomas, Doreen Univ Melbourne Dept Elect & Elect Engn Melbourne Vic 3010 Australia Univ Melbourne Dept Mech Engn Melbourne Vic Australia Univ So Denmark Det Naturvidenskabelige Fak Odense Denmark Univ Melbourne Math & Stat Melbourne Vic Australia

We present a new exact algorithm for computing minimum 2-edge-connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2-edge-connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals-doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2-edge-connected Steiner network problem.

关键词： 2-connected Steiner networks 2-edge-connected networks computational geometry exact algorithm GeoSteiner Steiner trees

来源：评论

学校读者我要写书评

暂无评论

On parameterized intractability: Hardness and completeness

引用

COMPUTER JOURNAL 2008年第1期51卷 39-59页

作者： Chen, Jianer Meng, Jie Texas A&M Univ Dept Comp Sci College Stn TX 77843 USA

We study the theory and techniques developed in the research of parameterized intractability, emphasizing on parameterized hardness and completeness that imply (stronger) computational lower bounds for natural computational problems. Moreover, the fundamentals of the structural properties in parameterized complexity theory, relationships to classical complexity theory and more recent developments in the area are also introduced.

关键词： parameterized computation fixed parameter tractability W-hierarchy exact algorithm

来源：评论

学校读者我要写书评

暂无评论

The project scheduling problem with irregular starting time costs

引用

OPERATIONS RESEARCH LETTERS 1999年第4期25卷 175-182页

作者： Maniezzo, V Mingozzi, A Univ Bologna Dept Math I-47023 Cesena Italy

We consider the problem of scheduling a set of activities satisfying precedence constraints in order to minimize the sum of the costs associated with the starting times of the activities. We consider the case in which the activity starting time cost functions are irregular functions. This problem can be solved in polynomial time either when the precedence graph has a special structure or when the starting time cost function of each activity is monotonic. A (0-1) integer programming formulation of this problem is presented and used to derive valid lower bounds to the optimal solution cost. An exact branch-and-bound algorithm is described. Computational results show the effectiveness of the proposed exact algorithm in solving problems up to 100 activities. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： combinatorial optimization integer programming project scheduling exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Structural Properties of Minimum Multi-source Multi-Sink Steiner Networks in the Euclidean Plane

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2023年第3期197卷 1104-1139页

作者： Westcott, Alexander Brazil, Marcus Ras, Charl Univ Melbourne Sch Math & Stat Melbourne Australia Univ Melbourne Sch Engn Melbourne Australia

Given two finite sets A and B of points in the Euclidean plane, a minimum multi-source multi-sink Steiner network in the plane, or a minimum (A, B)-network, is a directed graph embedded in the plane with a dipath from every node in A to every node in B such that the total length of all arcs in the network is minimised. Such a network may contain Steiner points-nodes appearing in the solution that are neither in A nor B. We show that for any finite point sets A, B in the plane, there exists a minimum (A, B)-network that is constructible by straightedge and compass (this was claimed in a paper by Maxwell and Swanepoel, but their argument is incorrect). We use this property to formulate an algorithmic framework for exactly finding minimum (A, B)-networks in the Euclidean plane. We also present several new structural and geometric properties of minimum (A, B)-networks. In particular, we resolve a conjecture of Alfaro by proving that, for any terminal set A, adding an appropriate orientation to the edges of a minimum 2-edge-connected Steiner network on A yields a minimum (A, A)-network.

关键词： Directed Steiner networks Steiner trees exact algorithm Alfaro's conjecture Geometric networks

来源：评论

学校读者我要写书评

暂无评论

The three column Bandpass problem is solvable in linear time

引用

THEORETICAL COMPUTER SCIENCE 2011年第4-5期412卷 281-299页

作者： Li, Zhong Lin, Guohui Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

The general Bandpass problem is NP-hard and was claimed to be NP-hard when the number of columns is three. Previously we designed a polynomial time row-stacking algorithm for the three column case, to produce a solution that is at most 1 less than the optimum. We show in this paper that for any bandpass number B >= 2, an optimal solution is always achievable in linear time. (c) 2010 Elsevier B.V. All rights reserved.

关键词： Bandpass problem exact algorithm Polynomial time solvable

来源：评论

学校读者我要写书评

暂无评论

Improved fixed parameter tractable algorithms for two "edge" problems: MAXCUT and MAXDAG

引用

INFORMATION PROCESSING LETTERS 2007年第2期104卷 65-72页

作者： Raman, Venkatesh Saurabh, Saket Inst Math Sci Madras 600113 Tamil Nadu India

We give improved parameterized algorithms for two '' edge '' problems MAXCUT and MAXDAG, where the solution sought is a subset of edges. MAXCUT of a graph is a maximum set of edges forming a bipartite subgraph of the given graph. On the other hand, MAXDAG of a directed graph is a set of arcs of maximum size such that the graph induced on these arcs is acyclic. Our algorithms are obtained through new kernelization and efficient exact algorithms for the optimization versions of the problems. More precisely our results include: (i) a kernel with at most alpha k vertices and beta k edges for MAXCUT. Here 0 < alpha <=, 1 and 1 < beta <= 2. Values of alpha and beta depends on the number of vertices and the edges in the graph;(ii) a kernel with at most 4k/3 vertices and 2k edges for MAXDAG;(iii) an O-*(1.2418(k)) parameterized algorithm for MAXCUT in undirected graphs. This improves the O-*(1.4143(k))(1) algorithm presented in [E. Prieto, The method of extremal structure on the k-maximum cut problem, in: The Proceedings of Computing: The Australasian Theory Symposium (CATS), 2005, pp. 119-126];(iv) an O-*(2(k)) algorithm for optimization version of MAXDAG in directed graphs. This is the first such algorithm to the best of our knowledge;(v) an O-*(2(k)) parameterized algorithm for MAXDAG in directed graphs. This improves the previous best of O-*(4(k)) presented in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458];(vi) an O-*(16(k)) parameterized algorithm to determine whether an oriented graph having m arcs has an acyclic subgraph with at least m/2 + k arcs. This improves the O-*(2(k)) algorithm given in [V. Raman, S. Saurabh, Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (3) (2006) 446-458]. In addition, we show that if a directed graph has minimum out degree at least f (n) (some function of n) th

关键词： directed feedback arc set max-cut parameterized complexity exact algorithm graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A cut-and-solve algorithm for virtual machine consolidation problem

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2024年 154卷 359-372页

作者： Luo, Jiang-Yao Chen, Liang Chen, Wei-Kun Yuan, Jian-Hua Dai, Yu-Hong Beijing Univ Posts & Telecommun Sch Sci Beijing 100876 Peoples R China Chinese Acad Sci Acad Math & Syst Sci LSEC ICMSEC Beijing Peoples R China Beijing Inst Technol Sch Math & Stat Beijing Key Lab MCAACI Beijing 100081 Peoples R China Beijing Univ Posts & Telecommun Key Lab Math & Informat Networks Minist Educ Beijing 100876 Peoples R China

The virtual machine consolidation problem attempts to determine which servers to be activated, how to allocate virtual machines to the activated servers, and how to migrate virtual machines among servers such that the summation of activated, allocation, and migration costs is minimized subject to the resource constraints of the servers and other practical constraints. In this paper, we first propose a new mixed integer linear programming formulation for the virtual machine consolidation problem. We show that compared with existing formulations, the proposed formulation is much more compact in terms of smaller numbers of variables or constraints, which makes it suitable for solving large-scale problems. We then develop a cut-and-solve algorithm, a tree search algorithm to efficiently solve the virtual machine consolidation problem to optimality. The proposed cut-and-solve algorithm is based on a novel relaxation of the virtual machine consolidation problem that provides a stronger lower bound than the natural continuous relaxation of the virtual machine consolidation problem, making a smaller search tree. By extensive computational experiments, we show that (i) the proposed formulation significantly outperforms existing formulations in terms of solution efficiency;(ii) compared with standard mixed integer linear programming solvers, the proposed cut-and-solve algorithm is much more efficient;and (iii) compared with an existing heuristic algorithm, the proposed cut-and-solve algorithm is better able to balance workload distribution across servers and achieve higher resource utilization.

关键词： Cut-and-solve Cutting plane exact algorithm Mixed integer linear programming Virtual machine consolidation

来源：评论

学校读者我要写书评

暂无评论

On the independent set problem in random graphs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2015年第11期92卷 2233-2242页

作者： Song, Yinglei Jiangsu Univ Sci & Technol Sch Comp Sci & Engn Zhanjiang 212003 Jiangsu Peoples R China

In this paper, we develop efficient exact and approximate algorithms for computing a maximum independent set in random graphs. In a random graph G, each pair of vertices are joined by an edge with a probability p, where p is a constant between 0 and 1. We show that a maximum independent set in a random graph that contains n vertices can be computed in expected computation time 2(O(log22 n)). In addition, we show that, with high probability, the parameterized independent set problem is fixed parameter tractable in random graphs and the maximum independent set in a random graph in n vertices can be approximated within a ratio of 2n/2(root log2 n) in expected polynomial time.

关键词： independent set random graphs exact algorithm parameterized algorithm approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Bundling three convex polygons to minimize area or perimeter

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2016年 51卷 1-14页

作者： Park, Dongwoo Bae, Sang Won Alt, Helmut Ahn, Hee-Kap POSTECH Dept Comp Sci & Engn Pohang South Korea Kyonggi Univ Dept Comp Sci Suwon South Korea Free Univ Berlin Berlin Germany

Given three convex polygons having n vertices in total in the plane, we consider the problem of finding a translation for each polygon such that the translated polygons are pairwise disjoint and the area or the perimeter of their convex hull is minimized. We present the first O(n(2))-time algorithm that finds optimal translations of input polygons using O(n(2)) space for this problem. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Packing problem Convex polygon Optimization exact algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：