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

algorithms for the joint multitasking scheduling and common due date assignment problem

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2017年第20期55卷 6052-6066页

作者： Liu, Ming Wang, Shijin Zheng, Feifeng Chu, Chengbin Tongji Univ Sch Econ & Management Shanghai Peoples R China Donghua Univ Glorious Sun Sch Business & Management Shanghai Peoples R China Univ Paris Saclay Lab Genie Ind Cent Supelec Chatenay Malabry France

In this paper, we investigate a joint multitasking scheduling and common due date assignment problem on a single machine, for which examples can be found in product delivery process in logistics. Multitasking allows the machine to perform multiple tasks. The multitasking phenomenon has been observed in various practical domains, including manufacturing and administration. In multitasking settings, each waiting job interrupts a currently in-processing job, causing an interruption time and a switching time. In common due date assignment problems, the objective is to determine the optimal value of this due date with the purpose of minimising a total penalty function, which is associated with service quality. For the problem with general interruption functions, analytical properties are obtained to reduce the search space of the optimal solutions. For the cases with linear interruption functions, we develop a polynomial-time algorithm. Numerical experiments have been conducted to validate the efficiency of our proposed algorithm. Computational results also demonstrate an interesting phenomenon that in some cases, the optimal solutions under multitasking are superior to the counterparts without multitasking. Besides, we also devise a mixed integer programme for the cases with linear interruption function.

关键词： scheduling common due date assignment multitasking scheduling mixed integer programming polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas

引用

MATHEMATICS OF OPERATIONS RESEARCH 2017年第1期42卷 238-255页

作者： Yokoi, Yu Univ Tokyo Dept Math Informat Tokyo 1138656 Japan

Classified stable matching, proposed by Huang, describes a matching model between academic institutes and applicants, in which each institute has upper and lower quotas on classes, i.e., subsets of applicants. Huang showed that the problem to decide whether there exists a stable matching or not is NP-hard in general. On the other hand, he showed that the problem is solvable if classes form a laminar family. For this case, Fleiner and Kamiyama gave a concise interpretation in terms of matroids and showed the lattice structure of stable matchings. In this paper we introduce stable matchings on generalized matroids, extending the model of Fleiner and Kamiyama. We design a polynomial-time algorithm which finds a stable matching or reports the nonexistence. We also show that the set of stable matchings, if nonempty, forms a lattice with several significant properties. Furthermore, we extend this structural result to the polyhedral framework, which we call stable allocations on generalized polymatroids.

关键词： stable matching lower quotas matroids generalized polymatroids polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient domination for classes of P₆-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2017年 223卷 15-27页

作者： Brandstaedt, Andreas Eschen, Elaine M. Friese, Erik Karthick, T. Univ Rostock Fachbereich Informat A Einstein Str 22 D-18051 Rostock Germany West Virginia Univ Lane Dept CSEE Morgantown WV 26506 USA Univ Rostock Fachbereich Math Ulmenstr 69 D-18057 Rostock Germany Indian Stat Inst Comp Sci Unit Chennai Ctr Madras 600113 Tamil Nadu India

