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

Maximizing the product of two linear functions in 0-1 variables

OPTIMIZATION 2002年第3期51卷 511-537页

作者： Hammer, PL Hansen, P Pardalos, PM Rader, DJ Rose Hulman Inst Technol Dept Math Terre Haute IN 47803 USA Rutgers State Univ RUTCOR New Brunswick NJ 08903 USA Ecole Hautes Etud Commerciales Gerad Montreal PQ Canada Univ Florida Dept Ind & Syst Engn Gainesville FL 32611 USA

We study both the continuous and discrete problems of maximizing the product of two linear functions subject to all variables being between, 0 and 1. We first give linear and low-order polynomial algorithms for the solution of the continuous problem. In addition, we describe penalties that help to fix variables in the discrete problem. Extensive computational tests demonstrate the effectiveness of these results.

关键词： quadratic 0-1 programming continuous problem discrete problem polynomial algorithms continuous relaxation penalties for nonnegative optimal solutions computational results

来源：评论

学校读者我要写书评

暂无评论

Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms

引用

DISCRETE APPLIED MATHEMATICS 2012年第6期160卷 697-707页

作者： Feder, Tomas Hell, Pavol Huang, Jing Rafiey, Arash Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 3R4 Canada Ist Dalle Molle Intelligenza Artificiale CH-6928 Manno Lugano Switzerland

Interval graphs admit linear-time recognition algorithms and have several elegant forbidden structure characterizations. Interval digraphs can also be recognized in polynomial time, and they admit a characterization in terms of incidence matrices. Nevertheless, they do not have a known forbidden structure characterization or low-degree polynomial-time recognition algorithm. We introduce a new class of 'adjusted interval digraphs'. By contrast, for these digraphs we exhibit a natural forbidden structure characterization, in terms of a novel structure which we call an 'invertible pair'. Our characterization also yields a low-degree polynomial-time recognition algorithm of adjusted interval digraphs. It turns out that invertible pairs are also useful for undirected interval graphs, and our result yields a new forbidden structure characterization of interval graphs. In fact, it can be shown to be a natural link proving the equivalence of some known characterizations of interval graphs the theorems of Lekkerkerker and Boland, and of Fulkerson and Gross. In addition, adjusted interval digraphs naturally arise in the context of list homomorphism problems. If H is a reflexive undirected graph, the list homomorphism problem LHOM(H) is polynomial if H is an interval graph, and NP-complete otherwise. If H is a reflexive digraph, LHOM(H) is polynomial if H is an adjusted interval graph, and we conjecture that it is also NP-complete otherwise. We show that our results imply the conjecture in two important cases. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Interval graphs Interval digraphs Adjusted interval digraphs Forbidden structure characterizations polynomial algorithms List homomorphism problems Dichotomy

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT OPTIMIZATION OF MONOTONIC FUNCTIONS ON TREES

引用

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS 1983年第4期4卷 512-516页

作者： PERL, Y SHILOACH, Y BAR ILAN UNIV RAMAT GAN ISRAEL IBM ISRAEL SCI CTR HAIFA ISRAEL

The problem of optimizing weighting functions over all the k-subtrees (subtrees with k vertices) of a given tree is considered. A general algorithm is presented that finds an optimal k-subtree of a given tree whenever the weighting function is what we call monotonic. Monotonicity is a very natural property, satisfied by most of the functions that one can think of.

关键词： optimal subtrees monotonic weighting functions dynamic programming polynomial algorithms NP completeness

来源：评论

学校读者我要写书评

暂无评论

Root-Squaring for Root-Finding 1

引用

25th International Workshop on Computer Algebra in Scientific Computing (CASC)

作者： Go, Soo Pan, Victor Y. Soto, Pedro CUNY Dept Comp Sci Lehman Coll Bronx NY 10468 USA CUNY PhD Programs Math & Comp Sci Grad Ctr New York NY 10016 USA Univ Oxford Math Inst Oxford England

ISBN: (数字)9783031417245

ISBN: (纸本)9783031417238;9783031417245

The root-squaring iterations of Dandelin (1826), Lobachevsky (1834), and Graffe (1837) recursively produce the coefficients of polynomials ph(x) whose zeros are the 2(h)th powers of the zeros of an input polynomial p(x) for h = 1, 2, 3,... The iterations have been the main tool for univariate polynomial root-finding in the 19th century and well beyond but became obsolete later because of severe numerical stability problems observed already in a few iterations. To circumvent this deficiency we apply root-squaring to Newton's Inverse Ratios p'(x)/p(x) and compute no coefficients of p(x) or ph(x) for h > 0, assuming that p(x) is a black box polynomial, represented by an oracle or subroutine for its evaluation rather than by its coefficients. Accordingly, our algorithm accelerates root-squaring for a polynomial p(x) that can be evaluated fast as well as for polynomial t(c,rho)(x) = p(x-c/rho) for a complex number c and a positive rho by performing root-squaring without computing the coefficients of t(c,rho)(x). Our extensive experiments demonstrate efficiency of application of our algorithms to estimation of extremal root radii, that is, the maximal and minimal distances from a point on the complex plane to the zeros of p(x). This is a well-known ingredient of various efficient polynomial root-finders, immediately extended to deciding whether a fixed disc on the complex plane contains any zero of p(x). The latter decision, called exclusion test for a disc, is the basic step of all efficient root-finders using subdivision iterations, in particular, of the recent polynomial root-finder by the second author, made nearly optimal due to a distinct application of root-squaring iterations.

