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

polynomial algorithms FOR LINEAR-PROGRAMMING OVER THE ALGEBRAIC-NUMBERS

ALGORITHMICA 1994年第6期12卷 436-457页

作者： ADLER, I BELING, PA UNIV VIRGINIA DEPT SYST ENGNCHARLOTTESVILLEVA 22903

We derive a bound on the computational complexity of linear programs whose coefficients are real algebraic numbers. Key to this result is a notion of problem size that is analogous in function to the binary size of a rational-number problem. We also view the coefficients of a linear program as members of a finite algebraic extension of the rational numbers. The degree of this extension is an upper bound on the degree of any algebraic number that can occur during the course of the algorithm, and in this sense can be viewed as a supplementary measure of problem dimension. Working under an arithmetic model of computation, and making use of a tool for obtaining upper and lower bounds on polynomial functions of algebraic numbers, we derive an algorithm based on the ellipsoid method that runs in time bounded by a polynomial in the dimension, degree, and size of the linear program. Similar results hold under a rational number model of computation, given a suitable binary encoding of the problem input.

关键词： LINEAR PROGRAMMING ALGEBRAIC NUMBERS COMPUTATIONAL COMPLEXITY ELLIPSOID METHOD polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Phylogeny- and parsimony-based haplotype inference with constraints

引用

INFORMATION AND COMPUTATION 2012年 213卷 33-47页

作者： Elberfeld, Michael Tantau, Till Univ Lubeck Inst Theoret Informat D-23538 Lubeck Germany

Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes based on genotype data. One fast computational haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. An extension of this approach tries to incorporate prior knowledge in the form of a set of candidate haplotypes from which the right haplotypes must be chosen. The objective is to increase the accuracy of haplotyping methods, but it was conjectured that the resulting formal problem constrained perfect phylogeny haplotyping might be NP-complete. In the paper at hand we present a polynomial-time algorithm for it. Our algorithmic ideas also yield new fixed-parameter algorithms for related haplotyping problems based on the maximum parsimony assumption. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Haplotype inference Perfect phylogeny Maximum parsimony polynomial-time algorithms Fixed-parameter algorithms

来源：评论

学校读者我要写书评

暂无评论

Strongly Stable and Maximum Weakly Stable Noncrossing Matchings

引用

ALGORITHMICA 2021年第9期83卷 2678-2696页

作者： Hamada, Koki Miyazaki, Shuichi Okamoto, Kazuya NTT Corp 3-9-11 Midori Cho Musashino Tokyo 1808585 Japan Kyoto Univ Grad Sch Informat Sakyo Ku Kyoto 6068501 Japan Kyoto Univ Acad Ctr Comp & Media Studies Sakyo Ku Kyoto 6068501 Japan Kyoto Univ Hosp Div Med Informat Technol & Adm Planning 54 Kawaharacho Kyoto 6068507 Japan

In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an O(n(2))-time algorithm to find one for an instance with n men and n women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomial time. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete. This NP-completeness holds even if each person's preference list is of length at most two and ties appear in only men's preference lists. To complement this intractability, we show that the problem is solvable in polynomial time if the length of preference lists of one side is bounded by one (but that of the other side is unbounded).

关键词： Stable marriage Noncrossing matching polynomial-time algorithms NP-completeness

来源：评论

学校读者我要写书评

暂无评论

A polynomial algorithm for 2-cyclic robotic scheduling: A non-Euclidean case

引用

DISCRETE APPLIED MATHEMATICS 2009年第2期157卷 339-355页

作者： Kats, Vladimir Levner, Eugene Holon Inst Technol IL-58102 Holon Israel Inst Ind Math IL-84105 Beer Sheva Israel

In this paper we consider the problem of no-wait cyclic scheduling of identical parts in an m-machine production line in which a robot is responsible for moving each part from a machine to another. The aim is to rind the minimum cycle time for the so-called 2-cyclic schedules, in which exactly two parts enter and two parts leave the production line during each cycle. The earlier known polynomial-time algorithms for this problem are applicable only under the additional assumption that the robot travel times satisfy the triangle inequalities. We lift this assumption on robot travel times and present a polynomial-time algorithm with the same time complexity as in the metric case, O(m(5) log m). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Cyclic scheduling Robotic scheduling polynomial-time algorithms Complexity No-wait condition Euler formula

来源：评论

学校读者我要写书评

暂无评论

Chinese Postman Problem on edge-colored multigraphs

引用

DISCRETE APPLIED MATHEMATICS 2017年第Part2期217卷 196-202页

作者： Gutin, Gregory Jones, Mark Sheng, Bin Wahlstrom, Magnus Yeo, Anders Royal Holloway Univ London Dept Comp Sci Egham TW20 0EX Surrey England Univ Southern Denmark Dept Math & Comp Sci Campusvey 55 DK-5230 Odense Denmark Univ Johannesburg Dept Math ZA-2006 Auckland Pk South Africa

It is well-known that the Chinese Postman Problem on undirected and directed graphs is polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in sharp contrast to the Chinese Postman Problem on mixed graphs, i.e., graphs with directed and undirected edges, for which, the,problem is NP-hard. (C) 2016 Published by Elsevier B.V.

关键词： Edge-colored graphs Properly colored trails Chinese Postman Problem polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job

引用

JOURNAL OF SCHEDULING 2016年第1期19卷 61-72页

作者： Dugarzhapov, Aldar Kononov, Alexander Novosibirsk State Univ Novosibirsk 630090 Russia Ecole Polytech Palaiseau France Sobolev Inst Math Novosibirsk Russia

