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

An improved algorithm for selecting p items with uncertain returns according to the minmax-regret criterion

MATHEMATICAL PROGRAMMING 2004年第2期100卷 345-353页

作者： Conde, E Univ Sevilla Fac Matemat E-41012 Seville Spain

We consider the problem of selecting a subset of p investments of maximum total return out of a set of n available investments with uncertain returns, where uncertainty is represented by interval estimates for the returns, and the minmax regret objective is used. We develop an algorithm that solves this problem in O(min{p,n-p}n) time. This improves the previously known complexity O(min{p,n-p}(2)n).

关键词： polynomial algorithm complexity robust optimization knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Good orientations of unions of edge-disjoint spanning trees

引用

JOURNAL OF GRAPH THEORY 2021年第4期96卷 594-618页

作者： Bang-Jensen, Jorgen Bessy, Stephane Huang, Jing Kriesell, Matthias Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Univ Montpellier Lab Informat Robot & Microelect Montpellier Montpellier France Univ Victoria Dept Math & Stat Victoria BC Canada Tech Univ Ilmenau Dept Math Ilmenau Germany

In this paper, we exhibit connections between the following subjects: Tree packing in graphs and digraphs (both behave completely different), the rigidity matroid of a graph, Henneberg moves on trees, the conjectures of Thomassen and Matthews and Sumner, and (s,t)-orderings of digraphs. We do this by studying graphs which admit acyclic orientations that contain an out-branching and in-branching which are arc-disjoint (such an orientation is calledgood). A2T-graphis a graph whose edge set can be decomposed into two edge-disjoint spanning trees. It is a well-known result due to Tutte and Nash-Williams, respectively, that every 4-edge-connected graph contains a spanning 2T-graph. Vertex-minimal 2T-graphs with at least two vertices which are known asgeneric circuitsplay an important role in rigidity theory for graphs. We prove that every generic circuit has a good orientation. Using this result we prove that ifGis 2T-graph whose vertex set has a partitionV1,V2, horizontal ellipsis ,Vkso that eachViinduces a generic circuitGiofGand the set of edges between differentGi's form a matching inG, thenGhas a good orientation. We also obtain a characterization for the case when the set of edges between differentGi's form adouble tree, that is, if we contract eachGito one vertex, and delete parallel edges we obtain a tree. All our proofs are constructive and imply polynomial algorithms for finding the desired good orderings and the pairs of arc-disjoint branchings which certify that the orderings are good. We identify a structure which can be used to certify that a given 2T-graph does not have a good orientation.

关键词： 2T-graph acyclic digraph acyclic orientation branchings generic circuit NP-complete problem polynomial algorithm rigidity matroid spanning trees vertex ordering

来源：评论

学校读者我要写书评

暂无评论

Polarity of chordal graphs

引用

DISCRETE APPLIED MATHEMATICS 2008年第13期156卷 2469-2479页

作者： Ekim, Tinaz Hell, Pavol Stacho, Juraj de Werra, Dominique Ecole Polytech Fed Lausanne ROSE CH-1015 Lausanne Switzerland Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, the existence of such a partition can be characterized by finitely many forbidden subgraphs, and hence tested in polynomial time. In this paper we address the question of polarity of chordal graphs, arguing that this is in essence a question of colourability, and hence chordal graphs are a natural restriction. We observe that there is no finite forbidden subgraph characterization of polarity in chordal graphs: nevertheless we present a polynomial time algorithm for polarity of chordal graphs. We focus oil a special case of polarity (called monopolarity) which turns Out to be the central concept for our algorithms. For the case of monopolar graphs, we illustrate the structure of all minimal obstructions;it turns out that they can all be described by it certain graph grammar, permitting our monopolarity algorithm to be cast as a certifying algorithm. (c) 2008 Elsevier B.V. All rights reserved.

关键词： chordal graph polar graph polynomial algorithm graph grammar matrix partition generalized colouring forbidden subgraph characterization

来源：评论

学校读者我要写书评

暂无评论

Relatively maximal perturbation bounds for global robustness of max-plus linear systems

引用

INTERNATIONAL JOURNAL OF ROBUST AND NONLINEAR CONTROL 2021年第9期31卷 4170-4183页

作者： Yin, Yingxuan Tao, Yuegang Wang, Cailu Hebei Univ Technol Sch Artificial Intelligence Tianjin Peoples R China Beijing Inst Technol Sch Automat Beijing Peoples R China

The perturbation bounds for the global robustness of max-plus linear systems are constructed, which guarantee that parameter perturbations within such bounds do not affect the original states and outputs. The eigenelement of a max-plus matrix is introduced to characterize the variable elements and to determine the maximal number of variable elements. The relatively maximal perturbation bound is proposed to describe the maximal variation range of system parameters. A polynomial algorithm is developed to find a relatively maximal perturbation bounds. The globally robust approach presented is applied in scheduling of container quay cranes to delimit the maximal traveling time delay.

关键词： container quay crane eigenelement global robustness max‐ plus linear system polynomial algorithm relatively maximal perturbation bound variable element

来源：评论

学校读者我要写书评

暂无评论

Precedence constrained parallel-machine scheduling of position-dependent jobs

引用

OPTIMIZATION LETTERS 2017年第7期11卷 1273-1281页

作者： Przybylski, Bartomiej Adam Mickiewicz Univ Fac Math & Comp Sci Ul Umultowska 87 PL-61614 Poznan Poland

We consider parallel-machine job scheduling problems with precedence constraints. Job processing times are variable and depend on positions of jobs in a schedule. The objective is to minimize the maximum completion time or the total weighted completion time. We specify certain conditions under which the problem can be solved by scheduling algorithms applied earlier for fixed job processing times.

