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

Minimizing total completion time on parallel machines with deadline constraints

SIAM JOURNAL ON COMPUTING 2003年第5期32卷 1370-1388页

作者： Leung, JYT Pinedo, M New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA NYU Stern Sch Business New York NY 10012 USA

Consider n independent jobs and m identical machines in parallel. Job j has a processing time p(j) and a deadline (d) over bar (j). It must complete its processing before or at its deadline. All jobs are available for processing at time t = 0 and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines;such a schedule is called a feasible schedule. Given a feasible set of jobs, our goal is to find a schedule that minimizes the total completion time SigmaC(j). In the classical alpha|beta|gamma scheduling notation this problem is referred to as P|prmt, (d) over bar (j)\SigmaC(j). Lawler (Recent Results in the Theory of Machine Scheduling, in Mathematical Programming: The State of the Art, A. Bachem, M. Grotschel, and B. Korte, eds., Springer, Berlin, 1982, pp. 202 - 234) raised the question of whether or not the problem is NP-hard. In this paper we present a polynomial-time algorithm for every m greater than or equal to 2, and we show that the more general problem with m unrelated machines, i.e., R | prmt, (d) over bar (j)\SigmaC(j), is strongly NP-hard.

关键词： parallel and identical machines unrelated machines total completion time deadline constraints preemptive scheduling maximum lateness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Sparse regular induced subgraphs in 2P₃-free graphs

引用

DISCRETE OPTIMIZATION 2013年第4期10卷 304-309页

作者： Lozin, Vadim V. Mosca, Raffaele Purcell, Christopher Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ G DAnnunzio Dipartimento Econ I-65127 Pescara Italy

We call graphs of a fixed degree k sparse regular graphs and their complements dense regular graphs. Recently, it was conjectured that finding a maximum regular induced subgraph H in a 2P(3)-free graph can be solved in polynomial time if and only if H is sparse. In the present paper, we prove the "sparse" part of this conjecture, i.e., we show that for each fixed k, the problem of finding a maximum k-regular induced subgraph in a 2P(3)-free graph can be solved in polynomial time. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Regular graph Induced subgraph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

ON QUADRATIC AND O(ROOT-N L) CONVERGENCE OF A PREDICTOR CORRECTOR algorithm FOR LCP

引用

MATHEMATICAL PROGRAMMING 1993年第3期62卷 537-551页

作者： YE, YY ANSTREICHER, K 1. Department of Management Sciences University of Iowa 52242 Iowa City IA USA

Recently several new results have been developed for the asymptotic (local) convergence of polynomial-time interior-point algorithms. It has been shown that the predictor-corrector algorithm for linear programming (LP) exhibits asymptotic quadratic convergence of the primal-dual gap to zero, without any assumptions concerning nondegeneracy, or the convergence of the iteration sequence. In this paper we prove a similar result for the monotone linear complementarity problem (LCP), assuming only that a strictly complementary solution exists. We also show by example that the existence of a strictly complementarity solution appears to be necessary to achieve superlinear convergence for the algorithm.

关键词： LINEAR COMPLEMENTARITY PROBLEM QUADRATIC PROGRAMMING SUPERLINEAR CONVERGENCE QUADRATIC CONVERGENCE polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the algorithmic inversion of the discrete Radon transform

引用

THEORETICAL COMPUTER SCIENCE 2002年第1-2期281卷 455-469页

作者： Gritzmann, P de Vries, S Tech Univ Munich Zentrum Math D-80333 Munich Germany

The present paper deals with the computational complexity of the discrete inverse problem of reconstructing finite point sets and more general functionals with finite support that are accessible only through some of the values of their discrete Radon transform. It turns out that this task behaves quite differently from its well-studied companion problem involving 1-dimensional X-rays. Concentrating on the case of coordinate hyperplanes in R-d and on functionals psi : Z(d) --> D with D is an element of {{0, 1,...,r}, N-0} for some arbitrary but fixed r, we show in particular that the problem can be solved in polynomial time if information is available for m such hyperplanes when m less than or equal to d - 1 but is NP-hard for m = d and D = {0, 1,...,r}. However, for D = N-0, a case that is relevant in the context of contingency tables, the problem is still in P. Similar results are given for the task of determining the uniqueness of a given solution and for a related counting problem. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： Radon transform discrete inverse problem discrete tomography contingency table computational complexity polynomial-time algorithm NP-hard