In a finite undirected graph G, a vertex dominates itself and all its neighbors in G. A vertex set D is an efficient dominating set (e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be NP-complete even for very restricted graph classes such as P-7-free chordal graphs;its complexity was an open question for P-6-free graphs and was open even for the subclass of P-6-free chordal graphs. Recently, Lokshtanov et al., and independently, Brandstadt and Mosca showed that ED is solvable in polynomial time for P-6-free graphs. The ED problem on a graph G can be reduced to the Maximum Weight Independent Set problem on the square of G. In this paper, we show that squares of P-6-free chordal graphs that have an e.d. are chordal;this, even holds for the larger class of (P-6, house, hole, domino)-free graphs. Thus, ED/WeightedED is solvable in polynomial time for (P-6, house, hole, domino)-free graphs, and in particular, for P-6-free chordal graphs. Also, the time bound achieved for ED on this class is much better than in the P-6-free case. Moreover, we show that squares of P-6-free graphs that have an e.d. are hole-free. Based on this result, we show that ED is solvable in polynomial time for (P-6, net)-free graphs;again, the time bound for ED on this class is much better than in the P-6-free case. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Efficient domination P-6-free graphs Chordal graphs Hole-free graphs (House, hole, domino)-free graphs polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

The Complexity of the Vertex 3-Colorability Problem for Some Hereditary Classes Defined By 5-Vertex Forbidden Induced Subgraphs

引用

GRAPHS AND COMBINATORICS 2017年第4期33卷 1009-1022页

作者： Malyshev, D. S. Natl Res Univ Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia

We completely determine the complexity status of the vertex 3-colorability problem for the problem restricted to all hereditary classes defined by at most 3 forbidden induced subgraphs each on at most 5 vertices. We also present a complexity dichotomy for the problem and the family of all hereditary classes defined by forbidding an induced bull and any set of induced subgraphs each on at most 5 vertices.

关键词： Vertex 3-colorability problem Computational complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Vertex coloring of graphs with few obstructions

引用

DISCRETE APPLIED MATHEMATICS 2017年第Part1期216卷 273-280页

作者： Lozin, V. V. Malyshev, D. S. Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Natl Res Univ Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia

We study the vertex coloring problem in classes of graphs defined by finitely many forbidden induced subgraphs. Of our special interest are the classes defined by forbidden induced subgraphs with at most 4 vertices. For all but three classes in this family we show either NP-completeness or polynomial-time solvability of the problem. For the remaining three classes we prove fixed-parameter tractability. Moreover, for two of them we give a 3/2 approximation polynomial algorithm. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Vertex coloring polynomial-time algorithm Fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

Pooling Problems with polynomial-time algorithms

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2016年第2期170卷 591-615页

作者： Haugland, Dag Hendrix, Eligius M. T. Univ Bergen Dept Informat Bergen Norway Univ Malaga Dept Comp Architecture Malaga Spain Wageningen Univ Operat Res & Logist Grp Wageningen Netherlands

The computational challenge offered by many traditional network flow models is modest, and large-scale instances can be solved fast. When the composition of the flow is part of the model, the required computation time may increase substantially. This is in particular true for the pooling problem, where the relative content of certain flow components is restricted. Flow entering the network at the source nodes has a given composition, whereas the composition in other nodes is determined by the composition of entering flows. At the network terminals, the flow composition is subject to restrictions referred to as quality constraints. The pooling problem is known to be strongly NP-hard, even if the network has only one pool, but is solvable in polynomial time if also the number of terminals or the number of quality parameters (flow components) is bounded. The problem is also NP-hard if there are only two sources and terminals and only one quality parameter. Two related questions have been left open in the literature so far. For the single-pool version, it has not been known whether the problem is solvable in polynomial time if the number of sources is bounded. For the version with a single quality parameter and two sources and terminals, the question whether a pseudo-polynomial algorithm exists has been open. This paper gives positive answers to both questions.

关键词： Pooling problem Complexity Global optimization polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

A polynomially solvable case of the pooling problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2017年第3期67卷 621-630页

作者： Boland, Natashia Kalinowski, Thomas Rigterink, Fabian Georgia Inst Technol Atlanta GA 30332 USA Univ Newcastle Callaghan NSW Australia

Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomial time by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border between (strongly) NP-hard and polynomially solvable cases of the pooling problem.

关键词： Pooling problem Computational complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

polynomial fixed-parameter algorithms: A case study for longest path on interval graphs

引用

THEORETICAL COMPUTER SCIENCE 2017年 689卷 67-95页

作者： Giannopoulou, Archontia C. Mertzios, George B. Niedermeier, Rolf TU Berlin Inst Softwaretech & Theoret Informat Berlin Germany Univ Durham Sch Engn & Comp Sci Durham England

We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomial time. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: LONGEST PATH, that is, given an undirected graph, find a maximum-length path in G. LONGEST PATH is NP-hard in general but known to be solvable in O (n(4)) time on n-vertex interval graphs. We show how to solve LONGEST PATH ON INTERVAL GRAPHS, parameterized by vertex deletion number k to proper interval graphs, in 0 (k(9)n) time. Notably, LONGEST PATH is trivially solvable in linear time on proper interval graphs, and the parameter value k can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis may enable a refined understanding of efficiency aspects for polynomial-time solvable problems similarly to what classical parameterized complexity analysis does for NP-hard problems. (C) 2017 Elsevier B.V. All rights reserved.

关键词： polynomial-time algorithm Longest path problem Interval graphs Proper interval vertex deletion set Data reduction Fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

AWeighted Linear Matroid Parity algorithm 2017

AWeighted Linear Matroid Parity Algorithm

引用

49th Annual ACM-SIGACT Symposium on Theory of Computing (STOC)

作者： Iwata, Satoru Kobayashi, Yusuke Univ Tokyo Tokyo 1138656 Japan Univ Tsukuba Tsukuba Ibaraki 3058573 Japan

ISBN: (纸本)9781450345286

The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Lovasz (1980) showed that this problem admits a minmax formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. In this paper, we present a combinatorial, deterministic, polynomialtime algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann (1986) for the unweighted problem.

关键词： Linear matroid parity matching polynomial-time algorithm Pfaf-fian primal-dual approach

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：