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

A polynomial-time algorithm for a flow-shop batching problem with equal-length operations

JOURNAL OF SCHEDULING 2011年第4期14卷 371-389页

作者： Brucker, Peter Shakhlevich, Natalia V. Univ Leeds Sch Comp Leeds LS2 9JT W Yorkshire England Univ Osnabruck Fachbereich Math Informat D-49069 Osnabruck Germany

A flow-shop batching problem with consistent batches is considered in which the processing times of all jobs on each machine are equal to p and all batch set-up times are equal to s. In such a problem, one has to partition the set of jobs into batches and to schedule the batches on each machine. The processing time of a batch B(i) is the sum of processing times of operations in B(i) and the earliest start of B(i) on a machine is the finishing time of B(i) on the previous machine plus the set-up time s. Cheng et al. (Naval Research Logistics 47:128-144, 2000) provided an O(n) pseudopolynomial-time algorithm for solving the special case of the problem with two machines. Mosheiov and Oron (European Journal of Operational Research 161: 285291, 2005) developed an algorithm of the same time complexity for the general case with more than two machines. Ng and Kovalyov (Journal of Scheduling 10: 353-364, 2007) improved the pseudopolynomial complexity to O(root n). In this paper, we provide a polynomial-time algorithm of time complexity O(log(3)n).

关键词： Batch scheduling Flow shop polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

"Almost-stable" matchings in the Hospitals/Residents problem with Couples 22nd

"Almost-stable" matchings in the Hospitals/Residents problem...

引用

22nd International Conference on the Principles and Practice of Constraint Programming (CP)

作者： Manlove, David F. McBride, Iain Trimble, James Univ Glasgow Sch Comp Sci Sir Alwyn Williams Bldg Glasgow G12 8QQ Lanark Scotland

ISBN: (纸本)9783319449524

The Hospitals / Residents problem with Couples (hrc) models the allocation of intending junior doctors to hospitals where couples are allowed to submit joint preference lists over pairs of (typically geographically close) hospitals. It is known that a stable matching need not exist, so we consider min bp hrc, the problem of finding a matching that admits the minimum number of blocking pairs (i.e., is "as stable as possible"). We show that this problem is NP-hard and difficult to approximate even in the highly restricted case that each couple finds only one hospital pair acceptable. However if we further assume that the preference list of each single resident and hospital is of length at most 2, we give a polynomial-time algorithm for this case. We then present the first Integer Programming (IP) and Constraint Programming (CP) models for min bp hrc. Finally, we discuss an empirical evaluation of these models applied to randomly-generated instances of min bp hrc. We find that on average, the CP model is about 1.15 times faster than the IP model, and when presolving is applied to the CP model, it is on average 8.14 times faster. We further observe that the number of blocking pairs admitted by a solution is very small, i.e., usually at most 1, and never more than 2, for the (28,000) instances considered.

关键词： Most-stable matching Blocking pair polynomial-time algorithm NP-hardness Integer programming model Constraint programming model Empirical evaluation

来源：评论

学校读者我要写书评

暂无评论

Co-Bipartite Neighborhood Edge Elimination Orderings

引用

Electronic Notes in Discrete Mathematics 2017年 61卷 655-661页

作者： Jiamjitrak, Wanchote van Leeuwen, Erik Jan Dept. Computer Science Aalto University Espoo Finland Dept. Inform. Comput. Sciences Utrecht University Utrecht Netherlands

In SODA 2001, Raghavan and Spinrad introduced robust algorithms as a way to solve hard combinatorial graph problems in polynomial time even when the input graph falls slightly outside a graph class for which a polynomial-time algorithm exists. As a leading example, the MAXIMUM CLIQUE problem on unit disk graphs (intersection graphs of unit disks in the plane) was shown to have a robust, polynomial-time algorithm by proving that such graphs admit a co-bipartite neighborhood edge elimination ordering (CNEEO). This begs the question whether other graph classes also admit a CNEEO. In this paper, we answer this question positively, and identify many graph classes that admit a CNEEO, including several graph classes for which no polynomial-time recognition algorithm exists (unless P=NP). As a consequence, we obtain robust, polynomial-time algorithms for MAXIMUM CLIQUE on all identified graph classes. We also prove some negative results, and identify graph classes that do not admit a CNEEO. This implies an almost-perfect dichotomy for subclasses of perfect graphs. © 2017 Elsevier B.V.