关键词： Parallel-machine scheduling Variable job processing times Precedence constraints polynomial algorithm Maximum completion time Total weighted completion time

来源：评论

学校读者我要写书评

暂无评论

Blockers and antiblockers of stable matchings

引用

THEORETICAL COMPUTER SCIENCE 2014年第0期524卷 126-133页

作者： Eirinakis, Pavlos Magos, Dimitrios Mourtos, Loannis Athens Univ Econ & Business Dept Management Sci & Technol Athens 10434 Greece Technol Educ Inst Athens Dept Informat Egaleo 12210 Greece

An implicit linear description of the stable matching polytope is provided in terms of the blocker and antiblocker sets of constraints of the matroid-kernel polytope. The explicit identification of both these sets is based on a partition of the stable pairs in which each agent participates. Here, we expose the relation of such a partition to rotations. We provide a time-optimal algorithm for obtaining such a partition and establish some new related results;most importantly, that this partition is unique. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Stable matching Matroid-kernel Polytope polynomial algorithm Rotation

来源：评论

学校读者我要写书评

暂无评论

The competitive salesman problem on a network: a worst-case approach

引用

OPERATIONS RESEARCH LETTERS 2006年第2期34卷 165-174页

作者： Averbakh, I Lebedev, V Univ Toronto Div Management Scarborough ON M1C 1A4 Canada Volgograd State Univ Dept Math Volgograd 400062 Russia

We provide a complexity analysis of the problem of optimal routing of a server on a transportation network in the presence of a competing server. The server that reaches a node first gets the profit from the node. The... 详细信息

关键词： polynomial algorithm NP-hardness traveling salesman

来源：评论

学校读者我要写书评

暂无评论

Characterization of removable elements with respect to having k disjoint bases in a matroid

引用

DISCRETE APPLIED MATHEMATICS 2012年第16-17期160卷 2445-2451页

作者： Li, Ping Lai, Hong-Jian Liang, Yanting Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Beijing Jiaotong Univ Dept Math Beijing 100044 Peoples R China W Virginia Univ Dept Math Morgantown WV 26506 USA Univ Wisconsin Fond du Lac Dept Math Fond Du Lac WI 54935 USA

The well-known spanning tree packing theorem of Nash-Williams and Tutte characterizes graphs with k edge-disjoint spanning trees. Edmonds generalizes this theorem to matroids with k disjoint bases. For any graph G that may not have k-edge-disjoint spanning trees, the problem of determining what edges should be added to G so that the resulting graph has k edge-disjoint spanning trees has been studied by Haas (2002) [11] and Liu et al. (2009) [17], among others. This paper aims to determine, for a matroid M that has k disjoint bases, the set E-k(M) of elements in M such that for any e is an element of E-k(M), M-e also has k disjoint bases. Using the matroid strength defined by Catlin et al. (1992) [4], we present a characterization of E-k(M) in terms of the strength of M. Consequently, this yields a characterization of edge sets E-k(G) in a graph G with at least k edge-disjoint spanning trees such that for all e is an element of E-k(G), G-e also has k edge-disjoint spanning trees. polynomial algorithms are also discussed for identifying the set E-k(M) in a matroid M, or the edge subset E-k(G) for a connected graph G. (C) 2012 Published by Elsevier B.V.

关键词： Disjoint bases Edge-disjoint spanning trees Spanning tree packing numbers Strength Fractional arboricity polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Existence of an Integer Solution to the Relaxed Weber Problem for a Tree Network

引用

AUTOMATION AND REMOTE CONTROL 2019年第7期80卷 1288-1293页

作者： Panyukov, A. V. Natl Res Univ South Ural State Univ Chelyabinsk Russia

The problem of finding an optimal location of the vertices of a tree network in an assembly space representing a finite set is considered. The optimality criterion is the minimum total cost of location and communications in all points of this space. Different vertices of the tree can be located in a single point of the assembly space. This problem is well-known as the Weber problem. The representation of the Weber problem as a linear programming problem is given. It is proved that the set of all optimal solutions to the corresponding relaxed Weber problem for the tree network contains an integer solution. This fact can be used to improve the efficiency of algorithms for the problems differing from the Weber problem by the presence of additional constraints: it allows us to find the optimal value of the objective function, which in turn significantly reduces the complexity of calculating the optimal solution itself, e.g., by the branch-and-bound method.

关键词： location problem integer linear programming problem relaxed problem computational complexity polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

An Interior-Point algorithm for Linear Programming with Optimal Selection of Centering Parameter and Step Size

引用

Journal of the Operations Research Society of China 2021年第3期9卷 659-671页

作者： Ya-Guang Yang Nuclear Regulatory Commission Office of ResearchRockville 20850USA

For interior-point algorithms in linear programming,it is well known that the selection of the centering parameter is crucial for proving polynomiality in theory and for efficiency in ***,the selection of the centering parameter is usually by heuristics and separated from the selection of the line-search step *** heuristics are quite different while developing practically efficient algorithms,such as Mehrotra’s predictor–corrector(MPC)algorithm,and theoretically efficient algorithms,such as short-step path-following *** introduces a dilemma that some algorithms with the best-known polynomial bound are least efficient in practice,and some most efficient algorithms may not be convergent in polynomial ***,in this paper,we propose a systematic way to optimally select the centering parameter and linesearch step size at the same time,and we show that the algorithm based on this strategy has the best-known polynomial bound and may be very efficient in computation for real problems.

关键词： Interior-point method Convergence polynomial algorithm Linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：