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

polynomial time algorithms for two special classes of the proportionate multiprocessor open shop

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第3期201卷 720-728页

作者： Matta, Marie E. Elmaghraby, Salah E. George Washington Univ Sch Business Dept Decis Sci Washington DC 20052 USA N Carolina State Univ Dept Ind Engn & Operat Res Raleigh NC 27695 USA

This paper describes a complex scheduling problem taken from a hospital diagnostic testing center that schedules hundreds of patients in an open shop environment consisting of multiple facilities and multiple processors. This scheduling problem, known as the multiprocessor open shop (MPOS) problem, is strongly NP-hard with few published results. Realizing that in many MPOS environments processing times are stage-dependent, not both job and stage-dependent, this paper examines a new class of problems for the MPOS-proportionate ones. This paper exploits the structural nature of the proportionate MPOS and defines new terms. Despite the enormous complexity of the MPOS problem, this work demonstrates that polynomial time algorithms exist for two special cases. Since other applications of this problem exist in service and manufacturing environments, solving the proportionate MPOS problem is not only significant in the theory of optimization, but also in many real-world applications. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Scheduling Sequencing Deterministic Proportionate multiprocessor open shop polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial time algorithms for Branching Markov Decision Processes and Probabilistic Min (Max) polynomial Bellman Equations

引用

MATHEMATICS OF OPERATIONS RESEARCH 2020年第1期45卷 34-62页

作者： Etessami, Kousha Stewart, Alistair Yannakakis, Mihalis Univ Edinburgh Sch Informat Edinburgh EH8 9AB Midlothian Scotland Univ Southern Calif Dept Comp Sci Los Angeles CA 90089 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

We show that one can compute the least nonnegative solution (also known as the least fixed point) for a system of probabilistic min (max) polynomial equations, to any desired accuracy epsilon > 0 in time polynomial in both the encoding size of the system and in log(1/epsilon). These are Bellman optimality equations for important classes of infinite-state Markov decision processes (MDPs), including branching MDPs (BMDPs), which generalize classic multitype branching stochastic processes. We thus obtain the first polynomial time algorithm for computing, to any desired precision, optimal (maximum and minimum) extinction probabilities for BMDPs. Our algorithms are based on a novel generalization of Newton's method, which employs linear programming in each iteration. We also provide polynomial-time (P-time) algorithms for computing an epsilon-optimal policy for both maximizing and minimizing extinction probabilities in a BMDP, whereas we note a hardness result for computing an exact optimal policy. Furthermore, improving on prior results, we provide more efficient P-time algorithms for qualitative analysis of BMDPs, that is, for determining whether the maximum or minimum extinction probability is 1, and, if so, computing a policy that achieves this. We also observe some complexity consequences of our results for branching simple stochastic games, which generalize BMDPs.

关键词： multitype branching processes Markov decision processes Bellman optimality equations generalized Newton method polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

polynomial time algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars 12

Polynomial Time Algorithms for Multi-Type Branching Processe...

引用

44th ACM Annual Symposium on Theory of Computing (STOC)

作者： Etessami, Kousha Stewart, Alistair Yannakakis, Mihalis Univ Edinburgh Sch Informat Edinburgh EH8 9AB Midlothian Scotland Columbia Univ Dept Comp Sci New York NY 10027 USA

ISBN: (纸本)9781450312455

We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in log(1/epsilon), where epsilon > 0 is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.) We use this result to resolve several open problems regarding the computational complexity of computing key quantities associated with some classic and heavily studied stochastic processes, including multi-type branching processes and stochastic context-free grammars.

关键词： polynomial time algorithms probabilistic systems of polynomial equations

来源：评论

学校读者我要写书评

暂无评论

polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem

引用

DISCRETE APPLIED MATHEMATICS 2019年 253卷 103-121页

作者： Aringhieri, Roberto Grosso, Andrea Hosteins, Pierre Scatamacchia, Rosario Univ Torino Dipartimento Informat Corso Svizzera 185 I-10149 Turin Italy INESC TEC Rua Dr Roberto Frias 378 P-4200 Porto Portugal Politecn Torino Dipartimento Ingn Gest & Prod Corso Duca Abruzzi 24 I-10129 Turin Italy

