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

Safe Approximation-An Efficient Solution for a Hard Routing Problem

algorithmS 2021年第2期14卷 48页

作者： Farago, Andras Mojaveri, Zohre R. Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci POB 830688MS EC31 Richardson TX 75080 USA

The Disjoint Connecting Paths problem and its capacitated generalization, called Unsplittable Flow problem, play an important role in practical applications such as communication network design and routing. These tasks are NP-hard in general, but various polynomial-time approximations are known. Nevertheless, the approximations tend to be either too loose (allowing large deviation from the optimum), or too complicated, often rendering them impractical in large, complex networks. Therefore, our goal is to present a solution that provides a relatively simple, efficient algorithm for the unsplittable flow problem in large directed graphs, where the task is NP-hard, and is known to remain NP-hard even to approximate up to a large factor. The efficiency of our algorithm is achieved by sacrificing a small part of the solution space. This also represents a novel paradigm for approximation. Rather than giving up the search for an exact solution, we restrict the solution space to a subset that is the most important for applications, and excludes only a small part that is marginal in some well-defined sense. Specifically, the sacrificed part only contains scenarios where some edges are very close to saturation. Since nearly saturated links are undesirable in practical applications, therefore, excluding near saturation is quite reasonable from the practical point of view. We refer the solutions that contain no nearly saturated edges as safe solutions, and call the approach safe approximation. We prove that this safe approximation can be carried out efficiently. That is, once we restrict ourselves to safe solutions, we can find the exact optimum by a randomized polynomial time algorithm.

关键词： routing NP-complete NP-hard approximation polynomial time algorithm disjoint connecting paths unsplittable flow network design

来源：评论

学校读者我要写书评

暂无评论

PERFORMANCE RESULTS OF THE SIMPLEX algorithm FOR A SET OF REAL-WORLD LINEAR-PROGRAMMING MODELS

引用

COMMUNICATIONS OF THE ACM 1982年第3期25卷 207-213页

作者： MCCALL, EH UNIV MINNESOTA MINNEAPOLISMN 55455

This paper provides performance results using the SPERRY UNIVAC 1100 Series linear programming product FMPS to solve a set of 16 real-world linear programming problems. As such, this paper provides a data point for the actual performance of a commercial simplex algorithm on real-world linear programming problems and shows that the simplex algorithm is a linear time algorithm in actual performance. Correlations and performance relationships not previously available are also provided. [ABSTRACT FROM AUTHOR]

关键词： computational complexity large scale linear time algorithm polynomial time algorithm simplex algorithm

来源：评论

学校读者我要写书评

暂无评论

The Complexity and algorithm for Minimum Expense Spanning Trees

引用

Procedia Engineering 2012年 29卷 118-122页

作者： Zhan Ning Wu Longshu Mathematics and Computer Science Department Xinyang Vocational and Technical College Xinyang 464000 China College of Science China Jiliang University Hangzhou 310018 China

The minimum spanning tree problem is a classical and well-known combinatorial optimization problem. There exist many efficient algorithms such as the Kruskal algorithm and Prim algorithm to solve it. But in a real network, the vertices as well as the edges may have weights, and there are many cases of the vertex weights according to the degrees of the vertices. In this paper, we consider the computational complexity of the minimum expense spanning tree problem, which is to find a spanning tree in a network with minimum total expenses. We show that this problem is NP-hard in some general situations. And we propose a polynomial time algorithm when computing all the weights of the vertices in a spanning tree.

关键词： Minimum expense spanning tree Computational complexity polynomial time algorithm Combinatorial optimization NP-hard

来源：评论

学校读者我要写书评

暂无评论

The complexity of the equation solvability problem over semipattern groups

引用

INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION 2017年第2期27卷 259-272页

作者： Foldvari, Attila Univ Debrecen Inst Math Pf 400 H-4002 Debrecen Hungary

