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

Separable standard quadratic optimization problems

OPTIMIZATION LETTERS 2012年第5期6卷 857-866页

作者： Bomze, Immanuel M. Locatelli, Marco Univ Vienna Vienna Austria Univ Parma I-43100 Parma Italy

A standard quadratic optimization problems (StQP) asks for the minimal value of a quadratic form over the standard simplex. StQPs form a central NP-hard class in quadratic optimization and have numerous practical applications. In this note we study the case of a separable objective function and propose an algorithm of worst-case complexity . Some extensions to multi-StQPs and a"" (1)-ball constrained problems are also addressed briefly.

关键词： Standard quadratic optimization polynomial-time algorithm Multi-standard quadratic optimization

来源：评论

学校读者我要写书评

暂无评论

"Almost-stable" matchings in the Hospitals/Residents problem with Couples

引用

CONSTRAINTS 2017年第1期22卷 50-72页

作者： Manlove, David F. McBride, Iain Trimble, James Univ Glasgow Sch Comp Sci Sir Alwyn Williams Bldg Glasgow G12 8QQ Lanark Scotland

The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even in the highly restricted case that each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then present the first Integer Programming (IP) and Constraint Programming (CP) models for min bp hrc. Finally, we discuss an empirical evaluation of these models applied to randomly-generated instances of min bp hrc. We find that on average, the CP model is about 1.15 times faster than the IP model, and when presolving is applied to the CP model, it is on average 8.14 times faster. We further observe that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.

关键词： Most-stable matching Blocking pair polynomial-time algorithm NP-hardness Integer programming model Constraint programming model Empirical evaluation

来源：评论

学校读者我要写书评

暂无评论

"Almost stable" matchings in the Roommates problem with bounded preference lists

引用

THEORETICAL COMPUTER SCIENCE 2012年 432卷 10-20页

作者： Biro, Peter Manlove, David F. McDermid, Eric J. Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland Hungarian Acad Sci Inst Econ Budapest Hungary 21st Century Technol Inc Austin TX 78730 USA

An instance of the classical Stable Roommates problem need not admit a stable matching. Previous work has considered the problem of finding a matching that is "as stable as possible", i.e., admits the minimum number of blocking pairs. It is known that this problem is NP-hard and not approximable within n(1/2-epsilon), for any epsilon > 0, unless P = NP, where n is the number of agents in a given instance. In this paper, we extend the study to the Stable Roommates problem with Incomplete lists. In particular, we consider the case that the lengths of the lists are bounded by some integer d. We show that, even if d = 3, there is some c > 1 such that the problem of finding a matching with the minimum number of blocking pairs is not approximable within c unless P = NP. On the other hand, we show that the problem is solvable in polynomial time ford <= 2, and we give a (2d - 3)-approximation algorithm for fixed d >= 3. If the given lists satisfy an additional condition (namely the absence of a so-called elitist odd party - a structure that is unlikely to exist in general), the performance guarantee improves to 2d - 4. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Stable Roommates problem Blocking pairs APX-hardness polynomial-time algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Finding a shortest even hole in polynomial time

引用

JOURNAL OF GRAPH THEORY 2022年第3期99卷 425-434页

作者： Cheong, Hou-Teng Lu, Hsueh-, I Natl Taiwan Univ Dept Comp Sci & Informat Engn 1 Roosevelt RdSect 4 Taipei 106 Taiwan

