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

Properties of polynomials of periodic functions and the complexity of periodicity detection by the Boolean function polynomial

引用

DISCRETE MATHEMATICS AND APPLICATIONS 2014年第3期24卷 129-137页

作者： Bukhman, Anton V. Lomonosov Moscow State Univ Moscow Russia

The algorithmic complexity of periodicity detection of Boolean functions given in a polynomial form is investigated. A function is said to be periodic with period if it takes the same values on input strings which differ only by inverting the components corresponding to nonzero entries in the bit string . Two polynomial-time algorithms for checking whether a given bit string is a period of a given Boolean function are presented. The relationship between the periods of a function and the length of its polynomial is investigated. The problem of finding the periods is explicitly reduced in polynomial time to the problem of solving a system of Boolean equations.

关键词： Boolean functions periodicity detection 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 1.Department of Industrial Engineering and Operations Research University of California 94720 Berkeley CA USA

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 ³ L).

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

来源：评论

学校读者我要写书评

暂无评论

INTERIOR PATH FOLLOWING PRIMAL-DUAL algorithms .1. LINEAR-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1989年第1期44卷 27-41页

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

We describe a primal-dual interior point algorithm for linear 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 the 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.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：