Search Results 1-9 of 9

  • An approximation algorithm for the covering 0-1 integer program (The state-of-the-art optimization technique and future development)

    Takazawa Yotaro , Mizuno Shinji

    … The covering 0-1 integer program is a generalization of fundamental combinatorial optimization problems such as the vertex cover problem, the set cover problem, and the minimum knapsack problem. …

    数理解析研究所講究録 (2027), 10-14, 2017-04

    IR 

  • Energy-on-Demand System Based on Combinatorial Optimization of Appliance Power Consumptions

    Naoyuki Morimoto

    … In an EoD system, when total power consumption exceeds the limit of power resource, a power allocation manager deployed in the system decides the optimal power allocation to all the appliances based on their importance and power consumptions, and controls the amount of power supplied to the appliances in a way that causes minimum undesired effect to quality-of-life of users. … From a mathematical viewpoint, the power allocation management in an EoD system can be considered as an optimization problem of appliance operation modes. …

    情報処理学会論文誌コンシューマ・デバイス&システム(CDS) 7(1), 2017-01-26

    IPSJ 

  • Energy-on-Demand System Based on Combinatorial Optimization of Appliance Power Consumptions

    Morimoto Naoyuki

    … In an EoD system, when total power consumption exceeds the limit of power resource, a power allocation manager deployed in the system decides the optimal power allocation to all the appliances based on their importance and power consumptions, and controls the amount of power supplied to the appliances in a way that causes minimum undesired effect to quality-of-life of users. … From a mathematical viewpoint, the power allocation management in an EoD system can be considered as an optimization problem of appliance operation modes. …

    Journal of Information Processing 25(0), 268-276, 2017

    J-STAGE 

  • A 2-APPROXIMATION ALGORITHM FOR THE MINIMUM KNAPSACK PROBLEM WITH A FORCING GRAPH

    Takazawa Yotaro , Mizuno Shinji

    … <p>Carnes and Shmoys [2] presented a 2-approximation algorithm for the minimum knapsack problem. … We extend their algorithm to the minimum knapsack problem with a forcing graph (MKPFG), which has a forcing constraint for each edge in the graph. … The forcing constraint means that at least one item (vertex) of the edge must be packed in the knapsack. …

    Journal of the Operations Research Society of Japan 60(1), 15-23, 2017

    J-STAGE 

  • A PTAS for the Subset Sum Reconfiguration Problem

    ITO Takehiro , DEMAINE Erik D.

    整数の集合A,容量cのナップサック,整数κに対し,要素の合計値(以下,部分集合和という)がκ以上c以下になるようなAの部分集合(以下,パッキングという)を見つける問題は,部分集合和問題と呼ばれ,NP完全であることが知られている.本論文では,与えられた2つのパッキングA_0とA_tの間を段階的に遷移させるシーケンスが存在するかどうか判定する問題を扱う.ここで,段階的な遷移シーケンスとは,以下の3つの …

    IEICE technical report 111(195), 7-14, 2011-08-30

    References (13)

  • A PTAS for the Subset Sum Reconfiguration Problem

    伊藤 健洋 , ErikD.Demaine

    … る.この最大化問題に対し,我々は多項式時間近似スキーム (PTAS) を与える.一方で,制約グラフが与えられる場合には,APX 困難であることも示す.The subset sum problem is a well-known NP-complete problem in which we wish to find a packing (subset) of items (integers) into a knapsack with capacity so that the sum of the integers in the packing is at most the capacity of the knapsack and at least a given integer …

    研究報告アルゴリズム(AL) 2011-AL-136(2), 1-8, 2011-08-30

  • A 0-1 KNAPSACK PROBLEM CONSIDERING RANDOMNESS OF FUTURE RETURNS AND FLEXIBLE GOALS OF AVAILABLE BUDGET AND TOTAL RETURN

    HASUIKE TAKASHI , ISHII HIROAKI

    … This paper proposes a 0-1 knapsack problem considering both the maximization ofthe total return including randomness and minimization of available budget, simultaneously.For the flexibility of setting each goal, the satisfaction function is introducedand the model maximizing minimum aspiration levels is proposed. …

    Scientiae Mathematicae Japonicae 68(1), 117-127, 2008-07-01

    J-STAGE  References (16)

  • A Near-Optimal Solution for the Vehicle Routing Problem with Multiple Use of Vehicles(<Special English Issue>Production and Logistics)

    OMURA Kazuhiko , MORIYAMA Hiroumi , HADA Takao

    … The vehicle routing problem with multiple use of vehicles is a variant of the classical vehicle routing problem in which vehicles can be used several times during a working day. … We propose a method to determine the lower bound of this problem by solving the degree-constrained minimum γ-tree problem and the 0-1 knapsack problem. …

    Journal of Japan Industrial Management Association 55(6), 360-370, 2005

    J-STAGE  References (11) Cited by (3)

  • Improvement of the Genetic Algorithm and its Application  [in Japanese]

    渡辺 勝正 [他]

    … Firstly, we introduce the GA, and compare the time of computation and the solution for traveling salesman problem (TSP) in the uses of one by one method with the GA. … Secondly on the knapsack problem, we discuss the ways of generating new genes by cross-over and mutation. … Thirdly, we apply the GA to find the minimum value of continuous functions, and propose a method of narrowing the range of new genes for increasing the precision of the solutions. …

    Memoirs of the Faculty of Engineering,Fukui University 40(1), p133-149, 1992-03

    IR 

Page Top