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

CLOSEDNESS OF INTEGER HULLS OF SIMPLE CONIC SETS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2016年第1期30卷 70-99页

作者： Moran, Diego A. Dey, Santanu S. Virginia Polytech Inst & State Univ Dept Ind & Syst Engn Blacksburg VA 24061 USA Univ Adolfo Ibanez Sch Business Diagonal Las Torres 2640 Santiago Chile Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

Let C be a full-dimensional pointed closed convex cone in R-m obtained by taking the conic hull of a strictly convex set. Given A is an element of Q(mxn1), B is an element of Q(mxn2), and b is an element of Q(m), a simple conic mixed-integer set (SCMIS) is a set of the form {(x, y) is an element of Z(n1) x R-n2 vertical bar Ax + By - b is an element of C}. In this paper, we give a complete characterization of the closedness of convex hulls of SCMISs. Under certain technical conditions on the cone C, we show that the closedness characterization can be used to construct a polynomial-time algorithm to check the closedness of convex hulls of SCMISs. Moreover, we also show that the Lorentz cone satisfies these technical conditions. In the special case of pure integer problems, we present sufficient conditions, which can be checked in polynomial time, to verify the closedness of intersection of SCMISs.

关键词： closedness polynomial-time algorithm mixed-integer convex programming

来源：评论

学校读者我要写书评

暂无评论

Identification of the anchor points in FDH models

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第3期246卷 936-943页

作者： Soleimani-damaneh, Majid Mostafaee, Amin Univ Tehran Coll Sci Sch Math Stat & Comp Sci Tehran Iran Islamic Azad Univ Tehran North Branch Dept Math Coll Sci Tehran Iran

This paper investigates the anchor points in nonconvex Data Envelopment Analysis (DEA), called Free Disposal Hull (FDH), technologies. We develop the concept of anchor points under various returns to scale as-sumptions in FDH models. A necessary and sufficient condition for characterizing the anchor points is provided. Since the set of anchor points is a subset of the set of extreme units, a definition of extreme units in non-convex technologies as well as a new method for obtaining these units are given. Finally, a polynomial-time algorithm for identification of the anchor points in FDH models is provided. Obtaining both extreme units and anchor points is done via calculating only some ratios, without solving any mathematical programming problem. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

关键词： Data Envelopment Analysis (DEA) FDH models Anchor point Returns to scale polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Convex optimisation-based joint channel and power allocation scheme for orthogonal frequency division multiple access networks

引用

IET COMMUNICATIONS 2015年第1期9卷 28-32页

作者： Liu, Peng Li, Jiandong Li, Hongyan Meng, Yun Xidian Univ State Key Lab ISN Xian 710071 Shaanxi Peoples R China Xidian Univ Inst Informat Sci Xian 710071 Shaanxi Peoples R China

This study concerns joint channel and power allocation scheme for multi-user orthogonal frequency division multiple access system. The author's highlight is margin adaptive (MA) resource allocation problem namely minimising the total transmit power of users with rate requirement constraints. MA is generally provable NP-hard;the typical methods are either to relax and round, or to fix the transmission mode of users (e.g. modulation and coding). Differently, they reorganise MA problem with only power variables left and design a novel relaxation scheme to enable the convexity. The polynomial-time algorithm-interior-point method-is employed to solve the relaxation problem and the theoretical complexity is further presented. Simulation results demonstrate that the author's scheme can provide high energy efficiency compared with the existing methods, 100% relative error bounds with respect to the optimum in most cases, and low computational complexity.

关键词： OFDM modulation frequency division multiple access channel allocation convex programming constraint theory radio access networks communication complexity joint channel and power allocation scheme multiuser orthogonal frequency division multiple access system margin adaptive resource allocation problem rate requirement constraints NP-hard problem MA problem power variables relaxation scheme polynomial-time algorithm relative error bounds computational complexity convex optimisation multiple access networks interior point method

来源：评论