来源：评论

学校读者我要写书评

暂无评论

Induced Disjoint Paths in AT-free graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2022年 124卷 170-191页

作者： Golovach, Petr A. Paulusma, Daniel van Leeuwen, Erik Jan Univ Bergen Dept Informat PB 7803 N-5020 Bergen Norway Univ Durham Sch Engn & Comp Sci Sci Labs South Rd Durham DH1 3LE England Univ Utrecht Dept Informat & Comp Sci Princetonpl 5 NL-3584 CC Utrecht Netherlands

Paths P-1, ..., P-k are mutually induced if any two distinct P-i and P-j have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (s(i), t(i)) contains k mutually induced paths P-i such that each P-i connects s(i) and t(i). This problem is NP-complete even for k = 2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. Consequently, the problem of deciding if an AT-free graph contains a fixed graph H as an induced topological minor admits a polynomial-time algorithm. We show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard with parameter vertical bar V-H vertical bar, even for a subclass of AT-free graphs, namely cobipartite graphs. We also show that the problems k-IN-A-PATH and k-IN-A-TREE are polynomial-time solvable on AT-free graphs even if k is part of the input. (C) 2021 Elsevier Inc. All rights reserved.

关键词： Disjoint paths AT-free graph Co-bipartite graph polynomial-time algorithm W[1]-hardness Induced topological minor k-in-a-Path k-in-a-Tree

来源：评论

学校读者我要写书评

暂无评论

SOLVING THE MAXIMUM POPULAR MATCHING PROBLEM WITH MATROID CONSTRAINTS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2024年第3期38卷 2226-2242页

作者： Csaji, Gergely Kiraly, Tamas Yokoi, Yu Eotvos Lorand Univ Dept Operat Res Budapest Hungary HUN REN Ctr Econ & Reg Studies Mech Design Res Grp Budapest Hungary Eotvos Lorand Univ HUN REN ELTE Egervary Res Grp Dept Operat Res Budapest Hungary Tokyo Inst Technol Sch Comp Dept Math & Comp Sci Tokyo Japan

We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Kamiyama [Theoret. Comput. Sci., 809 (2020), pp. 265--276] and solved in the special case where matroids are base orderable. Utilizing a newly shown matroid exchange property, we show that the problem is tractable for arbitrary matroids. We further investigate a different notion of popularity, where the agents vote with respect to lexicographic preferences, and show that both existence and verification problems become coNP-hard even in the b-matching case.

关键词： matroid popular matching polynomial-time algorithm stable matching

来源：评论

学校读者我要写书评

暂无评论

Dominating induced matchings in graphs containing no long claw

引用

JOURNAL OF GRAPH THEORY 2018年第1期88卷 18-39页

作者： Hertz, Alain Lozin, Vadim Ries, Bernard Zamaraev, Viktor de Werra, Dominique Polytech Montreal Dept Math & Ind Engn CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Gerad CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Univ Warwick Math Inst Coventry W Midlands England Univ Fribourg Dept Informat Fribourg Switzerland Ecole Polytech Fed Lausanne Inst Math Lausanne Switzerland

An induced matching M in a graph G is dominating if every edge not in M shares exactly one vertex with an edge in M. The dominating induced matching problem (also known as efficient edge domination) asks whether a graph G contains a dominating induced matching. This problem is generally NP-complete, but polynomial-time solvable for graphs with some special properties. In particular, it is solvable in polynomial time for claw-free graphs. In the present article, we provide a polynomial-time algorithm to solve the dominating induced matching problem for graphs containing no long claw, that is, no induced subgraph obtained from the claw by subdividing each of its edges exactly once.

