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

Decreasing minimization on M-convex sets: algorithms and applications

MATHEMATICAL PROGRAMMING 2022年第1-2期195卷 1027-1068页

作者： Frank, Andras Murota, Kazuo Eotvos Lorand Univ Dept Operat Res MTA ELTE Egervary Res Grp Pazmany P S 1-C H-1117 Budapest Hungary Tokyo Metropolitan Univ Dept Econ & Business Adm Tokyo 1920397 Japan Inst Stat Math Tokyo 1908562 Japan

This paper is concerned with algorithms and applications of decreasing minimization on an M-convex set, which is the set of integral elements of an integral base-polyhedron. Based on a recent characterization of decreasingly minimal (dec-min) elements, we develop a strongly polynomial algorithm for computing a dec-min element of an M-convex set. The matroidal feature of the set of dec-min elements makes it possible to compute a minimum cost dec-min element, as well. Our second goal is to exhibit various applications in matroid and network optimization, resource allocation, and (hyper)graph orientation. We extend earlier results on semi-matchings to a large degree by developing a structural description of dec-min in-degree bounded orientations of a graph. This characterization gives rise to a strongly polynomial algorithm for finding a minimum edge-cost dec-min orientation.

关键词： Network flows Resource allocation Graph orientation Decreasing minimization M-convex set polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

An efficient arc-search interior-point algorithm for convex quadratic programming with box constraints

引用

NUMERICAL algorithmS 2022年第2期91卷 711-748页

作者： Yang, Yaguang US NRC Off Res 11555 Rockville Pike Rockville MD 20852 USA