We study the Distance Critical Node Problem, a generalisation of the Critical Node Problem where the distances between node pairs impact on the objective function. We establish complexity results for the problem according to specific distance functions and provide polynomial and pseudo-polynomial algorithms for special graph classes such as paths, trees and series-parallel graphs. We also provide additional insights about special cases of the Critical Node Problem variants already tackled in the literature. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Critical Node Problem Connectivity measure Shortest paths Dynamic programming polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Single-Machine Scheduling with Learning Effects and Maintenance: A Methodological Note on Some polynomial-time Solvable Cases

引用

MATHEMATICAL PROBLEMS IN ENGINEERING 2017年第1期2017卷 1-6页

作者： Ying, Kuo-Ching Lu, Chung-Cheng Lin, Shih-Wei Chen, Jie-Ning Natl Taipei Univ Technol Dept Ind Engn & Management Taipei Taiwan Natl Chiao Tung Univ Dept Transportat & Logist Management Taipei Taiwan Chang Gung Univ Dept Informat Management Taoyuan Taiwan Ming Chi Univ Technol Dept Ind Engn & Management Taipei Taiwan Linkou Chang Gung Mem Hosp Dept Neurol Taoyuan Taiwan Wistron Corp Taipei Taiwan

This work addresses four single-machine scheduling problems (SMSPs) with learning effects and variable maintenance activity. The processing times of the jobs are simultaneously determined by a decreasing function of their corresponding scheduled positions and the sum of the processing times of the already processed jobs. Maintenance activity must start before a deadline and its duration increases with the starting time of the maintenance activity. This work proposes a polynomial-time algorithm for optimally solving two SMSPs to minimize the total completion time and the total tardiness with a common due date.

关键词： MACHINE learning PRODUCTION scheduling polynomial time algorithms PROBLEM solving MAINTENANCE

来源：评论

学校读者我要写书评

暂无评论

A polynomial time ALGORITHM FOR COMPUTING EXTINCTION PROBABILITIES OF MULTITYPE BRANCHING PROCESSES

引用

SIAM JOURNAL ON COMPUTING 2017年第5期46卷 1515-1553页

作者： Etessami, Kousha Stewart, Alistair Yannakakis, Mihalis Univ Edinburgh Sch Informat Edinburgh EH8 9AB Midlothian Scotland Univ Southern Calif Dept Comp Sci Los Angeles CA 90007 USA Columbia Univ Dept Comp Sci New York NY 10027 USA

We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding size of the system of equations and in log(1/c), where c > 0 is the desired additive error bound of the solution. (The model of computation is the standard Turing machine model.) We use this result to resolve several open problems regarding the computational complexity of computing key quantities associated with some classic and well studied stochastic processes, including multitype branching processes and stochastic context-free grammars.

关键词： multitype branching processes extinction probabilities polynomial time algorithms nonlinear systems of equations Newton's method computational complexity

来源：评论

学校读者我要写书评

暂无评论

Detecting Fixed Patterns in Chordal Graphs in polynomial time

引用

ALGORITHMICA 2014年第3期69卷 501-521页

作者： Belmonte, Remy Golovach, Petr A. Heggernes, Pinar van 't Hof, Pim Kaminski, Marcin Paulusma, Daniel Univ Bergen Dept Informat N-5008 Bergen Norway Univ Durham Sch Engn & Comp Sci Durham England Univ Libre Bruxelles Dept Informat Brussels Belgium