学校读者我要写书评

暂无评论

Two disjoint shortest paths problem with non-negative edge length

引用

OPERATIONS RESEARCH LETTERS 2019年第1期47卷 66-69页

作者： Kobayashi, Yusuke Sako, Ryo Kyoto Univ Kyoto Japan Univ Tsukuba Tsukuba Ibaraki Japan

In the two disjoint shortest paths problem (2-DSPP), the input is a graph (or a digraph) and its vertex pairs (s(1), t(1)) and (S-2, t(2)), and the objective is to find two vertex-disjoint paths P-1 and P-2 such that P-i is a shortest path from s(i) to t(i) for i = 1, 2, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Disjoint paths Shortest path polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

COUNTING THE NUMBER OF MINIMUM CUTS IN UNDIRECTED MULTIGRAPHS

引用

IEEE TRANSACTIONS ON RELIABILITY 1991年第5期40卷 610-614页

作者： NAGAMOCHI, H SUN, Z IBARAKI, T TOYOHASHI UNIV TECHNOL DEPT INFORMAT & COMP SCITOYOHASHI 441JAPAN

The problem of counting the number of cuts with the minimum cardinality in an undirected multigraph arises in various applications such as testing the super-lambda-ness of a graph and calculating upper and lower bounds on the probabilistic connectedness of a stochastic graph G in which edges are subject to failure. This paper shows that the number \C(G)\ of cuts with the minimum cardinality lambda(G) in a multiple graph G = (V, E) can be computed in O(\E\ + lambda(G)\V\2 + lambda(G)\C(G) parallel-to V\) time.

关键词： UNDIRECTED GRAPH MULTIGRAPH EDGE-CONNECTIVITY MINIMUM CUT polynomial-time algorithm SPANNING FOREST SPANNING SUBGRAPH EDGE CONTRACTION SUPER-LAMBDA

来源：评论

学校读者我要写书评

暂无评论

Graph Bipartization Problem with Applications to Via Minimization in VLSI Design

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2023年第4期34卷 347-361页

作者： Lin, Lan Lin, Yixun Tongji Univ Sch Elect & Informat Engn Shanghai 200092 Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Peoples R China

The bipartization problem for a graph G asks for finding a subset S of V(G) such that the induced subgraph G[S] is bipartite and vertical bar S vertical bar is maximized. This problem has significant applications in the via minimization of VLSI design. The problem has been proved NP-complete and the fixed parameter solvability has been known in the literature. This paper presents several polynomial-time algorithms for special graph families, such as split graphs, co-bipartite graphs, chordal graphs, and permutation graphs.

关键词： Bipartite induced subgraph odd-cycle transversal via minimization VLSI design polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Vertex and edge covers with clustering properties: Complexity and algorithms

引用

JOURNAL OF DISCRETE algorithmS 2009年第2期7卷 149-167页

作者： Fernau, Henning Manlove, David F. Univ Trier FB Abt Informat 4 D-54286 Trier Germany Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland

We consider the concepts of a t-total vertex cover and a t-total edge cover (t >= 1), which generalise the notions of a vertex cover and an edge cover, respectively. A t-total vertex (respectively edge) cover of a connected graph G is a vertex (edge) cover S of G such that each connected component of the subgraph of G induced by S has at least t vertices (edges). These definitions are motivated by combining the concepts of clustering and covering in graphs. Moreover they yield a spectrum of parameters that essentially range from a vertex cover to a connected vertex cover (in the vertex case) and from an edge cover to a spanning tree (in the edge case). For various values of t, we present NP-completeness and approximability results (both upper and lower bounds) and FPT algorithms for problems concerned with finding the minimum size of a t-total vertex cover, t-total edge cover and connected vertex cover, in particular improving on a previous FPT algorithm for the latter problem. (C) 2008 Elsevier B. V. All rights reserved.

关键词： t-total vertex cover Connected vertex cover t-total edge cover polynomial-time algorithm NP-completeness Approximation algorithm FPT algorithm