关键词： dominating induced matching graphs containing no long claw polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for evacuation problems in networks with a single sink of small degree and bounded capacitated edges

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第3期48卷 1-22页

作者： Higashikawa, Yuya Katoh, Naoki Teruyama, Junichi Tokuni, Yuki Univ Hyogo Kobe Japan

In this paper, we propose new algorithms for evacuation problems defined on dynamic flow networks. A dynamic flow network is a directed graph in which source nodes are given supplies and a single sink node is given a demand. The evacuation problem seeks a dynamic flow that sends all supplies from sources to the sink such that its demand is satisfied in the minimum feasible time horizon. For this problem, the current best algorithms are developed by Schl & ouml;ter (2018) and Kamiyama (2019), which run in strongly polynomial time but with high-order polynomial time complexity because they use submodular function minimization as a subroutine. In this paper, we propose new algorithms that do not explicitly execute submodular function minimization, and we prove that they are faster than the current best algorithms when an input network is restricted such that the sink has a small in-degree and every edge has the same capacity.

关键词： Dynamic flow Evacuation problem Quickest transshipment problem polynomial-time algorithm Base polytope

来源：评论

学校读者我要写书评

暂无评论

A solution to a conjecture on the generalized connectivity of graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第1期33卷 275-282页

作者： Chen, Lily Li, Xueliang Liu, Mengmeng Mao, Yaping Huaqiao Univ Sch Math Sci Quanzhou 362021 Peoples R China Nankai Univ Ctr Combinator Tianjin 300071 Peoples R China Nankai Univ LPMC TJKLC Tianjin 300071 Peoples R China Lanzhou Jiaotong Univ Dept Math Lanzhou 730070 Peoples R China Qinghai Normal Univ Dept Math Xining 810008 Qinghai Peoples R China

The generalized k-connectivity k(k) (G) of a graph G was introduced by Chartrand et al. in (Bull Bombay Math Colloq 2:1-6, 1984), which is a nice generalization of the classical connectivity. Recently, as a natural counterpart, Li et al. proposed the concept of generalized edge-connectivity for a graph. In this paper, we consider the computational complexity of the generalized connectivity and generalized edge-connectivity of a graph. We give a confirmative solution to a conjecture raised by S. Li in Ph.D. Thesis (2012). We also give a polynomial-time algorithm to a problem of generalized k-edge-connectivity.

关键词： Generalized connectivity Generalized edge-connectivity Complexity polynomial-time algorithm NP-complete

来源：评论

学校读者我要写书评

暂无评论

Best Match Graphs With Binary Trees

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2023年第3期20卷 1679-1690页

作者： Schaller, David Geiss, Manuela Hellmuth, Marc Stadler, Peter F. F. Max Planck Inst Math Sci D-04103 Leipzig Germany Univ Leipzig Interdisciplinary Ctr Bioinformat Dept Comp Sci Bioinformat Grp D-04107 Leipzig Germany Software Competence Ctr Hagenberg GmbH A-4232 Hagenberg Austria Stockholm Univ Fac Sci Dept Math SE-10691 Stockholm Sweden Univ Vienna Inst Theoret Chem A-1090 Vienna Austria Univ Nacl Colombia Fac Ciencias Sede Bogota Bogota 111321 Colombia Santa Fe Insitute Santa Fe NM 87501 USA

Best match graphs (BMG) are a key intermediate in graph-based orthology detection and contain a large amount of information on the gene tree. We provide a near-cubic algorithm to determine whether a BMG is binary-explainable, i.e., whether it can be explained by a fully resolved gene tree and, if so, to construct such a tree. Moreover, we show that all such binary trees are refinements of the unique binary-refinable tree (BRT), which in general is a substantial refinement of the also unique least resolved tree of a BMG. Finally, we show that the problem of editing an arbitrary vertex-colored graph to a binary-explainable BMG is NP-complete and provide an integer linear program formulation for this task.

关键词： Best match graphs binary trees rooted triple consistency polynomial-time algorithm NP-hardness integer linear program

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：