The complexity of the equation solvability problem is known for nilpotent groups, for not solvable groups and for some semidirect products of Abelian groups. We provide a new polynomial time algorithm for deciding the equation solvability problem over certain semidirect products, where the first factor is not necessarily Abelian. Our main idea is to represent such groups as matrix groups, and reduce the original problem to equation solvability over the underlying field. Further, we apply this new method to give a much more efficient algorithm for equation solvability over nilpotent rings than previously existed.

关键词： Semipattern groups pattern groups equivalence equation solvability computational complexity polynomial time algorithm nilpotent rings matrix rings

来源：评论

学校读者我要写书评

暂无评论

polynomially determine if a graph is (s, 3)-supereulerian

引用

DISCRETE MATHEMATICS 2021年第12期344卷 112601-112601页

作者： Xiong, Wei Song, Sulin Lai, Hong-Jian Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China West Virginia Univ Dept Math Morgantown WV 26506 USA

For integers s > 0 and t > 0, a graph G is (s, t)-supereulerian if for any disjoint edge sets X, Y c E(G) with |X| = 2 and s + t >= 5. As applications, we obtain a characterization of (s, t)-supereulerian gra... 详细信息

For integers s > 0 and t > 0, a graph G is (s, t)-supereulerian if for any disjoint edge sets X, Y c E(G) with |X| < s and |Y| < t, G has a spanning closed trail that contains X and avoids Y. Pulleyblank in 1979 showed that determining whether a graph is (0, 0)- supereulerian, even when restricted to planar graphs, is NP-complete. We investigate the value of the smallest integer j(s, t) such that every j(s, t)-edge-connected graph is (s, t)- supereulerian, and show that j(s, t) = { max{4, t + 2} if 0 < s < 1, or (s, t) E {(2, 0), (2, 1), (3, 0)}, 5 if (s, t) E {(2, 2), (3, 1)}, s + t + 1-(-1)s/2 if s >= 2 and s + t >= 5. As applications, we obtain a characterization of (s, t)-supereulerian graphs when t >= 3 in terms of edge-connectivities, and show that when t >= 3, there exists a polynomial time algorithm to determine if a graph is (s, t)-supereulerian. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Edge-connectivity Spanning closed trail Supereulerian graphs polynomial time algorithm (s, t)-supereulerian

来源：评论

学校读者我要写书评

暂无评论

A Batching Machine Model for Lot Scheduling on a Single Machine

引用

FOUNDATIONS OF COMPUTING AND DECISION SCIENCES 2018年第1期43卷 37-40页

作者： Kovalyov, Mikhail Y. Natl Acad Sci Belarus United Inst Informat Problems Surganova 6 Minsk 220012 BELARUS

A recently introduced lot scheduling problem is considered. It is to find a partition of jobs of n orders into lots and to sequence these lots on a single machine so that the total average completion time of the orders is minimized. A simple O(n log n) time algorithm is presented for this problem in the literature, with a relatively sophisticated proof of its optimality. We show that modeling this problem as a classic batching machine problem makes its optimal solution obvious.

关键词： scheduling lot-sizing single machine batching machine polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast algorithm for High-Throughput Screening Scheduling Based on the PERT/CPM Project Management Technique

引用

algorithmS 2024年第3期17卷 127页

作者： Levner, Eugene Kats, Vladimir Yan, Pengyu Che, Ada Holon Inst Technol Sch Comp Sci IL-5810201 Holon Israel Inst Ind Math IL-8424902 Beer Sheva Israel Univ Elect Sci & Technol China Sch Econ & Management Chengdu 610054 Peoples R China Northwestern Polytech Univ Sch Management Xian 710072 Peoples R China

High-throughput screening systems are robotic cells that automatically scan and analyze thousands of biochemical samples and reagents in real time. The problem under consideration is to find an optimal cyclic schedule of robot moves that ensures maximum cell performance. To address this issue, we proposed a new efficient version of the parametric PERT/CPM project management method that works in conjunction with a combinatorial subalgorithm capable of rejecting unfeasible schedules. The main result obtained is that the new fast PERT/CPM method finds optimal robust schedules for solving large size problems in strongly polynomial time, which cannot be achieved using existing algorithms.

关键词： cyclic robot scheduling high-throughput screening parametric PERT/CPM project management polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

PROBLEM OF COMPUTING THE EXPECTED MAXIMUM NUMBER OF VERTEX-DISJOINT S-T PATHS ON PROBABILISTIC DIGRAPHS

引用

ELECTRONICS AND COMMUNICATIONS IN JAPAN PART III-FUNDAMENTAL ELECTRONIC SCIENCE 1995年第1期78卷 13-23页

作者： CHENG, P MASUYAMA, S Faculty of Engineering Toyohashi University of Technology Toyohashi Japan 441 Members

The problem of finding vertex disjoint paths (i.e., path sharing no vertices) between a specified pair of vertices of a digraph has been extensively studied as one of the fundamental problems in graph theory. For digraphs whose vertices or edges have mutually independent failure probabilities (called probabilistic digraphs hereafter), the expected maximum number of vertex paths is a measure of reliability of the network and its computation is an important practical problem. In this paper, the problem of computing the expected maximum number of vertex disjoint paths between a specified pair of vertices in a given probabilistic digraph is considered. It is shown that the problem is in general NP-hard but that the expected value can be obtained in polynomial time for special types of probabilistic digraphs such as probabilistic s-t series-parallel digraphs and probabilistic s-t complete multistage digraphs in which the vertices have the same failure probability and the arcs are failure-free. Further, the problem is shown to be NP-hard for the following three cases: probabilistic planar digraphs;probabilistic s-t out-in bitrees;and probabilistic s-t complete multistage digraphs.

关键词： PROBABILISTIC DIGRAPH EXPECTED MAXIMUM NUMBER OF VERTEX-DISJOINT S-T PATHS NP-HARD polynomial time algorithm NETWORK RELIABILITY

来源：评论

学校读者我要写书评

暂无评论

A polynomially Solvable Special Case of the Knapsack Sharing Problem

A Polynomially Solvable Special Case of the Knapsack Sharing...

引用

中国运筹学会第七届学术交流会

作者： Cuilian Wu Yuzhong Zhang College of Operations Research and Management Science,Qufu Normal University,Rizhao,Shangdong, 276826

n this paper, a polynomial algorithm for a special case of knapsack sharingproblem is presented by decomposing it into a series of multidimentional knapsackproblems, without the assumption that the number of the const... 详细信息

关键词： knapsack problem knapsack sharing problem polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Vector Connectivity in Graphs

引用

NETWORKS 2014年第4期63卷 277-285页

作者： Boros, Endre Heggernes, Pinar van ' t Hof, Pim Milanic, Martin Rutgers State Univ MSIS Dept Piscataway NJ 08854 USA Rutgers State Univ RUTCOR Piscataway NJ 08854 USA Univ Bergen Dept Informat N-5008 Bergen Norway Univ Primorska UP IAM SI-6000 Koper Slovenia Univ Primorska UP FAMNIT SI-6000 Koper Slovenia

Motivated by challenges related to domination, connectivity, and information propagation in social and other networks, we initiate the study of the VECTOR CONNECTIVITY problem. This problem takes as input a graph G and an integer k(v) for every vertex v of G, and the objective is to find a vertex subset S of minimum cardinality such that every vertex v either belongs to S, or is connected to at least k(v) vertices of S by disjoint paths. If we require each path to be of length exactly 1, we get the well-known VECTOR DOMINATION problem, which is a generalization of the famous DOMINATING SET problem and several of its variants. Consequently, our problem becomes NP-hard if an upper bound on the length of the disjoint paths is also supplied as input. Due to the hardness of these domination variants even on restricted graph classes, like split graphs, VECTOR CONNECTIVITY seems to be a natural problem to study for drawing the boundaries of tractability for this type of problems. We show that VECTOR CONNECTIVITY can actually be solved in polynomial time on split graphs, in addition to cographs and trees. We also show that the problem can be approximated in polynomial time within a factor of In n + 2 on all n-vertex graphs. (C) 2014 Wiley Periodicals, Inc.

关键词： vector connectivity approximation algorithm polynomial time algorithm split graph cograph tree

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：