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

Multiechelon Lot Sizing: New Complexities and Inequalities

OPERATIONS RESEARCH 2020年第2期68卷 534-551页

作者： Zhao, Ming Zhang, Minjiao Univ Delaware Lerner Coll Business & Econ Newark DE 19716 USA Kennesaw State Univ Michael J Coles Coll Business Dept Econ Finance & Quantitat Anal Kennesaw GA 30144 USA

We study a multiechelon lot-sizing problem for a serial supply chain that consists of a production level and several transportation levels, where the demands can exist in the production echelon as well as in any transportation echelons. With the presence of stationary production capacity and general cost functions, our model integrates production, inventory, and transportation decisions and generalizes existing literature on many multiechelon lot-sizing models. First, we answer an open question in the literature by showing that multiechelon lot sizing with intermediate demands (MIS) is NP-hard. Second, we develop polynomial time algorithms for both uncapacitated and capacitated MIS with a fixed number of echelons. The run times of our algorithms improve on those of many known algorithms for different MIS models. Third, we present families of valid inequalities for MIS that generalize known inequalities. For the uncapacitated case, we develop a polynomial-time separation algorithm and efficient separation heuristics. Finally, we demonstrate the effectiveness of a branch-and-cut algorithm using proposed inequalities to solve large multi-item MIS problems.

关键词： lot sizing dynamic programming network flow polynomial-time algorithms valid inequalities

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling of proportional-linearly deteriorating jobs with positional due indices

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2020年第2期18卷 177-196页

作者： Chen, Rubing Yuan, Jinjiang Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

In this paper, we study the scheduling of proportional-linearly deteriorating jobs with positional due indices, release dates, deadlines and precedence relations on a single machine. The scheduling criteria studied in this paper include the makespan, maximum lateness, maximum tardiness, maximum flow time, maximum weighted completion time, maximum scheduling cost, total completion time, and the number of tardy jobs. By applying Lawler's rule and Smith's rule, polynomially solvable problems are processed by using two unified methods. We also present some new NP-hardness results when processing times of the jobs have no deterioration. Our results generalize a series of known achievements in the literature.

关键词： Single-machine scheduling Deteriorating jobs Due indices NP-hard polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring k-path Vertex Covers 14th

Reconfiguring k-path Vertex Covers

引用

14th International Conference and Workshops on algorithms and Computation (WALCOM)

作者： Hoang, Duc A. Suzuki, Akira Yagita, Tsuyoshi Kyushu Inst Technol Fukuoka Japan Tohoku Univ Sendai Miyagi Japan

ISBN: (纸本)9783030398811;9783030398804