In a so-called mixed-shop scheduling problem, the operations of some jobs have to be processed in a fixed order (as in the job-shop problem);the other ones can be processed in an arbitrary order (as in the open-shop problem). In this paper we present a new exact polynomial-time algorithm for the mixed-shop problems with preemptions and at most two unit operations per job.

关键词： Mixed-shop scheduling polynomial-time algorithms Preemption

来源：评论

学校读者我要写书评

暂无评论

A pricing approach for bandwidth allocation in differentiated service networks

引用

COMPUTERS & OPERATIONS RESEARCH 2008年第12期35卷 3769-3786页

作者： Guan, Yongpei Yang, Weilai Owen, Henry Blough, Douglas A. Univ Oklahoma Sch Ind Engn Norman OK 73019 USA Georgia Inst Technol Sch Elect & Comp Engn Atlanta GA 30332 USA

We present a decentralized auction-based scheme for bandwidth allocation and pricing in a differentiated service-based network. Different classes of clients provide their own expected bandwidth price and required amount of bandwidth. A service provider decides the admission price and differentiated service provided for each class of clients. We introduce mathematical formulations and provide a solution approach to maximize the service provider's revenue. For a single bottleneck link case, a polynomial-time algorithm is developed to obtain an optimal solution. For a multiple bottleneck link case, a heuristic algorithm is developed to solve the problem. The effectiveness of our solution approach is validated by simulation results, which compare our algorithms against the traditional flat-rate pricing approach. (c) 2007 Elsevier Ltd. All rights reserved.

关键词： telecommunication network pricing polynomial-time algorithms heuristics simulation

来源：评论

学校读者我要写书评

暂无评论

Optimal Selection of Line Extensions: Incorporating Operational, Financial, and Marketing Constraints

引用

IEEE TRANSACTIONS ON ENGINEERING MANAGEMENT 2014年第4期61卷 738-754页

作者： Mu, Liying Dawande, Milind Gavirneni, Srinagesh Sriskandarajah, Chelliah Univ Texas Dallas Naveen Jindal Sch Management Dallas TX 75080 USA Cornell Univ Johnson Sch Management Ithaca NY 14850 USA Texas A&M Univ Mays Business Sch College Stn TX 77843 USA

Line extensions-variants of existing products with new appearances, functions, or forms-constitute a significant fraction of products launched each year. While line extensions typically share components with existing products, they can also cannibalize the demand of existing products. The choice of an appropriate set of line extensions is an important recurring issue for a firm and they must incorporate constraints that arise naturally from operational, financial, and marketing considerations, resulting in an analytically challenging optimization problem. We consider several variants of this problem, develop efficient heuristics that deliver near-optimal solutions, and derive a variety of interesting insights on the inherent tradeoffs in the selection of line extensions.

关键词： Budget constraint cardinality constraint line extensions polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

On the Elusiveness of Clusters

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2012年第2期9卷 517-534页

作者： Kelk, Steven M. Scornavacca, Celine Van Iersel, Leo Maastricht Univ Dept Knowledge Engn DKE NL-6200 MD Maastricht Netherlands Univ Tubingen Ctr Bioinformat ZBIT D-72076 Tubingen Germany Univ Canterbury Dept Math & Stat Christchurch 1 New Zealand

Rooted phylogenetic networks are often used to represent conflicting phylogenetic signals. Given a set of clusters, a network is said to represent these clusters in the softwired sense if, for each cluster in the input set, at least one tree embedded in the network contains that cluster. Motivated by parsimony we might wish to construct such a network using as few reticulations as possible, or minimizing the level of the network, i.e., the maximum number of reticulations used in any "tangled" region of the network. Although these are NP-hard problems, here we prove that, for every fixed k >= 0, it is polynomial-time solvable to construct a phylogenetic network with level equal to k representing a cluster set, or to determine that no such network exists. However, this algorithm does not lend itself to a practical implementation. We also prove that the comparatively efficient CASS algorithm correctly solves this problem (and also minimizes the reticulation number) when input clusters are obtained from two not necessarily binary gene trees on the same set of taxa but does not always minimize level for general cluster sets. Finally, we describe a new algorithm which generates in polynomial-time all binary phylogenetic networks with exactly r reticulations representing a set of input clusters (for every fixed r >= 0).

关键词： Rooted phylogenetic networks clusters reticulate evolution parsimony computational complexity polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for Outerplanar Diameter Improvement

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2017年 89卷 315-327页

作者： Cohen, Nathann Goncalves, Daniel Kim, Eun Jung Paul, Christophe Sau, Ignasi Thilikos, Dimitrios M. Weller, Mathias CNRS LRI Orsay France CNRS LIRMM Montpellier France CNRS LAMSADE Paris France Comp Technol Inst & Press Diophantus Patras Greece Univ Athens Dept Math Athens Greece

The OUTERPLANAR DIAMETER IMPROVEMENT problem asks, given a graph G and an integer D, whether it is possible to add edges to G in a way that the resulting graph is outerplanar and has diameter at most D. We provide a dynamic programming algorithm that solves this problem in polynomial time. OUTERPLANAR DIAMETER IMPROVEMENT demonstrates several structural analogues to the celebrated and challenging PLANAR DIAMETER IMPROVEMENT problem, where the resulting graph should, instead, be planar. The complexity status of this latter problem is open. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Diameter improvement Outerplanar graphs Completion problems polynomial-time algorithms Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：