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

Faster algorithms for k-subset sum and variations

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-21页

作者： Antonopoulos, Antonis Pagourtzis, Aris Petsalakis, Stavros Vasilakis, Manolis Natl Tech Univ Athens Sch Elect & Comp Engn Athens 15780 Greece

We present new, faster pseudopolynomial time algorithms for the k-SUBSET SUM problem, defined as follows: given a set Z of n positive integers and k targets t(1), ... , t(k), determine whether there exist k disjoint subsets Z(1), ... , Z(k) subset of Z, such that E(Z(i)) = t(i), for i = 1, ... , k. Assuming t = max{t(1), ... , t(k)} is the maximum among the given targets, a standard dynamic programming approach based on Bellman's algorithm can solve the problem in O(nt(k)) time. We build upon recent advances on SUBSET SUM due to Koiliaris and Xu, as well as Bringmann, in order to provide faster algorithms for k-SUBSET SUM. We devise two algorithms: a deterministic one of time complexity (SIC)(n(k/(k+1))t(k)) and a randomised one of (SIC)(n + t(k)) complexity. Additionally, we show how these algorithms can be modified in order to incorporate cardinality constraints enforced on the solution subsets. We further demonstrate how these algorithms can be used in order to cope with variations of k-SUBSET SUM, namely SUBSET SUM RATIO, k-SUBSET SUM RATIO and MULTIPLE SUBSET SUM.

关键词： Color coding FFT k-Subset Sum Multiple Knapsack Multiple Subset Sum pseudopolynomial algorithms Subset Sum

来源：评论

学校读者我要写书评

暂无评论

Faster algorithms for k-SUBSET SUM and Variations 15th

Faster Algorithms for k-SUBSET SUM and Variations

引用

15th International Frontiers of Algorithmics Workshop (FAW) / Game Theory in Blockchain Track Conference / 2nd International Joint Conference on Theoretical Computer Science (IJTCS)

作者： Antonopoulos, Antonis Pagourtzis, Aris Petsalakis, Stavros Vasilakis, Manolis Natl Tech Univ Athens Polytechnioupoli Sch Elect & Comp Engn Zografos 15780 Greece

ISBN: (纸本)9783030970994;9783030970987

We present new, faster pseudopolynomial time algorithms for the k-SUBSET SUM problem, defined as follows: given a set Z of n positive integers and k targets t(1), ... , t(k), determine whether there exist k disjoint subsets Z(1), ... , Z(k) subset of Z, such that Sigma(Z(i)) = t(i), for i = 1, ... , k. Assuming t = max{t(1), ... , t(k)} is the maximum among the given targets, a standard dynamic programming approach based on Bellman's algorithm [3] can solve the problem in O(nt(k)) time. We build upon recent advances on SUBSET SUM due to Koiliaris and Xu [1 6] and Bringmann [1] in order to provide faster algorithms for k-SUBSET SUM. We devise two algorithms: a deterministic one of time complexity (O) over tilde (n(k)/((k+1))t(k)) and a randomised one of (O) over tilde (n + t(k)) complexity. We further demonstrate how these algorithms can be used in order to cope with variations of k-SUBSET SUM, namely SUBSET SUM RATIO, k-SUBSET SUM RATIO and MULTIPLE SUBSET SUM.

关键词： SUBSET SUM FFT Color Coding MULTIPLE SUBSET SUM MULTIPLE KNAPSACK k-SUBSET SUM pseudopolynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

The complexity of computation and approximation of the t-ratio over one-dimensional interval data

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2014年 80卷 26-43页

作者： Cerny, Michal Hladik, Milan Univ Econ Dept Econometr Prague 13067 3 Czech Republic Charles Univ Prague Dept Appl Math Fac Math & Phys Prague 11000 1 Czech Republic

The main question is how to compute the upper and lower limits of the range of possible values of a given statistic, when the data range over given intervals. Initially some well-known statistics, such as sample mean, sample variance or F-ratio, are considered in order to illustrate that in some cases the limits can be computed efficiently, while in some cases their computation is NP-hard. Subsequently, the t-ratio (variation coefficient) is considered. It is investigated when the limits for t-ratio are computable in polynomial time and a new efficient algorithm is designed for this case. Conversely, complementary NP-hardness results are proved, demonstrating the cases when the computation cannot be done efficiently. Subsequently, the NP-hardness results are strengthened: it is shown that under certain assumptions, even an approximate evaluation with an arbitrary absolute error is NP-hard. Finally, it is shown that the situation can also be (in some sense) regarded positively: a new pseudopolynomial algorithm is developed. The algorithm is of practical importance, especially when the dataset to be processed is large and does not contain "excessively" large numbers. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Interval data t-ratio Computational complexity NP-hardness Inapproximability pseudopolynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