关键词： edge ordering graph classes maximum clique polynomial-time algorithm robust algorithm

来源：评论

学校读者我要写书评

暂无评论

LOCATION OF ALTERNATIVE-FUEL REFUELING STATIONS ON TRANSPORTATION NETWORKS CONSIDERING VEHICLE DEVIATIONS AND GREENHOUSE GAS EMISSIONS

LOCATION OF ALTERNATIVE-FUEL REFUELING STATIONS ON TRANSPORT...

引用

作者： Kweon, Sang Jin PennState University Libraries

学位级别：Doctor of Philosophy

Burning conventional fossil fuels including gasoline and diesel mainly results in over 90% of greenhouse gas emissions from transportation. To reduce these emissions from the ground transportation sector, the use of alternative-fuel vehicles is being spotlighted. As a result, refueling station location problems for alternative-fuel vehicles have received attention as well. These refueling station location problems can be classified into two types depending on the set of candidate sites: when a preliminary (finite) set of candidate sites is given, this problem is called discrete; when the stations can be located anywhere along the network, the problem is called continuous. This dissertation considers one discrete and two continuous location problems for alternative-fuel refueling stations on transportation networks. First, the discrete location problem is addressed with two conflicting objectives of maximizing the total vehicle-miles traveled per time unit covered by the stations and minimizing the capital cost for constructing the refueling infrastructure. Two versions of bi-criteria binary linear programming models are proposed and validated with an application to the Pennsylvania Turnpike System regarding the location of liquefied natural gas refueling stations on existing service plazas. Next, assuming that a vehicle cannot deviate from the preplanned path, the continuous location problem for a single refueling station is addressed on a tree network with the objective of maximizing the traffic flow (in round trips per time unit) covered by the station. Two reduction properties regarding the problem size and some optimality conditions are derived. Then, an exact polynomial algorithm is developed to determine the set of optimal locations for the refueling station. Lastly, the continuous location problem introduced above is extended to a version where a given portion of drivers are willing to deviate to be able to refuel if the station is not located along their pre

关键词： Alternative-fuel vehicles bi-criteria optimization GHG emission reduction Facility location Refueling station Tree network Deviation-flow polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

ON THE COMPUTATIONAL COMPLEXITY OF MINIMUM-CONCAVE-COST FLOW IN A TWO-DIMENSIONAL GRID

引用

SIAM JOURNAL ON OPTIMIZATION 2016年第4期26卷 2059-2079页

作者： Ahmed, Shabbir He, Qie Li, Shi Nemhauser, George L. Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA Univ Minnesota Dept Ind & Syst Engn Minneapolis MN 55455 USA SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA

We study the minimum-concave-cost flow problem on a two-dimensional grid. We characterize the computational complexity of this problem based on the number of rows and columns of the grid, the number of different capacities over all the arcs, and the location of sources and sinks. The concave cost over each arc is assumed to be evaluated through an oracle machine, i.e., the oracle machine returns the cost over an arc in a single computational step, given the flow value and the arc index. We propose an algorithm whose running time is polynomial in the number of columns of the grid for the following cases: (1) the grid has a constant number of rows, a constant number of different capacities over all the arcs, and sources and sinks in at most two rows;(2) the grid has two rows and a constant number of different capacities over all the arcs connecting rows;(3) the grid has a constant number of rows and all sources in one row, with infinite capacity over each arc. These are presumably the most general polynomially solvable cases, since we show that the problem becomes NP-hard when any condition in these cases is removed. Our results apply to several variants and generalizations of the single item dynamic lot sizing model and answer several questions raised in serial supply chain optimization.

