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

Joint 10th International Conference on Soft Computing and Intelligent Systems (SCIS) / 19th International Symposium on Advanced Intelligent Systems (ISIS)

作者： Karuno, Yoshiyuki Nakahama, Oki Kyoto Inst Technol Fac Mech Engn Kyoto Japan Kyoto Inst Technol Grad Sch Sci & Technol Kyoto Japan

ISBN: (纸本)9781538626337

A subset selection problem from a finite set of items is considered, where a constraint is imposed on the cardinality of a selected subset. The subset selection problem is motivated by automated packaging systems, so-called multi-head weighers. Given a set of n items with their integral weights, a positive integer target weight t and a positive integer k, the subset selection problem asks to find a subset of the items so that the total weight of chosen items is no less than the target weight, and the number of the chosen items is exactly k, and further the total weight of them is as close to the target weight as possible. In this paper, an O(knt) time algorithm is presented to solve the subset selection problem. Numerical experiments are also conducted to demonstrate the performance of the pseudo-polynomial time algorithm on certain test instances having a feasible solution, and the results are reported.

关键词： engineering optimization combinatorial packing operation subset selection dynamic programming pseudo-polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

An Improved pseudopolynomial time Algorithm for Subset Sum 65

An Improved Pseudopolynomial Time Algorithm for Subset Sum

引用

65th Symposium on Foundations of Computer Science

作者： Chen, Lin Lian, Jiayi Mao, Yuchen Zhang, Guochuan Zhejiang Univ Hangzhou Peoples R China

ISBN: (纸本)9798331516758;9798331516741