An even (respectively, odd) hole in a graph is an induced cycle with even (respectively, odd) length that is at least four. Bienstock proved that detecting an even (respectively, odd) hole containing a given vertex is NP-complete. Conforti, Cornuejols, Kapoor, and Vuskovic gave the first known polynomial-time algorithm to determine whether a graph contains even holes. Chudnovsky, Kawarabayashi, and Seymour estimated that Conforti et al.'s algorithm runs in O ( n 40 ) time on an n-vertex graph and reduced the required time to O ( n 31 ). Subsequently, da Silva and Vuskovic, Chang and Lu, and Lai, Lu, and Thorup improved the time to O ( n 19 ), O ( n 11 ), and O ( n 9 ), respectively. The tractability of determining whether a graph contains odd holes has been open for decades until the algorithm of Chudnovsky, Scott, Seymour, and Spirkl that runs in O ( n 9 ) time, which Lai et al. also reduced to O ( n 8 ). By extending Chudnovsky et al.'s techniques for detecting odd holes, Chudnovsky, Scott, and Seymour (respectively) ensured the tractability of finding a long (respectively, shortest) odd hole. They also ensured the NP-hardness of finding a longest odd hole, whose reduction also works for finding a longest even hole. Recently, Cook and Seymour ensured the tractability of finding a long even hole. An intriguing missing piece is the tractability of finding a shortest even hole, left open for 16 years by, for example, Chudnovsky et al. and Johnson. We resolve this open problem by augmenting Chudnovsky et al.'s even-hole detection algorithm into the first known polynomial-time algorithm, running in O ( n 31 ) time, for finding a shortest even hole in an n-vertex graph that contains even holes.

关键词： data structure induced subgraph polynomial-time algorithm shortest even hole

来源：评论

学校读者我要写书评

暂无评论

polynomial-time Feasibility Condition for Multiclass Aircraft Sequencing on a Single-Runway Airport

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2011年第1期12卷 2-14页

作者： Harikiopoulo, Dimitri Neogi, Natasha Univ Illinois Dept Aeronaut & Aerosp Urbana IL 61801 USA

In this paper, we consider the airport-landing problem of scheduling different types of aircraft on a single runway. Since the minimum allowable landing separation time between two consecutive aircraft depends on the relative weight of both aircraft, this is a state-dependent scheduling problem, which, in the general case, is NP-hard. We attempt to modify the aircraft landing sequence from the traditionally used "first-come-first-served" (FCFS) order to be able to land more aircraft in a given period of time. Given a set of planes, the goal is to find a sequence such that no plane can land before it is actually available for landing, the minimum safety separation between two consecutive planes is always satisfied, and the total landing time (makespan) is minimized. Based on the Federal Aviation Administration (FAA) partition of aircraft into weight categories, our algorithm provides a polynomial-time feasibility condition for scheduling a set of planes in a given time interval. It ensures that the Aircraft Scheduling Problem (ASP) presented earlier is not NP-complete and allows us to develop possible practical real-time air traffic control (ATC) execution policies.

关键词： Aircraft-landing problem polynomial-time algorithm state-dependent scheduling

来源：评论

学校读者我要写书评

暂无评论

Reconstructing Phylogenetic Level-1 Networks from Nondense Binet and Trinet Sets

引用

algorithmICA 2017年第1期77卷 173-200页

作者： Huber, Katharina T. van Iersel, Leo Moulton, Vincent Scornavacca, Celine Wu, Taoyang Univ East Anglia Sch Comp Sci Norwich Norfolk England Delft Univ Technol Delft Inst Appl Math Delft Netherlands Univ Montpellier CNRS ISEM Montpellier France Inst Biol Computat Montpellier France

Binets and trinets are phylogenetic networks with two and three leaves, respectively. Here we consider the problem of deciding if there exists a binary level-1 phylogenetic network displaying a given set T of binary binets or trinets over a taxon set X, and constructing such a network whenever it exists. We show that this is NP-hard for trinets but polynomial-time solvable for binets. Moreover, we show that the problem is still polynomial-time solvable for inputs consisting of binets and trinets as long as the cycles in the trinets have size three. Finally, we present an O(3(vertical bar X vertical bar) poly(vertical bar X vertical bar)) time algorithm for general sets of binets and trinets. The latter two algorithms generalise to instances containing level-1 networks with arbitrarily many leaves, and thus provide some of the first supernetwork algorithms for computing networks from a set of rooted phylogenetic networks.

