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

Proceedings of the Eighteenth Computing: The Australasian Theory Symposium - Volume 128

作者： Naonori Kakimura Mizuyo Takamatsu University of Tokyo Tokyo Japan Chuo University Tokyo Japan

ISBN: (纸本)9781921770098

Given an undirected graph G = (V, E) and a directed graph D = (V, A), the master/slave matching problem is to find a matching of maximum cardinality in G such that for each arc (u, v) ε A with u being matched, v is also matched. This problem is known to be NP-hard in general, but polynomially solvable in a special case where the maximum size of a connected component of D is at most *** paper investigates the master/slave matching problem in terms of delta-matroids, which is a generalization of matroids. We first observe that the above polynomially solvable constraint can be interpreted as delta-matroids. We then introduce a new class of matching problem with delta-matroid constraints, which can be solved in polynomial time. In addition, we discuss our problem with additional constraints such as capacity constraints.

关键词： mixed matrix theory polynomial-time algorithm constrained matching delta-matroid

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

On the complexity of the dominating induced matching problem in hereditary classes of graphs

引用

DISCRETE APPLIED MATHEMATICS 2011年第7期159卷 521-531页

作者： Cardoso, Domingos M. Korpelainen, Nicholas Lozin, Vadim V. Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ Aveiro Dept Matemat P-3810193 Aveiro Portugal

The DOMINATING INDUCED MATCHING problem, also known as EFFICIENT EDGE DOMINATION, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a "boundary" separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Dominating induced matching Efficient edge dominating set polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Constructing the Simplest Possible Phylogenetic Network from Triplets

引用

algorithmICA 2011年第2期60卷 207-235页

作者： van Iersel, Leo Kelk, Steven Univ Canterbury Dept Math & Stat Christchurch 1 New Zealand CWI NL-1090 GB Amsterdam Netherlands

A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing so-called reticulations such as recombinations, hybridizations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network with smallest possible level in time O(|T| (k+1)), if k is a fixed upper bound on the level of the network.

关键词： Phylogenetics polynomial-time algorithm Phylogenetic networks Triplets Minimising reticulations

来源：评论

学校读者我要写书评

暂无评论

On the asymptotic optimality of an algorithm for solving the maximum m-PSP in a multidimensional Euclidean space

引用

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS 2011年第1-Sup期272卷 1-13页

作者： Baburin, A. E. Gimadi, E. Kh Russian Acad Sci Sobolev Inst Math Siberian Branch Novosibirsk 630090 Russia

An efficient algorithm A with a guaranteed error estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman tours) of maximum weight in a complete weighted undirected graph in a multidimensional Euclidean space a"e (k) . The time complexity of the algorithm is O(n (3)). The number of traveling salesman tours for which the algorithm is asymptotically optimal is established.

关键词： maximum traveling salesman problem edge-disjoint Hamiltonian circuits polynomial-time algorithm asymptotic optimality multidimensional Euclidean space

来源：评论

学校读者我要写书评

暂无评论

polynomial-time algorithms for scheduling problem for coupled-tasks in presence of treatment tasks

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 647-654页

作者： Simonin, G. Giroudeau, R. König, J.-C. LIRMM UMR 5056 34392 Montpellier Cedex 5 161 rue Ada France

We consider the problem to schedule n coupled-tasks in presence of treatment tasks. This work is motivated by the problem of data acquisition for a torpedo. In such context, we developp a O(nlog(n)) polynomial-time al... 详细信息

关键词： Coupled-tasks Matching polynomial-time algorithm Scheduling

来源：评论

学校读者我要写书评

暂无评论

Cooperative project scheduling with controllable processing times: a game theory framework

Cooperative project scheduling with controllable processing ...

引用

16th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA)

作者： Briand, Cyril Billaut, Jean-Charles Univ Toulouse LAAS CNRS F-31077 Toulouse 4 France

ISBN: (纸本)9781457700187

This paper considers a project-scheduling environment assuming that the activities of the project network are distributed among a set of actors (or agents). Activity durations are modeled as time intervals and are controllable, meaning that every actor is allowed to shorten the duration of some activities by adding extra-money. For performing the project, actors have to collaborate with each other intending to satisfy a desired project duration. In this work, every actor's payoff corresponds to a given ratio of the total customer's payment, which itself depends on the ability of the actors to achieve the project in time, provided daily penalty costs are applied in case of tardiness. This problem can be modeled as a game, where players (actors) have to select a strategy (a duration vector for their activities) intending to maximize their profit. In this paper, the focus is put on the modeling of this project game, and on the connections between various decision problems, arising either in decision or game theory. We also study the particular case where each activity is assigned to one specific agent and a polynomial-time algorithm is proposed for finding Nash equilibrium with the smallest project makespan.