关键词： minimum-concave-cost flow two-dimensional grid lot sizing serial supply chain computational complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Critical hereditary graph classes: a survey

引用

OPTIMIZATION LETTERS 2016年第8期10卷 1593-1612页

作者： Malyshev, D. S. Pardalos, P. M. Natl Res Univ Higher Sch Econ 25-12 Bolshaja Pecherskaja Ulitsa Nizhnii Novgorod 603155 Russia Univ Florida 401 Weil HallPOB 116595 Gainesville FL 32611 USA

The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called "critical" graph classes, which play an important role in the complexity analysis for the family. Recent progress in studying such classes is presented in the article.

关键词： Computational complexity polynomial-time algorithm Hereditary graph class Independent set problem Dominating set problem Coloring problem List edge-ranking problem

来源：评论

学校读者我要写书评

暂无评论

Two cases of polynomial-time solvability for the coloring problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第2期31卷 833-845页

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

The complexity of the coloring problem is known for all hereditary classes defined by two connected 5-vertex forbidden induced subgraphs except 13 cases. We update this result by proving polynomial-time solvability of... 详细信息

关键词： Vertex coloring Computational complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs

引用

DISCRETE APPLIED MATHEMATICS 2016年 203卷 117-126页

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

We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden induced subgraphs with at most five vertices. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Dominating set problem Hereditary class Computational complexity polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

A complexity dichotomy and a new boundary class for the dominating set problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第1期32卷 226-243页

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

We study the computational complexity of the dominating set problem for hereditary graph classes, i.e., classes of simple unlabeled graphs closed under deletion of vertices. Every hereditary class can be defined by a set of its forbidden induced subgraphs. There are numerous open cases for the complexity of the problem even for hereditary classes with small forbidden structures. We completely determine the complexity of the problem for classes defined by forbidding a five-vertex path and any set of fragments with at most five vertices. Additionally, we also prove polynomial-time solvability of the problem for some two classes of a similar type. The notion of a boundary class is a helpful tool for analyzing the computational complexity of graph problems in the family of hereditary classes. Three boundary classes were known for the dominating set problem prior to this paper. We present a new boundary class for it.

关键词： Dominating set Computational complexity polynomial-time algorithm Boundary class

来源：评论

学校读者我要写书评

暂无评论

Constrained domatic bipartition on trees

引用

DISCRETE OPTIMIZATION 2016年第PartB期22卷 372-388页

作者： Andreatta, Giovanni De Francesco, Carla De Giovanni, Luigi Serafini, Paolo Univ Padua Dipartimento Matemat Via Trieste 63 I-35121 Padua Italy Univ Udine Dipartimento Sci Matemat Informat & Fis Viale Sci 206 I-33100 Udine Italy

Given an undirected graph, the Constrained Domatic Bipartition Problem (CDBP) consists in determining a bipartition, if it exists, of the nodes into two dominating sets, with the additional constraint that one of the two subsets has a given cardinality. The problem is NP-hard in general and in this paper we focus on trees. First, we provide explicit solutions in simple cases, i.e., stars and paths. Then, we provide a polyhedral representation for all domatic bipartitions of a tree. Although the matrix associated with the polyhedron is not totally unimodular, we prove that all its vertices have integral components. Adding the cardinality constraint, the resulting polyhedron will generally lose this property. We then propose a constructive, dynamic programming algorithm for CDBP on trees, that is able to simultaneously find a solution for all possible cardinalities. The proposed algorithm is polynomial with complexity O(n(3)), where n is the number of nodes. Finally, we discuss the extension of CDBP to the weighted case, show that it is NP-hard and provide a pdeudo-polynomial algorithm for the problem. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Dominating set Cardinality constraint Tree polynomial-time algorithm Integral polytope

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：