New pseudopolynomial complexity bounds for the bounded and other integer Knapsack related problems

引用

OPERATIONS RESEARCH LETTERS 2009年第5期37卷 303-306页

作者： Tamir, Arie Tel Aviv Univ Sch Math Sci Tel Aviv Israel

We consider the bounded integer knapsack problem (BKP) max Sigma(n)(j=1) p(j)x(j), subject to: Sigma(n)(j=1) w(j)x(j) <= C, and x(j) is an element of {0, 1, .... m(j)}, j = 1,...,n. We use proximity results between the integer and the continuous versions to obtain an 0(n(3)W(2)) algorithm for BKP, where W = max(j=1,...,n)w(j). The respective complexity of the unbounded case with m(j) = infinity, for j = 1,..., n, is 0(n(2)W(2)). We use these results to obtain an improved strongly polynomial algorithm for the multicover problem with cyclical 1's and uniform right-hand side. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Bounded knapsack problem Bounded multiple-choice knapsack problem pseudopolynomial algorithms Multicover problem

来源：评论

学校读者我要写书评

暂无评论

Solution of the NP-hard total tardiness minimization problem in scheduling theory

引用

Computational Mathematics and Mathematical Physics 2007年第6期47卷 1039-1049页

作者： Lazarev, A.A. Dorodnicyn Computing Center Russian Academy of Sciences Moscow 119991 ul. Vavilova 40 Russian Federation

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1∥∑T j is considered. An NP-hard instance of the problem is completely analyzed.... 详细信息

The classical NP-hard (in the ordinary sense) problem of scheduling jobs in order to minimize the total tardiness for a single machine 1∥∑T _j is considered. An NP-hard instance of the problem is completely analyzed. A procedure for partitioning the initial set of jobs into subsets is proposed. algorithms are constructed for finding an optimal schedule depending on the number of subsets. The complexity of the algorithms is O(n ²∑p _j ), where n is the number of jobs and p _j is the processing time of the jth job (j = 1, 2, ..., n). © Nauka/Interperiodica 2007.

关键词： Minimization of total tardiness One machine pseudopolynomial algorithms Scheduling theory

来源：评论

学校读者我要写书评

暂无评论

Min-max optimization of several classical discrete optimization problems

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1998年第1期98卷 221-242页

作者： Yu, G Univ Texas Grad Sch Business Dept Management Sci & Informat Syst Austin TX 78712 USA Univ Texas Ctr Management Operat & Logist Austin TX 78712 USA

In this paper, we study discrete optimization problems with min-max objective functions. This type of problems has direct applications in the recent development of robust optimization. The following well-known classes of problems are discussed: minimum spanning tree problem, resource allocation problem with separable cost functions, and production control problem. Computational complexities of the corresponding min-max version of the above-mentioned problems are analyzed. pseudopolynomial algorithms for these problems are provided under certain conditions.

关键词： min-max discrete optimization computational complexity pseudopolynomial algorithms

来源：评论

学校读者我要写书评

暂无评论

GENERALIZATION OF BARAHONAS ALGORITHM FOR CASES OF INTEGER NONLINEAR-PROGRAMMING WITH BOX CONSTRAINTS

引用

OPERATIONS RESEARCH LETTERS 1993年第2期13卷 99-105页

作者： BALDICK, R LAWRENCE BERKELEY LAB DEPT ELECT & COMP ENGNBERKELEYCA 94720

Barahona described a linear time algorithm for a class of 0-1 quadratic programming problems. The algorithm was based on a transformation to a max-cut problem. We describe a linear algorithm that treats a slightly more general problem directly in its original form. We then give a pseudopolynomial algorithm for even more general problems.

关键词： INTEGER QUADRATIC PROGRAMMING SERIES-PARALLEL GRAPHS POLYNOMIAL algorithms pseudopolynomial algorithms BOX CONSTRAINTS DYNAMIC PROGRAMMING

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：