単位正方形上の一意被覆問題に対する近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
次のように定められる単位正方形一意被覆問題に対する多項式時間近似スキームを与える.すなわち,平面上に点集合と軸平行な単位正方形の集合が与えられたとき,その正方形集合の部分集合を選び,できる限り多くの点がその中のただ一つの正方形で覆われるようにするという問題である.Erlebachとvan Leeuwen(2008)はこの問題を一意被覆問題の幾何版として導入し,既存研究における最良の近似比はvan Leeuwen(2009)による2であった.我々の近似スキームは予算付き版へ拡張可能である.
- 2012-06-14
著者
-
伊藤 健洋
東北大学大学院情報科学研究科
-
宇野 裕之
大阪府立大学理学系研究科
-
岡本 吉央
東京工業大学情報理工学研究科
-
中野 眞一
群馬大学工学部
-
上原 隆平
北陸先端科学技術大学院大学情報科学研究科
-
上原 隆平
駒澤大学自然科学教室
-
上原 隆平
北陸先端科学技術大学情報科学研究科
-
上原 降平
北陸先端科学技術大学院大学情報科学研究科
-
岡本 吉央
東京工業大学
-
岡本 吉央
豊橋技術科学大学情報工学系
-
岡本 吉央
東大総合文化
-
宇野 毅明
東京工業大学
-
宇野 毅明
東京工業大学経営工学専攻
-
岡本 吉央
ETH Zurich
-
宇野 毅明
東京工業大学システム科学
-
大舘 陽太
群馬大学工学部情報工学科
-
宇野 裕之
大阪府立大学理学系研究科情報数理科学専攻
-
宇野 裕之
大阪府立大学
-
岡本 吉央
東京大学大学院総合文化研究科
-
宇野 毅明
国立情報学研究所情報学プリンシプル研究系
-
伊藤 健洋
東北大学情報科学研究科
-
岡本 吉央
北陸先端科学技術大学院大学大学院教育イニシアティブセンター
-
宇野 毅明
国立情報学研
-
岡本 吉央
北陸先端科学技術大学院大学 大学院教育イニシアティブセンター
-
岡本 吉央
電気通信大学
-
大舘 陽太
北陸先端科学技術大学院大学
-
中野 眞一
群馬大学工学部情報工学科
関連論文
- 絵画的迷路作成アルゴリズムの改善 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 嘘を含む比較による最小値最大値発見アルゴリズム (アルゴリズムと計算機科学の数理的基盤とその応用)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- リスト辺彩色の再構成問題
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- 木の均一分割問題
- 需要点と供給点があるグラフの分割問題の近似可能性
- グラフの距離辺彩色アルゴリズム
- 需要点と供給点のあるグラフの分割
- 再構成問題の計算複雑さ
- 需要と供給の木の分割
- フォン・ノイマン (特集 現代数学に影響を与えた数学者)
- エレガントな解答をもとむ 解答--出題 2009年10月号
- 2-D-19 最長路問題に対する次数2以下の点の除去処理とその分枝限定法での利用(離散最適化)
- 1-D-5 最小費用全域木ゲームにおけるシャープレイ値計算の困難性(離散アルゴリズム(2))
- プトレマイオスグラフのラミナー構造とその応用
- ある限られたグラフクラスに対する最長路問題
- 絵画的迷路の作り方 (理論計算機科学の深化と応用)
- コーダルグラフの独立点集合の数えあげ問題
- スーパーコンピューティング・コンテスト2010
- Investigating Web Structure by Cliques and Stars (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
- RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- 木のL(2,1)-ラベリングに対するO(n^)時間アルゴリズム
- ウェブグラフ : その性質と利用(OR研究の最前線)
- 2-C-6 最長路問題に対する2連結成分分解にもとづく分枝限定法による厳密解法(グラフ・ネットワーク(1))
- 複数の交叉演算による遺伝的アルゴリズムの改良
- ファジィ決定木生成法 ファジィC4.5とその改良(その3) : 修正利得のパラメータを節点の深さとデータ数に応じて変化させる方法
- ファジィ索引とその類似データに基づく推論への応用
- ファジィ決定木生成法 ファジィC4.5とその改良(その2) : 節点に応じて修正利得を変化させる方法
- 幾何図形におけるアナロジーへのファジィ理論の応用 : 図形の変化の階層的決定法
- ネヴァンリンナ賞業績紹介 スピールマン (特集 国際数学者会議2010)
- 木の(p, q)-全ラベリング問題
- 重み付きグラフにおける石移動ゲームについて
- 支配集合数え上げ問題とグラフクラス
- 孤立クリークおよび孤立スター縮約ウェブグラフにおけるウェブ構造マイニング
- 最小費用全域木ゲーム(OR事典Wiki)
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- 完全グラフ上の最大辺素パス問題に対する貪欲近似アルゴリズム (最適化の数理とアルゴリズム)
- 凸幾何に対する貪欲算法 (最適化の数理科学)
- 嘘を含む比較による最小値最大値発見アルゴリズム
- 木の最小コスト辺彩色のマッチングへの帰着
- 「Cellチャレンジ2009」実施報告
- 適応的計算幾何 (計算幾何学と離散数学)
- 閾グラフの最小辺ランキング全域木について
- 「Cell チャレンジ2009」実施報告
- ルールの生成法と推論法を変化させる学習の拡張
- 幾何図形におけるアナロジーへのファジィ理論の応用
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
- 最小辺ランキング全域木問題について
- On Minimum Edge Ranking Spanning Trees
- ランダム有向グラフにおける到達可能性と推移閉包の大きさについて
- 関係の推移閉包の大きさの近似的推定法
- グラフの距離辺彩色アルゴリズム
- ルールの生成法と推論法を変化させる学習の拡張 : 保有するデータ数を制限する場合
- Reconfiguration of list edge-colorings in a tree (コンピュテーション)
- 需要点と供給点のある木のコスト最小分割
- ファジィ索引とその類似データ検索への応用
- 二分タングルグラムの描き方 (列挙問題に対する計算の高速化と可視化)
- コンピュータサイエンス教科書シリーズ19数理計画法, 加藤直樹(著), コロナ社(2008-01), A5判, 定価(本体2,800円+税)
- コーダルサンドイッチの列挙, ランダム生成, 数え上げについて (理論計算機科学の深化 : 新たな計算世界観を求めて)
- 反転数を考慮したクイックソートの計算量解析
- 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- 間違えても大丈夫な凸包構成アルゴリズム
- 部分集合和遷移問題の多項式時間近似スキーム
- 木の最小コスト辺彩色のマッチングへの帰着
- 需要点と供給点のある木のコスト最小分割
- 定数ラウンドで復元可能な合理的秘密分散
- 木のリスト辺彩色の遷移可能性
- 部分集合和遷移問題の多項式時間近似スキーム
- レベル付き木の描画における頂点角解像度と交差角解像度
- 木,カクタスにおける点被覆の遷移可能性 (コンピュテーション)
- Rational Secret Sharing for Non-Simultaneous Channels (情報理論)
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 1.列挙の基本と基礎的なアルゴリズム(広がる列挙の技術-列挙による問題解決アプローチ-)
- 木,カクタスにおける点被覆の遷移可能性
- 非協力ゲーム(基礎編)
- 『計算機科学者のためのゲーム理論入門』シリーズについて
- DS-1-9 グラフのL(2,1)ラベリングの遷移可能性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 施設配置ゲームにおける仁・シャープレイ値の計算について (Theoretical Foundations of Computing)
- 大学院における研究室教育の構造化へ向けて (II. 活動報告 . (2) 質保証枠組みの方策)
- 非協力ゲーム(発展編)
- JAIST創立20周年記念シンポジウム報告 (III. センター関連イベント報告 . (1) JAIST創立20周年記念シンポジウム)
- 4つの教育ポリシー&ガイドラインを基盤としたJAISTにおける国際的質保証に向けた提案 (II. 活動報告 . (2) 質保証枠組みの方策)
- メカニズムデザイン(基礎編)
- 費用2種類の施設配置ゲームの仁とシャープレイ値の計算について
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- グラフ上の拡散競争ゲームの計算複雑さ
- 非同時通信路における合理的秘密分散(情報セキュリティ)
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- グラフを通したパズル・ゲームの一般化(娯楽のOR)
- 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
- 施設配置ゲームにおける仁・ジャープレイ値の計算について
- トロミノ詰込問題の計算複雑さについて
- エレガントな解答をもとむ 解答 : 出題 2013年2月号
- 近似のアルゴリズムと数理計画法 : 最近の進展 (特集 P≠NP予想最前線)
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)
- 次数指定した最大正則誘導部分グラフ探索問題(一般)