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

An algorithm for the Polyhedral Cycle Cover Problem with Constraints on the Number and Length of Cycles

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS 2019年第SUPPL 1期307卷 142-150页

作者： Shenmaier, V. V. Russian Acad Sci Siberian Branch Sobolev Inst Math Novosibirsk 630090 Russia

A cycle cover of a graph is a spanning subgraph whose connected components are simple cycles. Given a complete weighted directed graph, consider the intractable problem of finding a maximum-weight cycle cover which satisfies an upper bound on the number of cycles and a lower bound on the number of edges in each cycle. We suggest a polynomial-time algorithm for solving this problem in the geometric case where the vertices of the graph are points in a multidimensional real space and the distances between them are induced by a positively homogeneous function whose unit ball is an arbitrary convex polytope with a fixed number of facets. The obtained result extends the ideas underlying the well-known algorithm for the polyhedral Max TSP.

关键词： cycle cover Max TSP polyhedral metric optimal solution polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Reconstruction of time-consistent species trees

引用

algorithmS FOR MOLECULAR BIOLOGY 2020年第1期15卷 16-16页

作者： Lafond, Manuel Hellmuth, Marc Univ Sherbrooke Dept Comp Sci 2500 Boul Univ Sherbrooke PQ J1K 2R1 Canada Univ Leeds Sch Comp EC Stoner Bldg Leeds LS2 9JT W Yorkshire England

Background The history of gene families-which are equivalent to event-labeled gene trees-can to some extent be reconstructed from empirically estimated evolutionary event-relations containing pairs of orthologous, paralogous or xenologous genes. The question then arises as whether inferred event-labeled gene trees are "biologically feasible" which is the case if one can find a species tree with which the gene tree can be reconciled in a time-consistent way. Results In this contribution, we consider event-labeled gene trees that contain speciations, duplications as well as horizontal gene transfer (HGT) and we assume that the species tree is unknown. Although many problems become NP-hard as soon as HGT and time-consistency are involved, we show, in contrast, that the problem of finding a time-consistent species tree for a given event-labeled gene can be solved in polynomial-time. We provide a cubic-time algorithm to decide whether a "time-consistent" species tree for a given event-labeled gene tree exists and, in the affirmative case, to construct the species tree within the same time-complexity.

关键词： Tree reconciliation Gene evolution Species evolution Horizontal gene transfer time-consistency polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

An Efficient algorithm for the Fast Delivery Problem 22nd

An Efficient Algorithm for the Fast Delivery Problem

引用

22nd International Symposium on Fundamentals of Computation Theory (FCT)

作者： Carvalho, Iago A. Erlebach, Thomas Papadopoulos, Kleitos Univ Fed Minas Gerais Dept Comp Sci Belo Horizonte MG Brazil Univ Leicester Dept Informat Leicester Leics England

ISBN: (纸本)9783030250270;9783030250263

