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

A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions

INFORMATION AND COMPUTATION 2019年 267卷 74-95页

作者： Boros, Endre Elbassioni, Khaled Gurvich, Vladimir Makino, Kazuhisa Rutgers State Univ MSIS Dept 100 Rockafellar RdLivingston Campus Piscataway NJ 08854 USA Rutgers State Univ RUTCOR 100 Rockafellar RdLivingston Campus Piscataway NJ 08854 USA Khalifa Univ Sci & Technol Masdar Inst POB 54224 Abu Dhabi U Arab Emirates Natl Res Univ HSE Moscow Russia Kyoto Univ RIMS Kyoto 6068502 Japan

We consider two-person zero-sum stochastic mean payoff games with perfect information, or BWR-games, given by a digraph G = (V, E), with local rewards r : E -> Z, and three types of positions: black V-B, white V-W, and random V-R forming a partition of V. It is a long-standing open question whether a polynomial time algorithm for BWR-games exists, or not, even when vertical bar V-R vertical bar = 0. In fact, a pseudo-polynomial algorithm for BWR-games would already imply their polynomial solvability. In this paper,(1) we show that BWR-games with a constant number of random positions can be solved in pseudo-polynomial time. More precisely, in any BWR-game with vertical bar V-R vertical bar = 0 (1), a saddle point in uniformly optimal pure stationary strategies can be found in time polynomial in vertical bar V-W vertical bar + vertical bar V-B vertical bar, the maximum absolute local reward, and the common denominator of the transition probabilities. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Equilibrium computation Perfect information pseudo-polynomial algorithm Stochastic games Zero-sum games

来源：评论

学校读者我要写书评

暂无评论

A dynamic programming approach for the two-product capacitated lot-sizing problem with concave costs

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第1期307卷 116-129页

作者： Bunn, Kevin A. Ventura, Jose A. Penn State Univ Harold & Inge Marcus Dept Ind & Mfg Engn University Pk PA 16802 USA Penn State Univ Harold & Inge Marcus Dept Ind & Mfg Engn 356 Leonhard Bldg University Pk PA 16802 USA

In this paper, we analyze a two-product multi-period dynamic lot-sizing problem with a fixed capacity constraint in each period. Each product has a known demand in each period that must be satisfied over a finite planning horizon. The aim of this problem is to minimize the overall cost of placing orders and car-rying inventory across all periods. The structure of an optimal solution is analyzed with respect to a type of period called regeneration period, which is a period where the inventory of one or both products reach zero. We show that there is an optimal arrangement of placing orders between consecutive regeneration periods. We propose a pseudo-polynomial algorithm to solve the two-product problem. First, we show how the optimal ordering pattern between two consecutive regeneration periods can be solved using a shortest path problem. Then, we explain how the optimal locations for regeneration periods can be found by solving a shortest path problem on a different network, where each arc corresponds to the shortest path in a subproblem network. We then show how this approach can be scaled up to a three-product problem and generalize this technique to any number of products, as long as it is small.(c) 2022 Published by Elsevier B.V.

关键词： Production planning Capacitated lot sizing Multiple products Dynamic demand pseudo-polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Parallel Machines Scheduling with Deteriorating Maintenance Activities and Job Rejection

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第1期40卷

作者： Zou, Juan Sui, Yu-Kang Gao, Jie Zhang, Xian-Zhao Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China Linyi Univ Coll Math & Stat Linyi 276005 Shandong Peoples R China

We consider parallel identical machines scheduling problems with deteriorating maintenance activities and the option of job rejection. Each machine has at most one deteriorating maintenance activity. The length of each maintenance activity increases linearly with its starting time. The location of the maintenance activity on each machine needs to be determined. The goal is to find the sequence of jobs to minimize scheduling cost;we further the model by allowing job rejection. A job is either accepted and processed on one of machines, or rejected. The goal is to determine the sequence of the accepted jobs to minimize scheduling cost of the accepted jobs plus total rejection penalty of the rejected jobs. When the scheduling cost is the makespan, we design a pseudo-polynomial time algorithm, a 2-approximation algorithm and a fully polynomial time approximation scheme. When the scheduling cost is the total completion time, we provide a polynomial time algorithm for the problem. When the scheduling costs are the total weighted completion time under the agreeable ratio assumption and the maximum lateness, we present pseudo-polynomial time algorithms to solve these problems, respectively.

关键词： Scheduling deteriorating maintenance activity rejection pseudo-polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Single-machine scheduling with an external resource

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2021年第2期293卷 457-468页

作者： Briskorn, Dirk Davari, Morteza Matuschke, Jannik Univ Wuppertal Chair Prod & Logist Wuppertal Germany Univ Cote dAzur SKEMA Business Sch Nice France Katholieke Univ Leuven Res Ctr Operat Management Leuven Belgium

This paper studies the complexity of single-machine scheduling with an external resource, which is rented for a non-interrupted period. Jobs that need this external resource are executed only when the external resource is available. There is a cost associated with the scheduling of jobs and a cost associated with the duration of the renting period of the external resource. We look at four classes of problems with an external resource: a class of problems where the renting period is budgeted and the scheduling cost needs to be minimized, a class of problems where the scheduling cost is budgeted and the renting period needs to be minimized, a class of two-objective problems where both, the renting period and the scheduling cost, are to be minimized, and a class of problems where a linear combination of the scheduling cost and the renting period is minimized. We provide a thorough complexity analysis (NP-hardness proofs and (pseudo-)polynomial algorithms) for different members of these four classes. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Scheduling Single-machine scheduling External resource Complexity pseudo-polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximations for Restrictions of The Budgeted and Generalized Maximum Coverage Problems 10th

Approximations for Restrictions of The Budgeted and Generali...

引用

