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

A faster FPTAS for counting two-rowed contingency tables

DISCRETE APPLIED MATHEMATICS 2021年 303卷 161-170页

作者： Alon, Tzvi Halman, Nir Hebrew Univ Jerusalem Jerusalem Israel

In this paper we provide a deterministic fully polynomial time approximation scheme (FPTAS) for counting two-rowed contingency tables that is faster than any either deterministic or randomized approximation scheme for this problem known to date. Our FPTAS is derived via a somewhat sophisticated usage of the method of k-approximation sets and functions introduced by Halman et al. (2009). (C) 2020 Elsevier B.V. All rights reserved.

关键词： Contingency tables Dynamic programming k-approximation sets and functions

来源：评论

学校读者我要写书评

暂无评论

An FPTAS for two performance measures for the relocation scheduling problem subject to fixed processing sequences

引用

OPTIMIZATION LETTERS 2022年第4期16卷 1181-1196页

作者： Halman, Nir Vinetz, Uriel Bar Ilan Univ Ramat Gan Israel Tel Aviv Univ Tel Aviv Israel

In this paper we consider a resource-constrained scheduling problem on two parallel dedicated machines with given fixed processing sequences of jobs assigned to each one of the machines. The problem is to determine the starting times of all jobs, subject to the resource constraint, in order to minimize some given performance measure. Lin et al. (J Sched 19(2):153-163, 2016) showed that the problem is NP-hard in the ordinary sense under the performance measures of weighted total tardiness and weighted number of tardy jobs, and questioned the existence of approximation schemes. In this paper we answer their question in the affirmative by designing fully polynomial time approximation schemes.

关键词： Relocation scheduling Dynamic programming k-approximation sets and functions FPTAS

来源：评论

学校读者我要写书评

暂无评论

The TV advertisements scheduling problem

引用

OPTIMIZATION LETTERS 2019年第1期13卷 81-94页

作者： Diaz-Nunez, Fabian Halman, Nir Vasquez, Oscar C. Univ Santiago Chile Dept Ind Engn Santiago Chile Hebrew Univ Jerusalem Jerusalem Israel

A TV channel has a single advertisement break of duration h and a convex continuous function f[0,h] -> R+ representing the TV rating points within the advertisement break. Given n TV advertisements of different durations pj that sum up to h, and willingness to pay coefficients wj, the objective is to schedule them on the TV break in order to maximize the total revenue of the TV channel Sigma jwjcj-pjcjf(t)dt, where [cj-pj,cj) is the broadcast time interval of TV advertisement j. We show that this problem is NP-hard and propose a fully polynomial time approximation scheme, using a special dominance property of an optimal schedule and the technique of k-approximation sets and functions introduced by Halman et al. (Math Oper Res 34:674-685, 2009).

关键词： Scheduling TV rating points Dynamic programming Fully polynomial time approximation scheme k-approximation sets and functions

来源：评论

学校读者我要写书评

暂无评论

approximation schemes for non-separable non-linear boolean programming problems under nested knapsack constraints

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2018年第2期270卷 435-447页

作者： Halman, Nir kellerer, Hans Strusevich, Vitaly A. Hebrew Univ Jerusalem Jerusalem Israel Karl Franzens Univ Graz Inst Stat & Operat Res Univ Str 15 A-8010 Graz Austria Univ Greenwich Old Royal Naval Coll Dept Math Sci Pk Row London SE10 9LS England

We consider a fairly general model of "take-or-leave" decision-making. Given a number of items of a particular weight, the decision-maker either takes (accepts) an item or leaves (rejects) it. We design fully polynomial-time approximation schemes (FPTASs) for optimization of a non-separable non-linear function which depends on which items are taken and which are left. The weights of the taken items are subject to nested constraints. There is a noticeable lack of approximation results on integer programming problems with non-separable functions. Most of the known positive results address special forms of quadratic functions, and in order to obtain the corresponding approximation algorithms and schemes considerable technical difficulties have to be overcome. We demonstrate how for the problem under consideration and its modifications FPTASs can be designed by using (i) the geometric rounding techniques, and (ii) methods of k-approximation sets and functions. While the latter approach leads to a faster scheme, the running times of both algorithms compare favorably with known analogues for less general problems. (C) 2018 The Authors. Published by Elsevier B.V.

关键词： Combinatorial optimization Non-linear boolean programming Geometric rounding k-approximation sets and functions FPTAS

来源：评论

学校读者我要写书评

暂无评论

A technical note: fully polynomial time approximation schemes for minimizing the makespan of deteriorating jobs with nonlinear processing times

引用

JOURNAL OF SCHEDULING 2020年第6期23卷 643-648页

作者： Halman, Nir Hebrew Univ Jerusalem Jerusalem Israel

Fully polynomial time approximation schemes for scheduling deteriorating jobs with nonlinear processing times on a single machine are given via an application of the k-approximation sets and functions technique.

关键词： Dynamic scheduling FPTAS k-approximation sets and functions

来源：评论

