An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem
スポンサーリンク
概要
- 論文の詳細を見る
In this paper we present an algorithm to solve an as-yet untreated knapsack problem, the Multidimensional Multiple-choice Knapsack Problem (MMKP). Since our specific application occurs in the real-time domain, a solution for the MMKP with a small upper bound on the runtime is desirable. Thus, the Lagrange multiplier method is chosen, and a heuristic with a worst-case runtime behavior better than O(n^2m) is developed, n being the number of elements and m the number of dimensions. Extensive testing against an exact algorithm based on partial enumeration is used to establish the accuracy and efficiency of the heuristic.
- 社団法人電子情報通信学会の論文
- 1997-03-25
著者
-
Shiratori Norio
Graduate School of Information Sciences, Tohoku University
-
Moser Martin
Graduate School Of Information Science And Research Institute Of Electrical Communication Tohoku Uni
-
Moser Martin
Graduate School Of Information Science And Research Institue Of Electrical Communication Tohoku Univ
-
JOKANOVIC Dusan
Graduate School of Information Science and Research Institute of Electrical Communication, Tohoku Un
-
Shiratori Norio
Graduate School Of Information Sciences Tohoku University
-
Jokanovic Dusan
Graduate School Of Information Science And Research Institute Of Electrical Communication Tohoku Uni
-
Shiratori Norio
Graduate School Of Information Science And Research Institute Of Electrical Communication Tohoku Uni
-
Shiratori Norio
Graduate School of Global Information and Telecommunication Studies WASEDA University:Research Institute of Electrical Communication Tohoku University
関連論文
- Proposal and Performance Evaluation of Hash-based Authentication for P2P Network
- 新たな50年へ向けて-心に木を植える-
- Design of Adaptive Communication Mechanism for Ubiquitous Multiagent Systems
- Design of Adaptive Communication Mechanism for Ubiquitous Multiagent Systems
- WEB時代のイノベーションに向けた"技術的・社会的"課題
- 人の暮らしと自然のICTに基づいた共生へ向けて-「Kurihara」グリーンプロジェクト-
- 人の暮らしと自然のICTに基づいた共生へ向けて-「Kurihara」グリーンプロジェクト-
- WEB時代のイノベーションに向けた"技術的・社会的"課題
- An Algorithm for the Multidimensional Multiple-Choice Knapsack Problem
- DCAA : A Dynamic Constrained Adaptive Aggregation Method for Effective Network Traffic Information Summarization(Implementation and Operation)(Internet Technology IV)
- 移動ネットワーク環境におけるSNMPを用いた情報収集手法
- Estimation of Network Characteristics and Its Use in Improving Performance of Network Applications (Special Issue on Internet Technology and Its Applications)
- Efficient Channel Utilization Schemes for IEEE 802.11 DCF over MANET (特集:シームレスコンピューティングとその応用技術)
- Ensuring performance improvement of IEEE 802.11 with dynamical adjustment of RTS threshold (情報ネットワーク)
- 栗原グリーンプロジェクト - 環境負荷低減型のまちづくりを目指したICTシステムの構想 -
- 栗原グリーンプロジェクト - 広域分散地域におけるエネルギー管理システム -
- 栗原グリーンプロジェクト - グリーン指向管理情報ベース(G-MIB) -
- 栗原グリーンプロジェクト - スマートフォンを用いたパークアンドライド支援システム -
- 栗原グリーンプロジェクト - 環境負荷低減のための生活支援システム -
- Socio-familiar Personalized Serviceの提案とその応用 : 次世代ユビキタスサービスを実現するネットワークソフトウェアへ向けて(ネットワークソフトウェア技術とその応用論文)
- 個人情報を活用した人にやさしいサービスの実現方法に関する検討
- パーベイシブ環境におけるサービスの個人化とその応用
- Efficient Channel Utilization Schemes for IEEE 802.11 DCF over MANET
- Agent-based Intelligent Information Gathering on Large ScaleInformation Sources
- 利用者が所有する個人情報を活用したサービス横断的個人化方式の提案(ポストIPネットワーキング,新世代ネットワーク,ネットワークモデル,インターネットトラヒック,TCP/IP,マルチメディア通信,ネットワーク管理,リソース管理,プライベートネットワーク,NW安全性及び一般)
- On a Decision-Making Mechanism of an Intelligent Shopping Agent
- 災害に強いグリーン指向ネバーダイ・ネットワーク
- B-16-17 次世代グリーン指向ネットワーク管理技術(B-16.インターネットアーキテクチャ,一般セッション)
- B-14-2 グリーン指向ネットワーク管理に基づくセンサー連動型ICTシステムの省電力化(B-14.情報通信マネジメント,一般セッション)
- B-14-1 グリーン指向ネットワーク管理に基づくIP電話システムの省電力化(B-14.情報通信マネジメント,一般セッション)
- グリーン指向ネットワーク管理に基づくIP電話システムの省電力化に関する一検討
- Proposal and Performance Evaluation of Hash-based Authentication for P2P Network
- BS-1-36 G/D-MIB:A Proposal of Green-oriented Disaster-resistant Management Information Base