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

An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set

OPERATIONS RESEARCH LETTERS 2013年第2期41卷 191-196页

作者： Goyal, Vineet Ravi, R. Columbia Univ New York NY 10027 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

We consider the problem of minimizing a class of quasi-concave functions over a convex set. Quasi-concave functions are generalizations of concave functions and NP-hard to minimize in general. We present a simple fully polynomial time approximation scheme (FPTAS) for minimizing a class of low-rank quasi-concave functions. Our algorithm solves a polynomial number of linear minimization problems and computes an extreme point near-optimal solution. Therefore, it applies directly to combinatorial 0-1 problems where the convex hull of feasible solutions is known. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Quasi-concave programming Non-linear programming Non-convex programming polynomial approximation schemes

来源：评论

学校读者我要写书评

暂无评论

Approximability of flow shop scheduling

引用

MATHEMATICAL PROGRAMMING 1998年第1-2期82卷 175-190页

作者： Hall, LA Johns Hopkins Univ Dept Math Sci Baltimore MD 21218 USA

Shop scheduling problems are notorious for their intractability, both in theory and practice. In this paper, we construct a polynomial approximation scheme for the flow shop scheduling problem with an arbitrary fixed number of machines. For the three common shop models (open, flow, and job), this result is the only known approximation scheme. Since none of the three models can be approximated arbitrarily closely in the general case (unless P-NP), the result demonstrates the approximability gap between the models in which the number of machines is fixed, and those in which it is part of the input of the instance. The result can be extended to flow shops with job release dates and delivery times and to flow shops with a fixed number of stages, where the number of machines at any stage is fixed. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

关键词： flow shop scheduling approximation algorithms polynomial approximation schemes

来源：评论

学校读者我要写书评

暂无评论

A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball

引用

OPERATIONS RESEARCH LETTERS 1997年第2期20卷 59-63页

作者： Boyd, EA Department of Industrial Engineering Texas A&M University 23 Zavhry Building College Station TX 77843-3133 USA

A cutting plane algorithm is presented for finding E-approximate solutions to integer programs contained in the unit hypercube and represented by a separation oracle. Under the assumption that a polynomially bounded ball is contained in the feasible region of the problem, it is demonstrated that the algorithm is an oracle fully polynomial epsilon approximation scheme. Implications of the result for 0/1 integer programming are discussed.

关键词： polynomial approximation schemes cutting planes integer programming

来源：评论

学校读者我要写书评

暂无评论

A NEW LINEAR-STORAGE, polynomial-TIME approximation SCHEME FOR THE SUBSET-SUM PROBLEM

引用

DISCRETE APPLIED MATHEMATICS 1990年第1期26卷 61-77页

作者： FISCHETTI, M DEIS University of Bologna viale Risorgimento 2 40136 Bologna Italy

Given a set of positive integers, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding, a given W . For this problem, we present a polynomial-time approximation scheme requiring only a linear storage, and prove that its worst-case performance dominates that of the linear-storage approximation schemes from the literature. A modification of the scheme requiring linear time and space for any fixed bound ε on the relative error, is also given. Extensive computational results on randomly generated test problems are reported.

关键词： Subset sum polynomial approximation schemes computational analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：