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

NEW TRAJECTORY-FOLLOWING polynomial-time ALGORITHM FOR LINEAR-PROGRAMMING PROBLEMS

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1989年第3期63卷 433-458页

作者： ROOS, C Department of Mathematics and Informatics/Computer Science Delft University of Technology Delft Holland

A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., deepstep) version of the algorithm.

关键词： interior point methods Linear programming pathfollowing methods polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

The graph of atomic divisors and recognition of finite simple groups

引用

JOURNAL OF ALGEBRA 2019年 537卷 478-502页

作者： Buturlakin, Alexander A. Vasil'ev, Audrey V. Sobolev Inst Math 4 Acad Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogova Str Novosibirsk 630090 Russia

The spectrum omega(G) of a finite group G is the set of orders of elements of G. We present a polynomial-time algorithm that, given a finite set M of positive integers, outputs either an empty set or a finite simple group G. In the former case, there is no finite simple group H with M = omega(H), while in the latter case, M subset of omega(G) and M not equal omega(H) for all finite simple groups H with omega(H) not equal omega(G). (C) 2019 Elsevier Inc. All rights reserved.

关键词： Finite simple group Spectrum of a group Recognition by spectrum Prime graph Graph of atomic divisors polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

COMPUTATIONAL-COMPLEXITY OF INNER AND OUTER J-RADII OF POLYTOPES IN FINITE-DIMENSIONAL NORMED SPACES

引用

MATHEMATICAL PROGRAMMING 1993年第2期59卷 163-213页

作者： GRITZMANN, P KLEE, V UNIV WASHINGTON DEPT MATHSEATTLEWA 98195

This paper studies the complexity of computing (or approximating, or bounding) the various inner and outer radii of an n-dimensional convex polytope in the space R(n) equipped with an l(p) norm or a polytopal norm. The polytope P is assumed to be presented as the convex hull of finitely many points with rational coordinates (V-presented) or as the intersection of finitely many closed halfspaces defined by linear inequalities with rational coefficients (He-presented). The inner j-radius of P is the radius of a largest j-ball contained in P;it is P's in radius when j = n and half of P's diameter when j = 1. The outer j-radius measures how well P can be approximated, in a minimax sense, by an (n - j)-flat;it is P's circumradius when j = n and half of P's width when j = 1. The binary (Turing machine) model of computation is employed. The primary concern is not with finding optimal algorithms, but with establishing polynomial-time computability or NP-hardness. Special attention is paid to the case in which P is centrally symmetric. When the dimension n is permitted to vary, the situation is roughly as follows: (a) for general H-presented polytopes in l(p) spaces with 1 < p < infinity, all outer radius computations are NP-hard;(b) in the remaining cases (including symmetric H-presented polytopes), some radius computations can be accomplished in polynomial time and others are NP-hard. These results are obtained by using a variety of tools from the geometry of convex bodies, from linear and nonlinear programming, and from the theory of computational complexity. Applications of the results to various problems in mathematical programming, computer science and other fields are included.

关键词： COMPUTATIONAL CONVEXITY COMPUTATIONAL COMPLEXITY polynomial-time algorithms NP-HARDNESS MATHEMATICAL PROGRAMMING COMPUTATIONAL GEOMETRY ELLIPSOID METHOD LINEAR PROGRAMMING SENSITIVITY ANALYSIS QUADRATIC PROGRAMMING ROBOTICS CONVEX BODY POLARITY POLYTOPE CONVEX HULL BREADTH WIDTH DIAMETER RADIUS INSPHERE CIRCUMSPHERE

来源：评论

学校读者我要写书评

暂无评论

algorithms FOR PREEMPTIVE SCHEDULING OF DIFFERENT CLASSES OF PROCESSORS TO DO JOBS WITH FIXED timeS

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1993年第3期70卷 316-326页

作者： DONDETI, VR EMMONS, H CASE WESTERN RESERVE UNIV DEPT OPERAT RESCLEVELANDOH 44106

We consider scheduling problems that involve processors of different classes and jobs with fixed start and finish times. We allow preemption of jobs, but impose restrictions on the assignment of processors to jobs. We present polynomial-time algorithms for finding the minimal-cost preemptive solutions for two special cases in which the number of job classes is at most one more than the number of processor classes. We then discuss a generalized version in which a processor can be assigned only to a subset of the jobs and a job can be done only by a subset of the processors. We prove that for this case the problem of finding a preemptive feasible schedule with a given combination of processors can be solved in polynomial time, by transforming it into a transportation-network problem. Next, we extend these results to cyclic scheduling problems. Further, we discuss some transformations among these class scheduling problems and provide simpler proofs of NP-completeness for the nonpreemptive versions of the first two cases.

关键词： PREEMPTIVE SCHEDULING CLASSES OF PROCESSORS FIXED JOB timeS polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

AN EFFICIENT ALGORITHM FOR THE MINIMUM CAPACITY CUT PROBLEM

引用

MATHEMATICAL PROGRAMMING 1990年第1期47卷 19-36页

作者： PADBERG, M RINALDI, G CNR IST ANALISI SISTEMI & INFORMATI-00185 ROMEITALY

Given a finite undirected graph with nonnegative edge capacities the minimum capacity cut problem consists of partitioning the graph into two nonempty sets such that the sum of the capacities of edges connecting the two parts is minimum among all possible partitionings. The standard algorithm to calculate a minimum capacity cut, due to Gomory and Hu (1961), runs in O(n 4) time and is difficult to implement. We present an alternative algorithm with the same worst-case bound which is easier to implement and which was found empirically to be far superior to the standard algorithm. We report computational results for graphs with up to 2000 nodes.