We study a problem where k autonomous mobile agents are initially located on distinct nodes of a weighted graph (with n nodes and m edges). Each autonomous mobile agent has a predefined velocity and is only allowed to move along the edges of the graph. We are interested in delivering a package, initially positioned in a source node s, to a destination node y. The delivery is achieved by the collective effort of the autonomous mobile agents, which can carry and exchange the package among them. The objective is to compute a delivery schedule that minimizes the delivery time of the package. In this paper, we propose an (O(kn log(kn) + km) time algorithm for this problem. This improves the previous state-of-the-art (O(k(2)m + kn(2) + APSP) time algorithm for this problem, where APSP stands for the running-time of an algorithm for the All-Pairs Shortest Paths problem.

关键词： Mobile agents Dijkstra's algorithm polynomial-time algorithm time-dependent shortest paths

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for the tridiagonal and Hessenberg P-matrix linear complementarity problem

引用

OPERATIONS RESEARCH LETTERS 2012年第6期40卷 484-486页

作者： Gaertner, Bernd Sprecher, Markus ETH Inst Theoret Comp Sci CH-8092 Zurich Switzerland

关键词： Linear complementarity Tridiagonal matrix Hessenberg matrix P-matrix polynomial-time algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints

引用

COMPUTERS & OPERATIONS RESEARCH 2018年第Jan.期89卷 17-30页

作者： Charkhgard, Hadi Savelsbergh, Martin Talebian, Masoud Univ S Florida Dept Ind & Management Syst Engn Tampa FL 33620 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Sharif Univ Technol Grad Sch Management & Econ Tehran Iran

We present a linear programming based algorithm for a class of optimization problems with a multi-linear objective function and affine constraints. This class of optimization problems has only one objective function, but it can also be viewed as a class of multi-objective optimization problems by decomposing its objective function. The proposed algorithm exploits this idea and solves this class of optimization problems from the viewpoint of multi-objective optimization. The algorithm computes an optimal solution when the number of variables in the multi-linear objective function is two, and an approximate solution when the number of variables is greater than two. A computational study demonstrates that when available computing time is limited the algorithm significantly outperforms well-known convex programming solvers IPOPT and CVXOPT, in terms of both efficiency and solution quality. The optimization problems in this class can be reformulated as second-order cone programs, and, therefore, also be solved by second-order cone programming solvers. This is highly effective for small and medium size instances, but we demonstrate that for large size instances with two variables in the multi-linear objective function the proposed algorithm outperforms a (commercial) second-order cone programming solver. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Pareto optimal solutions Convex programming Multi-linear objective function Linear programming polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Task scheduling with progress control

引用

IISE TRANSACTIONS 2018年第1期50卷 54-61页

作者： Li, Chung-Lun Zhong, Weiya Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Shanghai Univ Sch Management Dept Business Adm Shanghai Peoples R China

Tasks with long durations often face the requirement of having to periodically report their progress to process controllers. Under this requirement, working teams that simultaneously process multiple tasks need to schedule their work carefully in order to demonstrate satisfactory progress on each unfinished task. We present a single-machine scheduling model that reflects this requirement. Our model has multiple milestones at which the tasks are penalized if their progress is below a satisfactory level. We develop polynomial solution methods for the general case with convex nonlinear penalty functions and for the special case with linear penalty functions. Extensions of our model are also discussed.

关键词： Scheduling multi-tasking polynomial-time algorithm progress milestones

来源：评论

学校读者我要写书评

暂无评论

Strong triadic closure in cographs and graphs of low maximum degree

引用

THEORETICAL COMPUTER SCIENCE 2018年 740卷 76-84页

作者： Konstantinidis, Athanasios L. Nikolopoulos, Stavros D. Papadopoulos, Charis Univ Ioannina Dept Math Ioannina Greece Univ Ioannina Dept Comp Sci & Engn Ioannina Greece

The MAxSTC problem is an assignment of the edges with two types of labels, namely, strong and weak, that maximizes the number of strong edges such that any two vertices that have a common neighbor with a strong edge are adjacent. The CLUSTER DELETION problem seeks for the minimum number of edge removals of a given graph such that the remaining graph is a disjoint union of cliques. Both problems are known to be NP-hard and an optimal solution for the CLUSTER DELETION problem provides a feasible solution for the MAxSTC problem, however not necessarily an optimal one. In this work we conduct the first systematic study that reveals graph families for which the optimal solutions for MAxSTC and CLUSTER DELETION coincide. We first show that MAxSTC coincides with CLUSTER DELETION on cographs and, thus, MAxSTC is solvable in polynomial time on cographs. As a side result, we give an interesting computational characterization of the maximum independent set on the cartesian product of two cographs. Furthermore, we address the influence of the low degree bounds to the complexity of the MAxSTC problem. We show that this problem is polynomial-time solvable on graphs of maximum degree three, whereas MAxSTC becomes NP-complete on graphs of maximum degree four. The proof of the latter result implies that there is no subexponential-time algorithm for MAxSTC unless the Exponential-time Hypothesis fails. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Strong triadic closure Cluster deletion Cographs Bounded degree graphs NP-completeness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Weighted efficient domination for some classes of H-free and of (H₁, H₂)-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2018年 250卷 130-144页

作者： Brandstaedt, Andreas Giakoumakis, Vassilis Milanic, Martin Univ Rostock Inst Informat D-18051 Rostock Germany Univ Picardie Jules Verne MIS Amiens France Univ Primorska UP IAM Muzejski Trg 2 SI-6000 Koper Slovenia Univ Primorska UP FAMNIT Glagoljaska 8 SI-6000 Koper Slovenia

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in G, is known to be NP-complete even for very restricted graph classes such as for claw-free graphs, for 2P(3)-free chordal graphs (and thus, for P-7-free graphs), and for bipartite graphs. For the complexity of ED and its weighted version WED, a dichotomy for H-free graphs was reached: A graph H is called a linear forest if H is acyclic and claw-free, that is, if all its components are paths. Thus, the ED problem remains NP-complete for H-free graphs whenever H is not a linear forest. For every linear forest H, WED is either solvable in polynomial time or NP-complete for H-free graphs;the final result showed that WED is solvable in polynomial time for P-6-free graphs. For (H-1 , H-2)-free graphs, however, we are still far away from a dichotomy result. The main topics of this paper are: (1) to improve the time bounds and simplify the proofs (based on modular decomposition) for polynomial time cases of WED for some H-free graph classes;(2) to investigate the complexity of WED for some cases of (H-1 , H-2)-free graphs such that WED is NP-complete for Hi-free graphs for at least one of i e (1, 2}. Since it is well known that WED is solvable in polynomial time for graph classes of bounded clique width, we consider only classes of (H-1, H-2)-free graphs with unbounded clique-width. (C) 2018 Published by Elsevier B.V.

关键词： Weighted efficient domination Modular decomposition H-free graphs Linear forest (H-1 , H-2)-free graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On decomposability of Multilinear sets

引用

MATHEMATICAL PROGRAMMING 2018年第2期170卷 387-415页

作者： Del Pia, Alberto Khajavirad, Aida Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53706 USA Carnegie Mellon Univ Dept Chem Engn Pittsburgh PA 15213 USA

We consider the Multilinear set defined as the set of binary points (x, y) satisfying a collection of multilinear equations of the form , , where denotes a family of subsets of of cardinality at least two. Such sets appear in factorable reformulations of many types of nonconvex optimization problems, including binary polynomial optimization. A great simplification in studying the facial structure of the convex hull of the Multilinear set is possible when is decomposable into simpler Multilinear sets ,;namely, the convex hull of can be obtained by convexifying each , separately. In this paper, we study the decomposability properties of Multilinear sets. Utilizing an equivalent hypergraph representation for Multilinear sets, we derive necessary and sufficient conditions under which is decomposable into , , based on the structure of pair-wise intersection hypergraphs. Our characterizations unify and extend the existing decomposability results for the Boolean quadric polytope. Finally, we propose a polynomial-time algorithm to optimally decompose a Multilinear set into simpler subsets. Our proposed algorithm can be easily incorporated in branch-and-cut based global solvers as a preprocessing step for cut generation.

关键词： Multilinear functions Convex hull Decomposition Zero-one polynomial optimization Factorable relaxations polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A quadratic time algorithm for computing the optimal landing times of a fixed sequence of planes

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第3期270卷 1148-1157页

作者： Faye, Alain ENSILE Lab CEDRIC 1 Sq Resistance F-91025 Evry France

This paper considers the Aircraft Landing Problem. The aim is to schedule arriving aircraft at the airport under the condition of safe landing. Landing times lie within predefined time windows and safety separation constraints between two successive aircraft landing on the same runway, must be satisfied. The objective is to minimize the total cost of landing deviation from predefined target times within the time windows. On each runway, for a fixed landing sequence, the problem can be solved by a linear program. When safety separation times satisfy the Triangle Inequality, we propose an O(n(2)) algorithm for solving the problem where n is the number of planes of the sequence. We compare the performance of this polynomial time algorithm to the linear programming method. The two methods are embedded in an iterative algorithm, based on simulated annealing, for solving the single runway case. Computational tests, performed on publicly available problems, show that the heuristic based on our algorithm is much faster than the one using linear programming. This gain in CPU time allows to obtain better solutions in a fixed amount of time. (C) 2018 Elsevier B.V. All rights reserved.

关键词： OR in airlines Aircraft Landing Problem Landing times Dynamic programming polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：