10th Latin and American algorithms, Graphs, and Optimization Symposium (LAGOS)

作者： Piva, Breno Univ Fed Sergipe Dept Comp Sao Cristovao SE Brazil

In this paper we present approximation preserving reductions from the Budgeted and Generalized Maximum Coverage Problems to the Knapsack Problem with Conflict Graphs. The reductions are used to yield polynomial Time Approximation Schemes for special classes of instances of these problems. Using these approximation schemes, the existence of pseudo-polynomial algorithms are proven and, in more particular cases, these algorithms are shown to have polynomial time complexity. Moreover, the characteristics of the instances that admit these algorithms are analyzed.

关键词： Budgeted Maximum Coverage Generalized Maximum Coverage Knapsack with Conflict Graph Approximation algorithm pseudo-polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximations for Restrictions of The Budgeted and Generalized Maximum Coverage Problems

引用

Electronic Notes in Theoretical Computer Science 2019年 346卷 667-676页

作者： Breno Piva Departamento de Computação Universidade Federal de Sergipe São Cristóvão SE Brazil

关键词： Budgeted Maximum Coverage Generalized Maximum Coverage Knapsack with Conflict Graph Approximation algorithm pseudo-polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

A convex programming-based algorithm for mean payoff stochastic games with perfect information

引用

OPTIMIZATION LETTERS 2017年第8期11卷 1499-1512页

作者： Boros, Endre Elbassioni, Khaled Gurvich, Vladimir Makino, Kazuhisa Rutgers State Univ MSIS Dept 100 Rockafellar RdLivingston Campus Livingston NJ 08854 USA Rutgers State Univ RUTCOR 100 Rockafellar RdLivingston Campus Livingston NJ 08854 USA Masdar Inst Sci & Technol POB 54224 Abu Dhabi U Arab Emirates Natl Res Univ Higher Sch Econ Moscow Russia Kyoto Univ RIMS Kyoto 6068502 Japan

关键词： Stochastic games Perfect information Mean payoff pseudo-polynomial algorithm Convex programming

来源：评论

学校读者我要写书评

暂无评论

Static and dynamic source locations in undirected networks

引用

TOP 2015年第3期23卷 619-646页

作者： Turner, Lara Gross, Dwi Poetranto Hamacher, Horst W. Krumke, Sven O. Univ Kaiserslautern Dept Math D-67653 Kaiserslautern Germany INFORM GmbH D-52076 Aachen Germany

Results from source location in the form of single cover problems in static networks are reviewed and extended by new results for the most general problem with arbitrary demands and costs. The matroidal structure of the single covers is established and used in a new and simple validity proof of the dual greedy algorithm for static single cover problems. Moreover, a primal greedy algorithm is derived which uses a new procedure to find the collection of all minimal deficient sets. For static plural cover problems on trees two linear-time algorithms to solve simultaneous and non-simultaneous problems with uniform costs are presented;for the simultaneous scenario with non-uniform costs, a pseudo-polynomial algorithm is proposed which can be turned into a fully polynomial-time approximation scheme. In contrast to its static counterpart, the single cover problem in dynamic, i.e., time-varying networks is shown to be strongly NP-hard. For special cases of the network topology polynomial algorithms are presented.

关键词： Source location problem Single cover problem Matroid (Dual) greedy algorithm (Minimal) deficient set Plural cover problem Tree network Linear algorithm pseudo-polynomial algorithm Fully polynomial-time approximation scheme Dynamic flow NP-hardness

来源：评论

学校读者我要写书评

暂无评论

A Problem of Scheduling Jobs with Non-Monotonic Stepwise Values

引用

INFORMATICA 2014年第1期25卷 37-53页

作者： Janiak, Adam Krysiak, Tomasz Trela, Radoslaw Wroclaw Univ Technol Inst Comp Engn Control & Robot PL-50372 Wroclaw Poland

The paper deals with a parallel processor scheduling problem with changeable job values. Contrary to other papers in this area, we assume that job values are characterized by a non-monotonic stepwise functions of job completion times (previously only non-increasing functions have been considered). We give examples of real-life systems that can be modelled in such a way, in order to show that the problem is interesting from practical point of view. The problem is shown to be NP-hard and a pseudo-polynomial time algorithm for its special case is constructed. Moreover, a number of heuristic algorithms is provided and experimentally tested.

关键词： scheduling parallel processors non-monotonic job value pseudo-polynomial algorithm heuristic

来源：评论

学校读者我要写书评

暂无评论

Stochastic binary problems with simple penalties for capacity constraints violations

引用

MATHEMATICAL PROGRAMMING 2013年第1-2期138卷 199-221页

作者： Fortz, B. Labbe, M. Louveaux, F. Poss, M. Univ Libre Brussels Fac Sci Dept Comp Sci Brussels Belgium Univ Namur FUNDP Dept Business Adm Namur Belgium Univ Coimbra Dept Math CMUC P-3001454 Coimbra Portugal

This paper studies stochastic programs with first-stage binary variables and capacity constraints, using simple penalties for capacities violations. In particular, we take a closer look at the knapsack problem with weights and capacity following independent random variables and prove that the problem is weakly -hard in general. We provide pseudo-polynomial algorithms for three special cases of the problem: constant weights and capacity uniformly distributed, subset sum with Gaussian weights and strictly positively distributed random capacity, and subset sum with constant weights and arbitrary random capacity. We then turn to a branch-and-cut algorithm based on the outer approximation of the objective function. We provide computational results for the stochastic knapsack problem (i) with Gaussian weights and constant capacity and (ii) with constant weights and capacity uniformly distributed, on randomly generated instances inspired by computational results for the knapsack problem.

关键词： Stochastic programming Knapsack problem pseudo-polynomial algorithm Mixed-integer non-linear programming Branch-and-cut algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：