We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set X of n positive integers and a target t, Subset Sum asks whether some subset of X sums to t. Bringmann proposes an (O) over tilde (n + t)-time algorithm [Bringmann SODA'17], and an open question has naturally arisen: can Subset Sum be solved in O(n+w) time? Here w is the maximum integer in X. We make a progress towards resolving the open question by proposing an (O) over tilde (n + root wt)-time algorithm.

关键词： subset sum pseudo-polynomial time algorithms additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

The weight-constrained maximum-density subtree problem and related problems in trees

引用

JOURNAL OF SUPERCOMPUTING 2010年第3期54卷 366-380页

作者： Hsieh, Sun-Yuan Chou, Ting-Yu Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Given a tree T = (V, E) of n nodes such that each node v is associated with a value-weight pair (val(v), w(v)), where value val(v) is a real number and weight w(v) is a non-negative integer, the density of T is defined as Sigma(v is an element of V) val(v)/Sigma(v is an element of V) w(v). A subtree of T is a connected subgraph (V', E') of T, where V' subset of V and E' subset of E. Given two integers w(min) and w(max), the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T' = (V', E') satisfying w(min) <= Sigma(v is an element of V')w(v) <= W-max. In this paper, we first present an O(w(max)n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O (w(max)(2)n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S subset of V, we also present an O(w(max)(2)n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.

关键词： Design and analysis of algorithms Maximum-density paths Maximum-density Steiner trees Maximum-density subtrees NP-completeness pseudo-polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Hyper temporal networks A tractable generalization of simple temporal networks and its relation to mean payoff games

引用

CONSTRAINTS 2017年第2期22卷 152-190页

作者： Comin, Carlo Posenato, Roberto Rizzi, Romeo Univ Trento Dept Math Trento Italy Univ Paris Est Marne La Vallee LIGM Paris France Univ Verona Dept Comp Sci Verona Italy

Simple Temporal Networks (STNs) provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables. In this paper we introduce Hyper Temporal Networks (HyTNs), a strict generalization of STNs, to overcome the limitation of considering only conjunctions of constraints but maintaining a practical efficiency in the consistency check of the instances. In a Hyper Temporal Network a single temporal hyperarc constraint may be defined as a set of two or more maximum delay constraints which is satisfied when at least one of these delay constraints is satisfied. HyTNs are meant as a light generalization of STNs offering an interesting compromise. On one side, there exist practical pseudo-polynomial time algorithms for checking consistency and computing feasible schedules for HyTNs. On the other side, HyTNs offer a more powerful model accommodating natural constraints that cannot be expressed by STNs like "Trigger off exactly delta min before (after) the occurrence of the first (last) event in a set.", which are used to represent synchronization events in some process aware information systems/workflow models proposed in the literature.

关键词： Simple temporal networks Temporal consistency Hypergraphs pseudo-polynomial time algorithms Mean payoff games Disjunctive temporal problems Workflows

来源：评论

学校读者我要写书评

暂无评论

The exact path length problem

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2002年第1期42卷 41-53页

作者： Nykänen, M Ukkonen, E Univ Helsinki Dept Comp Sci Helsinki 00014 Finland

We study a problem related to finding shortest paths in weighted graphs. We, ask whether or not there is a path between two nodes that has a given total cost k. The edge weights of the graph can be both positive and negative integers or even integer vectors. We show that many variants of this problem are NP-complete. We develop a pseudo-polynomial algorithm for (both positive and negative) integer weights. The running time of this algorithm is O(W(2)n(3) + \k\ min(\k\, W)n(2)), where n is the number of nodes in the graph, W is the largest absolute value of any edge weight, and k is the target cost. The algorithm is based on preprocessing the graph with a relaxation algorithm to eliminate the effects of weight sign alternations along a path. This preprocessing stage is applicable to other problems as well. For example, we show how to find the minimum absolute cost of any path between two given nodes in a graph with integer weights in O(W(2)n(3)) time. (C) 2002 Elsevier Science.

关键词： graph algorithms path problems pseudo-polynomial time algorithms NP-completeness

来源：评论

学校读者我要写书评

暂无评论

Dynamic programming algorithms for producing food mixture packages by automatic combination weighers

引用

JOURNAL OF ADVANCED MECHANICAL DESIGN SYSTEMS AND MANUFACTURING 2014年第5期8卷

作者： Imahori, Shinji Karuno, Yoshiyuki Tateishi, Kenju Nagoya Univ Dept Computat Sci & Engn Chikusa Ku Nagoya Aichi 4648603 Japan Kyoto Inst Technol Dept Mech & Syst Engn Sakyo Ku Kyoto 6068585 Japan Kyoto Inst Technol Grad Sch Sci & Technol Sakyo Ku Kyoto 6068585 Japan

The lexicographic bi-criteria combinatorial optimization problem to be discussed in this paper is a mathematical model of the food mixture packing performed by so-called automatic combination weighers, and it is described as follows. We are given a union I = I-1 boolean OR I-2 boolean OR . . . boolean OR I-m of m sets of items, where for each i = 1, 2,...,m, I-i = {I-ik vertical bar k = 1,2,...,n denotes a set of n items of the i-th type and I-ik denotes the k-th item of the i-th type. Each item I-ik has an integral weight w(ik) and an integral priority gamma(ik). The problem asks to find a union = I' = I'(1) boolean OR I'(2) boolean OR . . . boolean OR I'(m) of m subsets of items where I'(i) subset of I-i so that the total weight of chosen items for I' is no less than an integral target weight T, and the sum weight of chosen items of the i-th type for is no less than an integral indispensable weight b(i). The total weight of chosen items for I' is minimized as the primary objective, and further the total priority of chosen items for I' is maximized as the second objective. For the case in which there are two types of items (i.e., m = 2), we propose an O(nT) time dynamic programming algorithm, applying a linear search technique. We also conduct numerical experiments to demonstrate the empirical performance.

关键词： Engineering optimization Food packaging 0-1 integer programming Dynamic programming pseudo-polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Kansei engineering, humans and computers: efficient dynamic programming algorithms for combinatorial food packing problems

引用

INTERNATIONAL JOURNAL OF BIOMETRICS 2011年第3期3卷 228-245页

作者： Imahori, Shinji Karuno, Yoshiyuki Nagamochi, Hiroshi Wang, Xiaoming Nagoya Univ Dept Computat Sci & Engn Chikusa Ku Nagoya Aichi 4648603 Japan Kyoto Inst Technol Dept Mech & Syst Engn Sakyo Ku Kyoto Kyoto 6068585 Japan Kyoto Univ Dept Appl Math & Phys Sakyo Ku Kyoto Kyoto 6068501 Japan Kyoto Inst Technol Dept Mech & Syst Engn Sakyo Ku Kyoto Kyoto 6068585 Japan

The packing system performs an operation of choosing a subset I ' from the set of I of the current n items to produce a package of foods. By repeating the packing operation, it produces a large number of packages one by one. The primary objective is to choose a subset I so that the total weight of chosen items is as close to a specified target weight T as possible. We additionally try to maximise the total priority of chosen items as the second objective so that items with longer durations in hoppers are preferably chosen. We show that the combinatorial food packing problem can be solved in O(nT) time if all input data are integral.

关键词： automatic combination weighers food packing problems target weight constraints combinatorial optimisation lexicographic bi-criteria optimisation computer algorithms dynamic programming pseudo-polynomial time algorithms optimal solutions minimal solutions

来源：评论

学校读者我要写书评

暂无评论

The Legal Firing Sequence Problem of Petri nets

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2000年第3期E83D卷 397-406页

作者： Watanabe, T Hiroshima Univ Fac Engn Dept Circuits & Syst Higashihiroshima 7398527 Japan

The subject of the paper is to give an overview and latest results on the Legal Firing Sequence Problem of Petri nets (LFS for short). LFS is very fundamental in the sense that it appears as a subproblem or a simpler form of various basic: problems in Petri net. theory, such as the weil-known marking reachability problem, the minimum initial resource allocation problem, the liveness (of level 4) problem, the scheduling problem md so on. However, solving LFS generally is not easy: it is SP-hard even for Petri nets having very simple structures. This intractability of LFS may have been preventing us from producing efficient algorithms for those problems. So research on LFS from computational complexity point of view seems to be rewarding.

关键词： Petri nets Legal Firing Sequence Problems time complexity analysis NP-hardness pseudo-polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：