关键词： Phylogenetic tree Phylogenetic network polynomial-time algorithm Exponential-time algorithm NP-hard Supernetwork Trinet Aho algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved formulation and efficient heuristics for the discrete parallel-machine makespan ScheLoc problem

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 140卷 106238-106238页

作者： Wang, Shijin Wu, Ruochen Chu, Feng Yu, Jianbo Liu, Xin Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China Univ Paris Saclay Univ Evry Lab IBISC F-91025 Evry France Fuzhou Univ Sch Econ & Management Fuzhou 350116 Peoples R China Tongji Univ Sch Mech Engn Shanghai 200092 Peoples R China Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China

The scheduling-location (ScheLoc) problem is a new and interesting field, which is a combination of two complex problems: the machine-location problem and the scheduling problem. Owing to the NP-hardness of both the component problems, the ScheLoc problem is naturally NP-hard. This study investigates a deterministic and discrete parallel-machine ScheLoc problem for minimizing the makespan. A new mixed integer programming formulation based on network flow problems is proposed. Two formulation-based heuristics are developed for small-scale problems. Subsequently, a polynomial-time heuristic is designed for efficiently solving large-scale problems. Extensive computational experiments are conducted for 1450 benchmark problem instances with different scales. The computational results show that our model can solve more problem instances to optimality than that in Healer and Deghdak (2017) in the same time limit. In addition, the heuristics can yield near-optimal solutions for small-scale problems in a short time. The polynomial-time algorithm outperforms most of the state-of-the-art methods for the large-scale problems in terms of both the efficiency and solution quality.

关键词： Scheduling-location (ScheLoc) problem Discrete location Mixed integer programming formulation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Satgraphs and independent domination. Part 1

引用

THEORETICAL COMPUTER SCIENCE 2006年第1-3期352卷 47-56页

作者： Zverovich, IE Rutgers State Univ RUTCOR Rutgers Ctr Operat Res Piscataway NJ 08854 USA

A graph G is called a satgraph if there exists a partition A boolean OR B = V(G) such that A induces a clique [possibly, A = 0], B induces a matching [i.e., G(B) is a 1-regular subgraph, possibly, B = 0], and there are no triangles (a, b, b'), where alpha epsilon A and b, b' epsilon B. We also introduce the hereditary closure of Y A J, denoted by H Y A J [hereditary satgraphs]. The class H Y A J contains split graphs. In turn, H Y A J is contained in the class of all (1, 2)-split graphs [A. Gyarfas, Generalized split graphs and Ramsey numbers, J. Combin. Theory Ser. A 81 (2) (1998) 255-261], the latter being still not charactefized. We characterize satgraphs in terms of forbidden induced subgraphs. There exist close connections between satgraphs and the satisfiability problem [SAT]. In fact, SAT is linear-time equivalent to finding the independent domination number in the corresponding satgraph. It follows that the independent domination problem is NP-complete for the hereditary satgraphs. In particular, it is NP-complete for perfect graphs. (c) 2005 Elsevier B.V. All rights reserved.

关键词： satgraphs satisfiability problem hereditary class of graphs forbidden induced subgraph characterization independent domination problem polar graphs perfect graphs NP-complete polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

D0L sequence equivalence is in P for fixed alphabets

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2008年第2期42卷 361-374页

作者： Ruohonen, Keijo Tampere Univ Technol Inst Math FIN-33101 Tampere Finland

A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and ... 详细信息

关键词： D0L system equivalence problem polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

RECOGNIZING MAX-FLOW MIN-CUT PATH MATRICES

引用

OPERATIONS RESEARCH LETTERS 1988年第1期7卷 37-42页

作者： HARTVIGSEN, DB WAGNER, DK PURDUE UNIV SCH IND ENGNW LAFAYETTEIN 47907

Seymour has introduced a class of matrices for which the polyhedron { x | Ax ≥ 1, x ≥ 0} has all integral extreme points. T main result of this paper is a polynomial-time algorithm for determining whether a given ma... 详细信息

关键词： matroids maximum-flow problem polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：