关键词： Symbolic-numeric computing Root-finding polynomial algorithms Computer algebra

来源：评论

学校读者我要写书评

暂无评论

Degeneracy in interior point methods for linear programming: a survey

引用

Annals of Operations Research 1993年第1期46-47卷 107-138页

作者： Güler, O. den Hertog, D. Roos, C. Terlaky, T. Tsuchiya, T. Faculty of Technical Mathematics and Computer Science Delft University of Technology Delft 2600 GA P.O. Box 5031 Netherlands The Institute of Statistical Mathematics Tokyo 106 4-6-7 Minami-Azabu Minato-ku Japan

The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming. We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions. © 1993 J.C. Baltzer AG, Science Publishers.

关键词： basis recovery degeneracy global and local convergence interior point methods Linear programming numerical performance polynomial algorithms sensitivity analysis

来源：评论

学校读者我要写书评

暂无评论

Committee Selection with a Weight Constraint Based on a Pairwise Dominance Relation

Committee Selection with a Weight Constraint Based on a Pair...

引用

2nd International Conference on Algorithmic Decision Theory, ADT 2011

作者： Delort, Charles Spanjaard, Olivier Weng, Paul UPMC CNRS LIP6 UMR 7606 F-75005 Paris France

ISBN: (纸本)9783642248726

This paper is devoted to a knapsack problem with a cardinality constraint when dropping the assumption of additive representability [10]. More precisely, we assume that we only have a classification of the items into ordered classes. We aim at generating the set of preferred subsets of items, according to a pairwise dominance relation between subsets that naturally extends the ordering relation over classes [4,16]. We first show that the problem reduces to a multiobjective knapsack problem with cardinality constraint. We then propose two polynomial algorithms to solve it, one based on a multiobjective dynamic programming scheme and the other on a multiobjective branch and bound procedure. We conclude by providing numerical tests to compare both approaches.

关键词： Committee selection Ordinal combinatorial optimization Multiobjective combinatorial optimization Knapsack with cardinality constraint polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms

Interval graphs, adjusted interval digraphs, and reflexive l...

引用

4th Workshop on Graph Classes, Optimization, and Width Parameters (GROW)

关键词： Interval graphs Interval digraphs Adjusted interval digraphs Forbidden structure characterizations polynomial algorithms List homomorphism problems Dichotomy

来源：评论

学校读者我要写书评

暂无评论

Parallel machine problems with equal processing times: a survey

Parallel machine problems with equal processing times: a sur...

引用

Multidisciplinary International Scheduling Conference - Theory and Applications (MISTA)

作者： Kravchenko, Svetlana A. Werner, Frank Univ Magdeburg Fak Math D-39106 Magdeburg Germany United Inst Informat Problems Minsk 220012 BELARUS

The basic scheduling problem we are dealing with is the following. There are n jobs, each requiring an identical execution time. All jobs have to be processed on a set of parallel machines. Preemptions can be either allowed or forbidden. The aim is to construct a feasible schedule such that a given criterion is minimized. In this paper, we survey existing approaches for the problem class considered.

关键词： Parallel machine problem Equal processing times Non-preemptive problems Preemptive problems polynomial algorithms NP-hard problems

来源：评论

学校读者我要写书评

暂无评论

A simple but NP-hard Problem of Mixed-discrete Programming and its Solution by Approximate algorithms

引用

Optimization 1985年第5期16卷 705-714页

作者： Dempe, S. Technische Hochschule Karl-Marx-Stadt Sektion Mathematik DDR - 9010 PSF 964 Karl-Marx-Stadt Germany

A NP-hard problem (P) of mixed-discrete linear programming is considered which consists in the minimization of a linear objective function subject to a special nonconnected subset of an unbounded polymatroid. For this problem we describe three polynomial approximate algorithms including a greedy algorithm and a fully polynomial approximation scheme solving a special subproblem of (P). © 1985, Taylor & Francis Group, LLC. All rights reserved.

关键词： Approximate algorithms Fully polynomial approximation scheme Greedy algorithm Mixed-discrete programming polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimax regret p-center location on a network with demand uncertainty

引用

Location Science 1997年第4期5.0卷 247-254页

作者： Averbakh, I. Berman, Oded Mathematics Department MS-9063 Western Washington University Bellingham WA 98225-9063 United States Division of Management and Economics Scarborough Campus University of Toronto Scarborough Ont. M1C 1A4 Canada

We consider the weighted p-center problem on a transportation network with uncertain weights of nodes. Specifically, for each node, an interval estimate of its weight is known. The objective is to find the 'minimax regret' solution, i.e. to minimize the worst-case loss in the objective function that may occur because a decision is made without knowing which state of nature will take place. We discuss properties of the problem and show that the problem can be solved by means of solving (n+1) regular weighted p-center problems. This leads to polynomial algorithms for the cases where the regular weighted p-center problem can be solved in polynomial time, e.g. for the case of a tree network, and for the case of a general network with p=1.

关键词： robust optimization p -center problems polynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：