This paper proposes an arc-search interior-point algorithm for convex quadratic programming with box constraints. The problem has many applications, such as optimal control with actuator saturation. It is shown that an explicit feasible starting point exists for this problem. Therefore, an efficient feasible interior-point algorithm is proposed to tackle the problem. It is proved that the proposed algorithm is polynomial and has the best known complexity bound O (root nlog(1/is an element of). Moreover, the search neighborhood for this special problem is wider than an algorithm for general convex quadratic programming problems, which implies that longer steps and faster convergence are expected. Finally, an engineering design problem is considered and the algorithm is applied to solve the engineering problem.

关键词： Arc-search Interior-point method Convex quadratic programming polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

On the feasibility of solutions to the split delivery vehicle routing problem represented as edge variables

引用

OPERATIONS RESEARCH LETTERS 2025年 58卷

作者： de Araujo, Daniel de Araujo, Daniel Uchoa, Eduardo Univ Fed Fluminense Rua Passo Patria 156 BR-24210240 Niteroi RJ Brazil

Mixed integer programming formulations for the Split Delivery Vehicle Routing Problem (SDVRP) typically use edge decision variables. It was believed that feasibility couldn't be verified in polynomial time. We show that this recognition problem depends on the formulation's constraints and prove that it's strongly NP-hard for a recent formulation. With subtour elimination constraints, we provide an O(n log n)-time recognition algorithm. This challenges assumptions about edge-based formulations and provides new insights into SDVRP solution verification complexity.

关键词： Split delivery Vehicle routing polynomial algorithm Edge formulation

来源：评论

学校读者我要写书评

暂无评论

List 3-Coloring Graphs with No Induced P6 + rP3

引用

algorithmICA 2021年第1期83卷 216-251页

作者： Chudnovsky, Maria Huang, Shenwei Spirkl, Sophie Zhong, Mingxian Princeton Univ Princeton NJ 08544 USA Nankai Univ Tianjin 300350 Peoples R China Univ Waterloo Waterloo ON Canada CUNY Lehman Coll New York NY 10016 USA CUNY Grad Ctr New York NY 10016 USA

For an integer t, we let P t denote the t-vertex path. We write H + G for the disjoint union of two graphs H and G, and for an integer r and a graph H, we write rH for the disjoint union of r copies of H. We say that a graph G is H-free if no induced subgraph of G is isomorphic to the graph H. In this paper, we study the complexity of k-coloring, for a fixed integer k, when restricted to the class of H-free graphs with a fixed graph H. We provide a polynomial-time algorithm to test if, for fixed r, a (P-6 + rP(3))-free is three-colorable, and find a coloring if one exists. We also solve the list version of this problem, where each vertex is assigned a list of possible colors, which is a subset of {1, 2, 3}. This generalizes results of Broersma, Golovach, Paulusma, and Song, and results of Klimosova, Malik, Masarik, Novotna, Paulusma, and Slivova. Our proof uses a result of Ding, Seymour, and Winkler relating matchings and hitting sets in hypergraphs. We also prove that the problem of deciding if a (P 5 + P 2)-free graph has a k-coloring is NP-hard for every fixed k >= 5.

关键词： Graph coloring Forbidden induced subgraph polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Location problems with continuous demand and unreliable facilities: Applications of families of incremental Voronoi diagrams

引用

DISCRETE APPLIED MATHEMATICS 2021年 300卷 36-55页

作者： Averbakh, Igor Berman, Oded Kalcsics, Jorg Krass, Dmitry Univ Toronto Scarborough Dept Management 1265 Mil Trail Toronto ON M1C 1A4 Canada Univ Toronto Rotman Sch Management 105 St George St St George ON M5E 3E6 Canada Univ Edinburgh Sch Math Peter Guthrie Tait Rd Edinburgh EH9 3FD Midlothian Scotland

We consider conditional facility location problems with unreliable facilities that can fail with known probabilities. The demand is uniformly distributed over a convex polygon in the rectilinear plane where a number of facilities are already present, and it is required to optimally locate another facility. We analyze properties of the exponential family of incremental Voronoi diagrams associated with possible realizations of the set of operational facilities, and, based on this analysis, present polynomial algorithms for three conditional location problems. The approach can be extended to various other conditional location problems with continuous demand and unreliable facilities, under different probabilistic models including ones with correlated facility failures. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Reliable facility location Continuous location Voronoi diagram 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A new split-based hybrid metaheuristic for the reconfigurable transfer line balancing problem

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2021年第4期59卷 1127-1144页

作者： Lahrichi, Y. Grangeon, N. Deroussi, L. Norre, S. CNRS LIMOS UMR 6158 Aubiere France

We consider the Reconfigurable Transfer Line Balancing Problem. This problem consists of allocating a set of operations (necessary to machine a single part) to different workstations placed into a serial line. Each workstation can contain multiple machines operating in parallel. The machines considered are mono-spindle head CNC machines which may imply sequence-dependent setup times between operations in order to perform tool changes. Therefore, the operations allocated to a workstation should be sequenced. Besides, accessibility, inclusion, exclusion and precedence constraints between operations are considered. In this article, we propose a polynomial exact algorithm that balances the transfer line provided the overall sequence of the operations (called 'giant sequence') is given. We use this algorithm to solve the balancing problem when the overall sequence of operations is not fixed by embedding it in a metaheuristic framework. We perform experimentation on literature instances. The results obtained show the effectiveness of the proposed approach compared to literature.

关键词： split algorithm metaheuristic balancing transfer line setup time polynomial algorithm sequencing

来源：评论

学校读者我要写书评

暂无评论

Connected max cut is polynomial for graphs without the excluded minor K5\e

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第4期40卷 869-875页

作者： Chaourar, Brahim Imam Mohammad Ibn Saud Islamic Univ IMSIU POB 90950 Riyadh 11623 Saudi Arabia

Given a graph G = (V, E), a connected cut delta(U) is the set of edges of E linking all vertices of U to all vertices of V\U such that the induced subgraphs G[U] and G[V\U] are connected. Given a positive weight function w defined on E, the connected maximum cut problem (CMAX CUT) is to find a connected cut Omega such that w(Omega) is maximum among all connected cuts. CMAX CUT is NP-hard even for planar graphs, and thus for graph without the excluded minor K-5. In this paper, we prove that CMAX CUT is polynomial for the class of graphs without the excluded minor K-5\e, denoted by G(K-5\e). We deduce two quadratic time algorithms: one for the minimum cut problem in G( K-5\e) without computing the maximum flow, and another one for Hamilton cycle problem in the class of graphs without the two excluded minors the prism P-6 and K-3,K-3. This latter problem is NP-complete for maximal planar graphs.

关键词： Max cut Connected max cut polynomial algorithm Min cut Graphs without the excluded minor K-5\e Hamilton cycle problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：