关键词： Computer crashes Context Gold Job shop scheduling Nash equilibrium Nash equilibrium computational complexity controllable processing time cooperative project scheduling duration vector game theory game theory penalty cost polynomial-time algorithm project

来源：评论

学校读者我要写书评

暂无评论

How to Play Unique Games against a Semi-Random Adversary Study of Semi-Random Models of Unique Games

How to Play Unique Games against a Semi-Random Adversary Stu...

引用

52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS)

作者： Kolla, Alexandra Makarychev, Konstantin Makarychev, Yury Microsoft Research United States IBM Research United States TTIC United States

ISBN: (纸本)9780769545714

In this paper, we study the average case complexity of the Unique Games problem. We propose a semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable instance of Unique Games, then she chooses an epsilon-fraction of all edges, and finally replaces ("corrupts") the constraints corresponding to these edges with new constraints. If all steps are adversarial, the adversary can obtain any (1 - epsilon)-satisfiable instance, so then the problem is as hard as in the worst case. We show however that we can find a solution satisfying a (1 - delta) fraction of all constraints in polynomial-time if at least one step is random (we require that the average degree of the graph is (Omega) over tilde (log k)). Our result holds only for epsilon less than some absolute constant. We prove that if epsilon >= 1/2, then the problem is hard in one of the models, that is, no polynomial-time algorithm can distinguish between the following two cases: (i) the instance is a (1 - epsilon)-satisfiable semi-random instance and (ii) the instance is at most delta-satisfiable (for every delta > 0);the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1 - epsilon)-satisfiable. We present an algorithm that distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1 -delta)-satisfiable instances if epsilon > c delta (for some absolute constant c).

关键词： Approximation algorithms Approximation methods Games Mathematical model polynomials Vectors computability computational complexity game theory graph theory graph theory polynomial-time algorithm semirandom adversary semirandom unique game models

来源：评论

学校读者我要写书评

暂无评论

Keeping partners together: algorithmic results for the hospitals/residents problem with couples

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2010年第3期19卷 279-303页

作者： McDermid, Eric J. Manlove, David F. Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland

The Hospitals/Residents problem with Couples (HRC) is a generalisation of the classical Hospitals/Residents problem (HR) that is important in practical applications because it models the case where couples submit joint preference lists over pairs of hospitals (h (i) ,h (j) ). We consider a natural restriction of HRC in which the members of a couple have individual preference lists over hospitals, and the joint preference list of the couple is consistent with these individual lists in a precise sense. We give an appropriate stability definition and show that, in this context, the problem of deciding whether a stable matching exists is NP-complete, even if each resident's preference list has length at most 3 and each hospital has capacity at most 2. However, with respect to classical (Gale-Shapley) stability, we give a linear-time algorithm to find a stable matching or report that none exists, regardless of the preference list lengths or the hospital capacities. Finally, for an alternative formulation of our restriction of HRC, which we call the Hospitals/Residents problem with Sizes (HRS), we give a linear-time algorithm that always finds a stable matching for the case that hospital preference lists are of length at most 2, and where hospital capacities can be arbitrary.

关键词： Stable matching problem NP-completeness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A Fast algorithm for the Path 2-Packing Problem

引用

THEORY OF COMPUTING SYSTEMS 2010年第1期46卷 59-79页

作者： Babenko, Maxim A. Moscow MV Lomonosov State Univ Dept Mech & Math Moscow 119991 Russia

Let G be an undirected graph and T = {T-1,..., T-k} be a collection of disjoint subsets of nodes. Nodes in T-1 boolean OR ... boolean OR T-k are called terminals, other nodes are called inner. By a T-path we mean a path P such that P connects terminals from distinct sets in T and all internal nodes of P are inner. We study the problem of finding a maximum cardinality collection P of T-paths such that at most two paths in P pass through any node. Our algorithm is purely combinatorial and has the time complexity O(mn(2)), where n and m denote the numbers of nodes and edges in G, respectively.

关键词： Path packing T-paths polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：