关键词： Minimum weighted cuts networks polynomial-time algorithms computation

来源：评论

学校读者我要写书评

暂无评论

List-k-Coloring H-Free Graphs for All k >4

引用

COMBINATORICA 2024年第5期44卷 1063-1068页

作者： Chudnovsky, Maria Hajebi, Sepehr Spirkl, Sophie Princeton Univ Princeton NJ USA Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada

Given an integer k>4 and a graph H, we prove that, assuming P not equal NP, the List-k-Coloring Problem restricted to H-free graphs can be solved in polynomial time if and only if either every component of H is a path on at most three vertices, or removing the isolated vertices of H leaves an induced subgraph of the five-vertex path. In fact, the "if" implication holds for all k >= 1

关键词： Coloring List-Coloring Induced subgraphs polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

PhySIC:: A veto supertree method with desirable properties

引用

SYSTEMATIC BIOLOGY 2007年第5期56卷 798-817页

作者： Ranwez, Vincent Berry, Vincent Criscuolo, Alexis Fabre, Pierre-Henri Guillemot, Sylvain Scornavacca, Celine Douzery, Emmanuel J. P. Univ Montpellier I Inst Sci Evolut CNRS ISEMUMR 5554 F-34095 Montpellier France Univ Montpellier 2 CNRS Lab Informat Robot Microelectron LIRMMUMR 5506 F-34392 Montpellier France

This paper focuses on veto supertree methods;i.e., methods that aim at producing a conservative synthesis of the relationships agreed upon by all source trees. We propose desirable properties that a supertree should satisfy in this framework, namely the non-contradiction property (PC) and the induction property (PI). The former requires that the supertree does not contain relationships that contradict one or a combination of the source topologies, whereas the latter requires that all topological information contained in the supertree is present in a source tree or collectively induced by several source trees. We provide simple examples to illustrate their relevance and that allow a comparison with previously advocated properties. We show that these properties can be checked in polynomial time for any given rooted supertree. Moreover, we introduce the PhySIC method (PHYlogenetic Signal with induction and non-Contradiction). For k input trees spanning a set of n taxa, this method produces a supertree that satisfies the above-mentioned properties in O(kn(3) + n(4)) computing time. The polytornies of the produced supertree are also tagged by labels indicating areas of conflict as well as those with insufficient overlap. As a whole, PhySIC enables the user to quickly summarize consensual information of a set of trees and localize groups of taxa for which the data require consolidation. Lastly, we illustrate the behaviour of PhySIC on primate data sets of various sizes, and propose a supertree covering 95% of all primate extant genera. The PhySIC algorithm is available at http:/ /***/cgi-bin/PhySIC. [Formal properties;phylogenetics;polynomial-time algorithms;primates;software;supertrees;triplets;veto methods.]

关键词： Formal properties phylogenetics polynomial-time algorithms primates software supertrees triplets veto methods

来源：评论

学校读者我要写书评

暂无评论

Computing the cores of strategic games with punishment-dominance relations

引用

INTERNATIONAL JOURNAL OF GAME THEORY 2008年第2期37卷 185-201页

作者： Masuzawa, Takuya Osaka Univ Econ Fac Econ Higashi Yodogawa Ku Osaka Japan

In this paper, we discuss the computational complexity of the strategic cores of a class of n-person games defined by Masuzawa (Int J Game Theory 32:479-483, 2003), which includes economic situations with monotone externality. We propose an algorithm for finding an alpha-core strategy of any game in this class which, counting the evaluation of a payoff for a strategy profile as one step, terminates after O(n(3). M) operations, where M is the maximum size of a strategy set of any of the n players. The idea underlying this method is based on the property of reduced games.

关键词： polynomial-time algorithms NTU games the alpha-core reduced games public good provision

来源：评论

学校读者我要写书评

暂无评论

PROJECTION algorithms FOR LINEAR-PROGRAMMING

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1992年第3期60卷 287-295页

作者： BETKE, U GRITZMANN, P UNIV TRIER FACHBEREICH MATH 4W-5500 TRIERGERMANY

Based on the nearest-point projection of geometric convexity we give a general projection approach for solving the feasibility problem of linear programming. Application of Shor's method of space dilation gives rise to a family of polynomial-time ellipsoidal algorithms with improved termination criteria in case of infeasibility. Moreover, the approach renders possible application of various techniques from nonlinear programming. In particular, using a variable metric algorithm with exact line search we obtain a fast and practically well-behaving algorithm for linear programming.

关键词： LINEAR PROGRAMMING CONVEX PROGRAMMING NEAREST-POINT MAP ELLIPSOID METHOD polynomial-time algorithms VARIABLE METRIC algorithms DFP-METHOD BFGS-METHOD

来源：评论

学校读者我要写书评

暂无评论

INTERIOR PATH FOLLOWING PRIMAL-DUAL algorithms .2. CONVEX QUADRATIC-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1989年第1期44卷 43-66页

作者： MONTEIRO, RDC ADLER, I Department of Industrial Engineering and Operations Research University of California Berkeley USA

We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of $$O\left( {\sqrt n L} \ri... 详细信息

We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of $$O\left( {\sqrt n L} \right)$$ number of iterations, whereL is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of O(n 3 L).

关键词： convex quadratic programming Interior-point methods Karmarkar's algorithm logarithmic barrier function path following polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：