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

Size versus stability in the marriage problem

THEORETICAL COMPUTER SCIENCE 2010年第16-18期411卷 1828-1841页

作者： Biro, Peter Manlove, David F. Mittal, Shubham Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland Indian Inst Technol Dept Comp Sci & Engn New Delhi 110016 India

Given an instance I of the classical Stable Marriage problem with Incomplete preference lists (SMI), a maximum cardinality matching can be larger than a stable matching. In many large-scale applications of SMI, we seek to match as many agents as possible. This motivates the problem of finding a maximum cardinality matching in I that admits the smallest number of blocking pairs (so is "as stable as possible"). We show that this problem is NP-hard and not approximable within n(1-epsilon), for any epsilon > 0, unless P = NP, where n is the number of men in I. Further, even if all preference lists are of length at most 3, we show that the problem remains NP-hard and not approximable within delta, for some delta > 1. By contrast, we give a polynomial-time algorithm for the case where the preference lists of one sex are of length at most 2. We also extend these results to the cases where (i) preference lists may include ties, and (ii) we seek to minimize the number of agents involved in a blocking pair. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Stable marriage problem Stable matching Blocking pair Blocking agent Inapproximability result polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A unified approach for scheduling with convex resource consumption functions using positional penalties

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2010年第2期206卷 301-312页

作者： Leyvand, Yaron Shabtay, Dvir Steiner, George McMaster Univ DeGroote Sch Business Operat Management Area Hamilton ON Canada Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n(3)) time. Furthermore, we show how the unified model can housed repeatedly as a subroutine to solve all problems from the second group in O(n(4)) time. In addition, we also show that faster algorithms exist for several special cases. Crown Copyright (C) 2010 Published by Elsevier B.V. All rights reserved.

关键词： Single machine scheduling Controllable processing times Resource allocation Due date assignment Positional penalties polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL TRIANGULATIONS OF POINTS AND SEGMENTS WITH STEINER POINTS

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2010年第1期20卷 89-104页

作者： Aronov, Boris Asano, Tetsuo Funke, Stefan NYU Dept Comp & Informat Sci Polytech Inst Brooklyn NY USA JAIST Sch Informat Sci Tokyo Japan Ernst Moritz Arndt Univ Greifswald Dept Math & Comp Sci D-17487 Greifswald Germany

Consider a set X of points in the plane and a set E of non-crossing segments with endpoints in X. One can efficiently compute the triangulation of the convex hull of the points, which uses X as the vertex set, respects E, and maximizes the minimum internal angle of a triangle. In this paper we consider a natural extension of this problem: Given in addition a Steiner point p, determine the optimal location of p and a triangulation of X boolean OR {p} respecting E, which is best among all triangulations and placements of p in terms of maximizing the minimum internal angle of a triangle. We present a polynomial- time algorithm for this problem and then extend our solution to handle any constant number of Steiner points.

关键词： Computational geometry constrained Delaunay triangulation polynomial-time algorithm Steiner point triangulation Voronoi diagram geometric optimization

来源：评论

学校读者我要写书评

暂无评论

The College Admissions problem with lower and common quotas

引用

THEORETICAL COMPUTER SCIENCE 2010年第34-36期411卷 3136-3153页

作者： Biro, Peter Fleiner, Tamas Irving, Robert W. Manlove, David F. Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland Budapest Univ Technol & Econ Dept Comp Sci & Informat Theory H-1117 Budapest Hungary

We study two generalised stable matching problems motivated by the current matching scheme used in the higher education sector in Hungary. The first problem is an extension of the College Admissions problem in which the colleges have lower quotas as well as the normal upper quotas. Here, we show that a stable matching may not exist and we prove that the problem of determining whether one does is NP-complete in general. The second problem is a different extension in which, as usual, individual colleges have upper quotas, but, in addition, certain bounded subsets of colleges have common quotas smaller than the sum of their individual quotas. Again, we show that a stable matching may not exist and the related decision problem is NP-complete. On the other hand, we prove that, when the bounded sets form a nested set system, a stable matching can be found by generalising, in non-trivial ways, both the applicant-oriented and college-oriented versions of the classical Gale-Shapley algorithm. Finally, we present an alternative view of this nested case using the concept of choice functions, and with the aid of a matroid model we establish some interesting structural results for this case. (C) 2010 Elsevier B.V. All rights reserved.

关键词： College Admissions problem Hospitals/Residents problem Lower quotas Common quotas Nested set systems NP-hardness polynomial-time algorithm Matroids Rural Hospitals theorem

来源：评论

学校读者我要写书评

暂无评论

INDEPENDENT SETS OF MAXIMUM WEIGHT IN APPLE-FREE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第1期24卷 239-254页

作者： Brandstaedt, Andreas Lozin, Vadim V. Mosca, Raffaele Univ Rostock Inst Informat D-18051 Rostock Germany Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ G DAnnunzio Dipartimento Sci I-65121 Pescara Italy

We present the first polynomial-time algorithm to solve the maximum weight independent set problem for apple-free graphs, which is a common generalization of several important classes where the problem can be solved efficiently, such as claw-free graphs, chordal graphs, and cographs. Our solution is based on a combination of two algorithmic techniques (modular decomposition and decomposition by clique separators) and a deep combinatorial analysis of the structure of apple-free graphs. Our algorithm is robust in the sense that it does not require the input graph G to be apple-free;the algorithm either finds an independent set of maximum weight in G or reports that G is not apple-free.