A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The k-Path Vertex Cover Reconfiguration (k-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of k-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k = 2, known as the Vertex Cover Reconfiguration (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes including planar graphs, bounded bandwidth graphs, chordal graphs, and bipartite graphs, can be extended for k-PVCR. In particular, we prove a complexity dichotomy for k-PVCR on general graphs: on those whose maximum degree is 3 (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is 2 (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for k-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

关键词： Combinatorial Reconfiguration Computational complexity k-path vertex cover PSPACE-completeness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Bribery and Control in Stable Marriage 13th

Bribery and Control in Stable Marriage

引用

13th International Symposium on Algorithmic Game Theory (SAGT)

作者： Boehmer, Niclas Bredereck, Robert Heeger, Klaus Niedermeier, Rolf TU Berlin Algorithm & Computat Complex Berlin Germany

ISBN: (纸本)9783030579807;9783030579791

We initiate the study of external manipulations in STABLE MARRIAGE by considering several manipulative actions as well as several "desirable" manipulation goals. For instance, one goal is to make sure that a given pair of agents is matched in a stable solution, and this may be achieved by the manipulative action of reordering some agents' preference lists. We present a comprehensive study of the computational complexity of all problems arising in this way. We find several polynomial-time solvable cases as well as NP-hard ones. For the NP-hard cases, focusing on the natural parameter "budget" (that is, the number of manipulative actions), we also perform a parameterized complexity analysis and encounter parameterized hardness results.

关键词： Stable matching Matching markets Manipulation Strategic behavior polynomial-time algorithms Parameterized hardness

来源：评论

学校读者我要写书评

暂无评论

Strongly Stable and Maximum Weakly Stable Noncrossing Matchings 31st

Strongly Stable and Maximum Weakly Stable Noncrossing Matchi...

引用

31st International Workshop on Combinatorial algorithms (IWOCA)

作者： Hamada, Koki Miyazaki, Shuichi Okamoto, Kazuya NTT Corp 3-9-11 Midori Cho Musashino Tokyo 1808585 Japan Kyoto Univ Grad Sch Informat Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan Kyoto Univ Acad Ctr Comp & Media Studies Sakyo Ku Yoshida Honmachi Kyoto 6068501 Japan Kyoto Univ Hosp Div Med Informat Technol & Adm Planning Sakyo Ku 54 Kawaharacho Kyoto 6068507 Japan

ISBN: (纸本)9783030489656;9783030489663

In IWOCA 2019, Ruangwises and Itoh introduced stable noncrossing matchings, where participants of each side are aligned on each of two parallel lines, and no two matching edges are allowed to cross each other. They defined two stability notions, strongly stable noncrossing matching (SSNM) and weakly stable noncrossing matching (WSNM), depending on the strength of blocking pairs. They proved that a WSNM always exists and presented an O(n(2))-time algorithm to find one for an instance with n men and n women. They also posed open questions of the complexities of determining existence of an SSNM and finding a largest WSNM. In this paper, we show that both problems are solvable in polynomial time. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete.

关键词： Stable marriage Noncrossing matching polynomial-time algorithms NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Two-echelon lot-sizing with asymmetric information and continuous type space

引用

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2019年 87卷 158-176页

作者： Kerkkamp, R. B. O. van den Heuvel, W. Wagelmans, A. P. M. Erasmus Univ Econometr Inst Postbus 1738 NL-3000 DR Rotterdam Netherlands

We analyse a two-echelon discrete lot-sizing problem with a supplier and a retailer under information asymmetry. We assume that all cost parameters are time independent and that the retailer has single dimensional continuous private information, namely either his setup cost or his holding cost. The supplier uses mechanism design to determine a menu of contracts that minimises his expected costs, where each contract specifies the retailer's procurement plan and a side payment to the retailer. There is no restriction on the number of contracts in the menu. To optimally solve this principal-agent contracting problem we present a two-stage approach, based on a theoretical analysis. The first stage generates a list of procurement plans that is sufficient to solve the contracting problem to optimality. The second stage optimally assigns these plans to the retailer types and determines all side payments. The result is an optimal menu with finitely many contracts that pools retailer types. We identify cases for which the contracting problem can be solved in polynomial time and provide the corresponding algorithms. Furthermore, our analysis reveals that information asymmetry leads to atypical structures in the plans of the optimal menu, e.g., plans violating the zero-inventory property. Our solution approach and several results are directly applicable to more general problems as well. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： Discrete lot-sizing Mechanism design Asymmetric information Combinatorial optimisation polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Critical (P6, banner)-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 258卷 143-151页

作者： Huang, Shenwei Li, Tao Shi, Yongtang Nankai Univ Coll Comp Sci Tianjin 300071 Peoples R China Nankai Univ Ctr Combinator Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China

Given two graphs H-1 and H-2, a graph is (H-1, H-2)-free if it contains no induced subgraph isomorphic to H-1 or H-2. Let P-t and C-t be the path and the cycle on t vertices, respectively. A banner is the graph obtained from a C-4 by adding a new vertex and making it adjacent to exactly one vertex of the C-4. In this paper, we show that there are finitely many k-critical (P-6, banner)-free graphs for k = 4 and k = 5. For k = 4, we characterize all such graphs. Our results generalize previous results on k-critical (P-6, C-4)-free graphs for k = 4 and k = 5. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Coloring Critical graphs Hereditary classes Strong perfect graph theorem polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

The graph of atomic divisors and recognition of finite simple groups

引用

JOURNAL OF ALGEBRA 2019年 537卷 478-502页

作者： Buturlakin, Alexander A. Vasil'ev, Audrey V. Sobolev Inst Math 4 Acad Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogova Str Novosibirsk 630090 Russia

The spectrum omega(G) of a finite group G is the set of orders of elements of G. We present a polynomial-time algorithm that, given a finite set M of positive integers, outputs either an empty set or a finite simple group G. In the former case, there is no finite simple group H with M = omega(H), while in the latter case, M subset of omega(G) and M not equal omega(H) for all finite simple groups H with omega(H) not equal omega(G). (C) 2019 Elsevier Inc. All rights reserved.

关键词： Finite simple group Spectrum of a group Recognition by spectrum Prime graph Graph of atomic divisors polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Paths and trails in edge-colored weighted graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 799卷 104-114页

作者： Miao, Runjie Yuan, Jinjiang Huang, Fei Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

Let (G, c, w) be an edge-colored weighted graph, where G is a nontrivial connected graph, c is an edge-coloring of G, and w is an edge-weighting of G. A path, a trail, a cycle, or a closed trail of G, say F, is called proper under the edge-coloring c if every two consecutive edges of F receive different colors in c. Let s and t be two specified nonadjacent vertices in G. In this paper, we study the problems for finding, in (G, c, w), the minimum weighted proper s-t-path, the minimum weighted proper s-t-trail, the minimum weighted proper cycle, the minimum weighted proper closed trail, the maximum weighted proper s-t-path, and the maximum weighted proper s-t-trail. When the minimization problems are considered we assume that (G, c, w) has no negative proper cycle, and when the maximization problems are considered we assume that (G, c, w) has no proper closed trail. We show that all these problems are solvable in polynomial time. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Edge-colored weighted graphs Paths and trails polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Stable roommates with narcissistic, single-peaked, and single-crossing preferences

引用

AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS 2020年第2期34卷 53-53页

作者： Bredereck, Robert Chen, Jiehua Finnendahl, Ugo Paavo Niedermeier, Rolf TU Berlin Berlin Germany TU Wien Vienna Austria

The classicalStable Roommatesproblem is to decide whether there exists a matching of an even number of agents such that no two agents which are not matched to each other would prefer to be with each other rather than with their respectively assigned partners. We investigateStable Roommateswith complete (i.e., every agent can be matched with any other agent) or incomplete preferences, with ties (i.e., two agents are considered of equal value to some agent) or without ties. It is known that in general allowing ties makes the problem NP-complete. We provide algorithms forStable Roommatesthat are, compared to those in the literature, more efficient when the input preferences are complete and have some structural property, such as being narcissistic, single-peaked, and single-crossing. However, when the preferences are incomplete and have ties, we show that being single-peaked and single-crossing does not reduce the computational complexity-Stable Roommatesremains NP-complete.

关键词： Stable matching Incomplete preferences Preferences with ties Restricted preference domains NP-completeness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：