来源：评论

学校读者我要写书评

暂无评论

HEURISTIC algorithm FOR FINDING THE MAXIMUM INDEPENDENT SET

引用

CYBERNETICS AND SYSTEMS ANALYSIS 2012年第5期48卷 673-680页

作者： Plotnikov, A. D. Volodymyr Dahl East Ukraine Natl Univ Minist Educ & Sci Youth & Sport Ukraine Lugansk Ukraine

A heuristic algorithm is developed for finding the maximum independent set of vertices in an undirected graph. To this end, the technique of finite partially ordered sets is used, in particular, the technique of partitioning such a set into a minimum number of chains. A special digraph is constructed and a solution algorithm is proposed on the basis of a hypothesis about its properties. Some experimental data are presented for well-known examples.

关键词： heuristic algorithm maximum independent set clique NP-hard NP-complete class NP polynomial-time algorithm finite partially ordered set

来源：评论

学校读者我要写书评

暂无评论

String noninclusion optimization problems

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 1998年第3期11卷 456-467页

作者： Rubinov, AR Timkovsky, VG Natl Transport Inst Moscow Russia Russian Acad Sci Econ Forecasting Inst Dept Comp Sci Moscow 117418 Russia

For every string inclusion relation there are two optimization problems: find a longest string included in every string of a given finite language, and find a shortest string including every string of a given finite language. As an example, the two well-known pairs of problems, the longest common substring (or subsequence) problem and the shortest common superstring (or supersequence) problem, are interpretations of these two problems. In this paper we consider a class of opposite problems connected with string noninclusion relations: find a shortest string included in no string of a given finite language and find a longest string including no string of a given finite language. The predicate "string alpha is not included in string beta" is interpreted as either "alpha is not a substring of beta" or "alpha is not a subsequence of beta". The main purpose is to determine the complexity status of the string noninclusion optimization problems. Using graph approaches we present polynomial-time algorithms for the first interpretation and NP-hardness proofs for the second. We also discuss restricted versions of the problems, correlations between the string inclusion and noninclusion problems, and generalized problems which are the string inclusion problems for one language and the string noninclusion problems for another. In applications the string inclusion problems are used to find a similarity between any structures which can be represented by strings. Respectively, the noninclusion problems can be used to find a nonsimilarity. Such problems occur in computational molecular biology, data compression, pattern recognition, and flexible manufacturing. The above generalized problems arise naturally in all of these applied areas. Apart from this practical reason, we hope that studying the string noninclusion problems will yield deeper understanding of the string inclusion problems.

关键词： string inclusion longest shortest common subsequence substring supersequence superstring polynomial-time algorithm NP-hard problem

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time deterministic approach to the travelling salesperson problem

引用

INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS 2020年第4期35卷 454-460页

作者： Jazayeri, Ali Sayama, Hiroki Drexel Univ Coll Comp & Informat Philadelphia PA 19104 USA SUNY Binghamton Dept Syst Sci & Ind Engn Binghamton NY USA

We propose a new polynomial-time deterministic algorithm that produces an approximated solution for the travelling salesperson problem. The proposed algorithm ranks cities based on their priorities calculated using a power function of means and standard deviations of their distances from other cities and then connects the cities to their neighbours in the order of their priorities. When connecting a city, a neighbour is selected based on their neighbours' priorities calculated as another power function that additionally includes their distance from the focal city to be connected. This repeats until all the cities are connected into a single loop. The time complexity of the proposed algorithm is O(n(2)), where n is the number of cities. Numerical evaluation shows that, despite its simplicity, the proposed algorithm produces shorter tours with less time complexity than other conventional tour construction heuristics. The proposed algorithm can be used by itself or as an initial tour generator for other more complex heuristic optimisation algorithms.

关键词： Travelling salesperson problem polynomial-time algorithm deterministic algorithm approximation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：