关键词： maximum independent set clique separators modular decomposition polynomial-time algorithm claw-free graphs apple-free graphs

来源：评论

学校读者我要写书评

暂无评论

引用

JOURNAL OF DISCRETE algorithmS 2010年第2期8卷 102-116页

作者： Sng, Colin T. S. Manlove, David F. Univ Glasgow Dept Comp Sci Glasgow G12 8QQ Lanark Scotland

We consider the problem of finding a popular matching in the Weighted Capacitated House Allocation problem (WCHA). An instance of WCHA involves a set of agents and a set of houses. Each agent has a positive weight indicating his priority, and a preference list in which a subset of houses are ranked in strict order. Each house has a capacity that indicates the maximum number of agents who could be matched to it. A matching M of agents to houses is popular if there is no other matching M' such that the total weight of the agents who prefer their allocation in M to that in M exceeds the total weight of the agents who prefer their allocation in M to that in M'. Here, we give an O(root Cn1 + m) algorithm to determine if an instance of WCHA admits a popular matching, and if so, to find a largest such matching, where C is the total capacity of the houses, n(1) is the number of agents, and m is the total length of the agents' preference lists. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Popular matching problem Priorities Strict preference lists Maximum popular matching polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

THE k-IN-A-PATH PROBLEM FOR CLAW-FREE GRAPHS

THE <i>k</i>-IN-A-PATH PROBLEM FOR CLAW-FREE GRAPHS

引用

27th International Symposium on Theoretical Aspects of Computer Science (STACS)

作者： Fiala, Jiri Kaminski, Marcin Lidicky, Bernard Paulusma, Daniel Charles Univ Prague Fac Math & Phys DIMATIA Malostranske Nam 2-25 CR-18000 Prague Czech Republic Inst Theoret Comp Sci ITI CR-18000 Prague Czech Republic Univ Libre Bruxelles Dept Comp Sci B-1050 Brussels Belgium Univ Durham Dept Comp Sci Sci Labs Durham DH1 3LE England

Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k = 3. We show how to solve this problem in polynomial time on claw-free graphs, when k is no... 详细信息

ISBN: (纸本)9783939897163

关键词： induced path claw-free graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Deciding k-Colorability of P ₅-Free Graphs in polynomial time

引用

algorithmICA 2010年第1期57卷 74-81页

作者： Hoang, Chinh T. Kaminski, Marcin Lozin, Vadim Sawada, Joe Shu, Xiao Wilfrid Laurier Univ Waterloo ON N2L 3C5 Canada Rutgers State Univ RUTCOR Piscataway NJ 08854 USA Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ Guelph Guelph ON N1G 2W1 Canada

The problem of computing the chromatic number of a P (5)-free graph (a graph which contains no path on 5 vertices as an induced subgraph) is known to be NP-hard. However, we show that for every fixed integer k, there exists a polynomial-time algorithm determining whether or not a P (5)-free graph admits a k-coloring, and finding one, if it does.

关键词： Graph coloring Dominating clique polynomial-time algorithm P(5)-free graph

来源：评论

学校读者我要写书评

暂无评论

Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability

Metric Extension Operators, Vertex Sparsifiers and Lipschitz...

引用

2010 IEEE 51st Annual Symposium on Foundations of Computer Science

作者： Makarychev, Konstantin Makarychev, Yury IBM TJ Watson Res Ctr Yorktown Hts NY 10598 USA Toyota Technol Inst Chicago IL USA

ISBN: (纸本)9780769542447

We study vertex cut and flow sparsifiers that were recently introduced by Moitra [23], and Leighton and Moitra [18]. We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k / log log k) cut and flow sparsifiers, matching the best known existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log(2) k / log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomial-time algorithm for finding optimal operators. We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1950s. Using this connection, we obtain a lower bound of Omega(root log k / log log k) for flow sparsifiers and a lower bound of Omega(root log k / log log k) for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist (O) over tilde(root log k) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than (Omega) over tilde(root log k) would imply a negative answer to this question.

关键词： Banach spaces Banach spaces Lipschitz extendability algorithmic upper bound computational complexity flow sparsifiers functional analysis functional analysis linear metric extension operators linear operators lipschitz extendability minimum metric extensions optimal operators polynomial-time algorithm vertex cut vertex sparsifiers

来源：评论

学校读者我要写书评

暂无评论

On the complexity of the Eulerian closed walk with precedence path constraints problem

引用

Electronic Notes in Discrete Mathematics 2010年第C期36卷 899-906页

作者： Kerivin, H.L.M. Lacroix, M. Mahjoub, A.R. Department of Mathematical Sciences Clemson University Clemson SC 29634 O-326 Martin Hall United States Université Paris-Dauphine LAMSADE 75775 Paris Cedex 16 Place du Maréchal de Lattre de Tassigny France

The Eulerian closed walk problem in a digraph is a well-known polynomial-time solvable problem. In this paper, we show that if we impose the feasible solutions to fulfill some precedence constraints specified by paths of the digraph, then the problem becomes NP-complete. We also present a polynomial-time algorithm to solve this variant of the Eulerian closed walk problem when the paths are arc-disjoint. We also give necessary and sufficient conditions for the existence of feasible solutions in this polynomial-time solvable case. © 2010 Elsevier B.V.

关键词： Eulerian closed walk NP-completeness polynomial-time algorithm Precedence path constraints

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：