The Contractibility problem takes as input two graphs G and H, and the task is to decide whether H can be obtained from G by a sequence of edge contractions. The Induced Minor and Induced Topological Minor problems are similar, but the first allows both edge contractions and vertex deletions, whereas the latter allows only vertex deletions and vertex dissolutions. All three problems are NP-complete, even for certain fixed graphs H. We show that these problems can be solved in polynomial time for every fixed H when the input graph G is chordal. Our results can be considered tight, since these problems are known to be W[1]-hard on chordal graphs when parameterized by the size of H. To solve Contractibility and Induced Minor, we define and use a generalization of the classic Disjoint Paths problem, where we require the vertices of each of the k paths to be chosen from a specified set. We prove that this variant is NP-complete even when k=2, but that it is polynomial-time solvable on chordal graphs for every fixed k. Our algorithm for Induced Topological Minor is based on another generalization of Disjoint Paths called Induced Disjoint Paths, where the vertices from different paths may no longer be adjacent. We show that this problem, which is known to be NP-complete when k=2, can be solved in polynomial time on chordal graphs even when k is part of the input. Our results fit into the general framework of graph containment problems, where the aim is to decide whether a graph can be modified into another graph by a sequence of specified graph operations. Allowing combinations of the four well-known operations edge deletion, edge contraction, vertex deletion, and vertex dissolution results in the following ten containment relations: (induced) minor, (induced) topological minor, (induced) subgraph, (induced) spanning subgraph, dissolution, and contraction. Our results, combined with existing results, settle the complexity of each of the ten corresponding containment proble

关键词： polynomial time algorithms TOPOLOGICAL graph theory SUBGRAPHS GRAPH theory COMPUTATIONAL complexity

来源：评论

学校读者我要写书评

暂无评论

A polynomial time algorithm for convex cost lot-sizing problems

引用

OPERATIONS RESEARCH LETTERS 2015年第4期43卷 359-364页

作者： Teksan, Z. Melis Geunes, Joseph Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

This paper provides a polynomial-time algorithm for economic lot-sizing problems with convex costs in the production and inventory quantities. The resulting algorithm is based on a primal dual approach that takes advantage of the problem's special structure. This approach improves upon existing results in the literature, which are either pseudo-polynomial or focus on special cases. We apply the approach to a production planning problem with price-dependent supply, leading to an improved bound on the algorithm's running time for a special case. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Convex cost lot sizing polynomial time algorithms Production and inventory systems Supply chain management

来源：评论

学校读者我要写书评

暂无评论

Computing the clique number of a-perfect graphs in polynomial time

引用

EUROPEAN JOURNAL OF COMBINATORICS 2014年 35卷 449-458页

作者： Pecher, Arnaud Wagler, Annegret K. Univ Bordeaux Lab Bordelais Rech Informat LaBRI INRIA Sud Ouest F-33405 Talence France Univ Blaise Pascal Clermont Ferrand II LIMOS CNRS F-63173 Aubiere France

A main result of combinatorial optimization is that the clique and chromatic numbers of a perfect graph are computable in polynomial time (Grotschel et al., 1981) [7]. This result relies on polyhedral characterizations of perfect graphs involving the stable set polytope of the graph, a linear relaxation defined by clique constraints, and a semi-definite relaxation, the Theta-body of the graph. A natural question is whether the algorithmic results for perfect graphs can be extended to graph classes with similar polyhedral properties. We consider a superclass of perfect graphs, the a-perfect graphs, whose stable set polytope is given by constraints associated with generalized cliques. We show that for such graphs the clique number can be computed in polynomial time as well. The result strongly relies upon Fulkerson's antiblocking theory for polyhedra and Lovasz's Theta function. (C) 2013 Elsevier Ltd. All rights reserved.

关键词： NUMBER theory PERFECT graphs GRAPH theory polynomial time algorithms COMBINATORIAL optimization CHROMATIC polynomial

来源：评论

学校读者我要写书评

暂无评论

Existence and Uniqueness of Structures Computable in polynomial time

引用

ALGEBRA AND LOGIC 2016年第1期55卷 72-76页

作者： Alaev, P. E. Sobolev Inst Math Pr Akad Koptyuga 4 Novosibirsk 630090 Russia Novosibirsk State Univ Ul Pirogova 2 Novosibirsk 630090 Russia

Presented by Associate Editor S. S. Goncharov

关键词： polynomial time algorithms COMPUTABLE functions RECURSIVE functions PREDICATE (Logic) ALGEBRA

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：