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 trans...
详细信息
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 polynomialtimealgorithms 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.
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...
详细信息
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.
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 o...
详细信息
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 polynomialtime. 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.
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...
详细信息
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.
作者:
Hamada, KokiMiyazaki, ShuichiOkamoto, KazuyaNTT 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
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 de...
详细信息
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 polynomialtime. Our algorithms are applicable to extensions where preference lists may include ties, except for one case which we show to be NP-complete.
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 con...
详细信息
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 polynomialtime 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.
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 obtain...
详细信息
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.
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 g...
详细信息
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.
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...
详细信息
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 polynomialtime. (C) 2019 Elsevier B.V. All rights reserved.
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 ...
详细信息
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.
暂无评论