Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
スポンサーリンク
概要
- 論文の詳細を見る
Given an M×N array of reals, we want to find a rectangular contiguous subarray such that the sum of the entries in the subarray is maximized. Since Bentley posed this problem in his Programming Pearls column in 1984 with an O (NM 2) time solution, no progress on the sequential complexity has been reported to date. We give the first subcubic algorithm, by reducing the problem to “funny matrix multiplication”, where the scalar product and addition in usual matrix multiplication are replaced by addition and max operations, respectively. We also give a faster ε-approximation algorithm via the same reduction.
- 東北大学の論文
著者
-
玉木 久夫
明治大学理工学部情報科学科
-
Tamaki H
Department Of Computer Science Faculty Of Science And Engineering Meiji University
-
Tamaki Hisao
The School Of Science And Technology Meiji University
-
Tamaki Hisao
Department Of Computer Science Meiji University
-
Hisao Tamaki
Department Of Computer Science Meiji University.
-
Tokuyama Takeshi
Graduate School Of Information Science Tohoku University
関連論文
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- 点集合の距離重複度列のノルムと最大部分集合問題
- 密な部分グラフ問題の貪欲解法
- 放物線のアレンジメントの組合せ複雑度について
- 平面グラフの刻み幅決定アルゴリズムの小交差数グラフへの拡張に向けて
- 頂点彩色問題に対する列生成法アプローチの高速化
- テストパターンの静的圧縮における厳密解と貧欲解の比較(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
- 平面ユークリッドTSPの分割統治法ヒューリスティツクス
- 平面グラフの分枝幅決定アルゴリズムの効率的実装
- グラフ及び領域空間に関する大域丸めの幾何学的性質について
- 合成数のAKS witnessに関する実験的研究
- 小さな碁盤における囲碁の厳密解アルゴリズム
- TD-1-12 アルゴリズムデモ発見的動的計画法 : 巡回セールスマン問題を例として
- ハイパーキューブ上の順列の同形を反復しない網羅的生成
- 平面巡回セールスマン問題に対するアローラの近似アルゴリズムの効率的実装
- Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm)
- 障害物との交差数が少ない全域木
- パラメトリックなポリマトロイドとその幾何学的応用
- 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
- 巡回カメラマン問題とその自動光学的検査への応用
- 教育を目的としたC言語ソース管理APIの作成とその応用(e-learning/一般)
- JavaのeラーニングのためのEclipseプラグインの開発(e-learning/一般)
- 極小横断列挙のメモリ効率の良いアルゴリズム
- 2H-7 耐故障トーラス構成の一方式とシミュレーションによる評価
- Distance Trisector of a Segment and a Point
- Voronoi Diagrams with Respect to Criteria on Vision Information
- 単一根有向グラフと対称変換に基づいた囲碁の棋譜管理・閲覧システムの開発(セッション(1) : ゲーム情報学(1))
- 巡回セールスマン問題の近似アルゴリズム:天才アローラによる20年ぶりの急進展(近似アルゴリズムに関する最近の話題)
- 経路最適化問題の近似アルゴリズム : 幾何学的/非幾何学的場合の対比
- ハイパーキューブ上の単距離置換のルーティング
- 組合せ的解析における確率的手法
- Graph Orientation Problems for Multiple st-Reachability
- Quasi-Norms for a Double Sequence
- k-cyclic Orientations of Graphs
- On Detecting Digital Line Components in a Binary Image
- グラフの自動描画における交差を考慮した巨大近傍探索
- Reconstructing sets from distances given by graphs (コンピュテーション)
- Discrepancy-Based Digital Halftoning: Automatic Evaluation and Optimization
- Quantum Algorithms for Intersection and Proximity Problems
- Quantum Computation in Computational Geometry
- Routing a Permutation in the Hypercube by Two Sets of Edge-Disjoint Paths
- Combinatorics on Arrangements and Parametric Matroids : A Bridge between Computational Geometry and Combinatorial Optimization(Special Issue on Algorithm Engineering : Surveys)
- On Properties of a Set of Global Roundings Associated with Clique Connection of Graphs
- Algorithms for the Maximum Subarray Problem Based on Matrix Multiplication
- Approximation Algorithms for Geometric Optimization Problems(Special Issue on Algorithm Engineering : Surveys)
- Computing directed pathwidth in O(1.89n) time
- A Fast and Simple Subexponential Fixed Parameter Algorithm for One-Sided Crossing Minimization
- DS-1-11 An Algorithm for Optimally Locating Baselines using Quad Decomposition
- A Linear Edge Kernel for Two-Layer Crossing Minimization
- Search space reduction through commitments in pathwidth computation: an experimental study