学校读者我要写书评

暂无评论

AUTOMATIC GENERATION OF FPTASes FOR STOCHASTIC MONOTONE DYNAMIC PROGRAMS MADE EASIER

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第4期35卷 2679-2722页

作者： Alon, Tzvi Halman, Nir Hebrew Univ Jerusalem Jerusalem Israel Bar Ilan Univ Ramat Gan Israel

In this paper we go one step further in the automatic generation of FPTASes for multistage stochastic dynamic programs with scalar state and action spaces, in which the cost-to-go functions have a monotone structure in the state variable. While there exist a few frameworks for automatic generation of FPTASes, so far none of them is general and simple enough to be extensively used. We believe that our framework has these two attributes and has great potential to attract interest from both the operations research and theoretical computer science communities. Moreover, it seems very reasonable that many intractable problems that currently do not admit an FPTAS, can be formulated as DPs that fit into our framework and therefore will admit a first FPTAS. Our results are achieved by a combination of Bellman equation formulations, the technique of k-approximation sets and functions, and in particular the calculus of k-approximation functions.

关键词： dynamic programming FPTAS k-approximation sets and functions

来源：评论

学校读者我要写书评

暂无评论

Strongly Polynomial FPTASes for Monotone Dynamic Programs

引用

ALGORITHMICA 2022年第10期84卷 2785-2819页

作者： Alon, Tzvi Halman, Nir Hebrew Univ Jerusalem Jerusalem Israel Bar Ilan Univ Ramat Gan Israel

In this paper we introduce a framework for the automatic generation of Strongly Polynomial Fully Polynomial Time approximation Schemes (SFPTASes) for monotone dynamic programs. While some ad-hoc SFPTASes for specific problems are already known, this is the first framework yielding such SFPTASes. In addition, it is possible to use our algorithm to get efficient (non strongly polynomial) FPTASes. Our results are derived by improving former (non strongly polynomial) FPTASes which were designed via the method of k-approximation sets and functions. We demonstrate our SFPTAS framework on five application problems, namely, 0/1 knapsack, counting 0/1 knapsack, Counting s - t paths, Mobile agent routing and Counting n-tuples, for the last problem we get the fastest SFPTAS known to date. In addition, we use our algorithm to get the fastest (non strongly polynomial) FPTASes for the following other three application problems: Stochastic ordered knapsack, Bi-criteria path problem with maximum survival probability and Minimizing the makespan of deteriorating jobs.

关键词： Strongly polynomial algorithms Dynamic programming k-approximation sets and functions

来源：评论

学校读者我要写书评

暂无评论

Provably Near-Optimal approximation Schemes for Implicit Stochastic and Sample-Based Dynamic Programs

引用

INFORMS JOURNAL ON COMPUTING 2020年第4期32卷 1157-1181页

作者： Halman, Nir Hebrew Univ Jerusalem Sch Business Adm IL-91905 Jerusalem Israel

In this paper, we address two models of nondeterministic discrete time finite-horizon dynamic programs (DPs): implicit stochastic DPs (the information about the random events is given by value oracles to their cumulative distribution functions) and sample-based DPs (the information about the random events is deduced by drawing random samples). Such data-driven models frequently appear in practice, where the cumulative distribution functions of the underlying random variables are either unavailable or too complicated to work with. In both models, the single-period cost functions are accessed via value oracle calls and assumed to possess either monotone or convex structure. We develop the first near-optimal relative approximation schemes for each of the two models. Applications in stochastic inventory control (that is, several variants of the so-called newsvendor problem) are discussed in detail. Our results are achieved by a combination of Bellman equation calculations, density estimation results, and extensions of the technique of k-approximation sets and functions introduced by Halman et al. (2009) [Halman N, klabjan D, Mostagir M, Orlin J, Simchi-Levi D (2009) A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Math. Oper. Res. 34(3):674-685.].

关键词： approximation algorithms inventory control k-approximation sets and functions sample average approximation

来源：评论

学校读者我要写书评

暂无评论

Resource allocation in rooted trees subject to sum constraints and nonlinear cost functions

引用

INFORMATION PROCESSING LETTERS 2021年 170卷 106114-106114页

作者： Halman, Nir Wimer, Shmuel Bar Ilan Univ Fac Engn Ramat Gan Israel

We study resource allocation problems in rooted trees in which demand values are given in the leaves. Single-type resources (weights) are to be assigned in the tree nodes such that the total weight in the rooted path from each leaf to the root equals its demand. The goal is to minimize the total costs of the allocated resources. It is known that the linear cost case, i.e., when the cost of a resource is proportional to its weight, is solvable in linear time. In this paper we show that when costs are monotone nondecreasing functions, which reflect, e.g., (dis)economies of scale, the problem becomes intractable, and design for it a fully polynomial time approximation scheme by formulating it as a dynamic program and using the technique of k-approximation sets and functions. (C) 2021 Published by Elsevier B.V.

关键词： Resource allocation Dynamic programming k-approximation sets and functions FPTAS Design of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：