NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
スポンサーリンク
概要
- 論文の詳細を見る
We propose a 0.935-approximation algorithm for MAX 2SAT and a 0.863-approximation algorithm for MAX DICUT. The approximation ratios improve upon the recent results of Zwick, which are equal to 0.93109 and 0.8596434254 respectively. Also proposed are derandomized versions of the same approximation ratios. We note that these approximation ratios are obtained by numerical computation rather than theoretical proof. The algorithms are based on the SDP relaxation proposed by Goemans and Williamson but do not use the 'rotation' technique proposed by Feige and Goemans. The improvements in the approximation ratios are obtained by the technique of 'hyperplane separation with skewed distribution function on the sphere.'
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
Matsui Tomomi
University of Tokyo
-
松井 知己
東京大学大学大学院 情報理工学系研究科 数理情報学専攻
-
松井 知己
東京大学 大学院情報理工学系研究科
-
Matuura S
University Of Tokyo
-
Matuura Shiro
University Of Tokyo
関連論文
- 古典的オーヴァーハングパズルをLPで解く(ORメモランダム)
- パズル・ゲームに見る悪魔の証明
- LINEAR TIME APPROXIMATION ALGORITHM FOR MULTICOLORING LATTICE GRAPHS WITH DIAGONALS
- スポーツスケジューリング
- 木における消防士問題に対する近似アルゴリズムの改良
- 統計的機械翻訳におけるフレーズ対応最適化を利用したN-best翻訳候補のリランキング
- オークションの設計理論とOR(2)(数理計画の理論と実装)
- 数理計画の理論と実装 : オークションの設計理論とOR(1)(ネットワークシステムのセキュリティ評価と危機管理)
- Integer programming for a phrase alignment problem on statistical machine translation (21世紀の数理計画--最適化モデルとアルゴリズム--RIMS研究集会報告集)
- 解けないパズルをLPで解く : ペグソリティアとパゴダ関数と線形計画(ORメモランダム)
- 新入生のための数学ブートキャンプ(後編)
- 新入生のための数学ブートキャンプ(前編)
- DS-1-3 閉ジャクソンネットワークに対するMCMC法(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 完璧にサンプリングしよう! : 第三話 終わりある未来
- 完璧にサンプリングしよう! : 第二話 天と地の狭間で
- Perfectness and Multicoloring of Unit Disk Graphs on Triangular Lattice Points (Theoretical Computer Science and its Applications)
- 完璧にサンプリングしよう! : 第一話 遥かなる過去から
- スポーツスケジューリング : 未解決問題を中心に
- 閉ジャクソンネットワークに対するパーフェクトサンプリング法
- 三角格子点上の単位円グラフに対する多重彩色
- 閉ジャクソンネットワークに対するパーフェクトサンプリング法
- 三角格子点上の単位円グラフに対する多重彩色
- 離散化Dirichlet分布に従うパーフェクトサンプリング
- $m×n$分割表の近似数え上げスキームの提案 (計算機科学基礎理論の新展開)
- Dirichlet分布に従う多項式時間近似サンプリング法(マルコフ連鎖)
- ディジタルハーフトーニング : ネットワークフローアルゴリズムによる最適化
- Dirichlet分布のrapidly mixing approximate sampler
- Dirichlet 分布の rapidly mixing approximate sampler
- Successful Manipulation in Stable Marriage Model with Complete Preference Lists
- 2-C-14 Cheating Strategies for Gale-Shapley Algorithm with Complete Preference Lists
- 重みつきマトロイドのK番目に重い基を求める
- 偽金貨を探そう(高校生のためのOR)
- A note on Asymmetric Power Index for Voting Games
- A note on mixed level supersaturated designs
- Approximate Counting Scheme for m×n Contingency Tables(Foundations of Computer Science)
- Dependent Randomized Rounding to the Home-Away Assignment Problem in Sports Scheduling(Discrete Mathematics and Its Applications)
- Home-Away Table Feasibility Problem
- Notes on Equitable Round-Robin Tournaments(Special Section on Discrete Mathematics and Its Applications)
- Polynomial time approximate or perfect samplers for discretized Dirichlet distribution
- A Linear Relaxation for Hub Network Design Problems(Special Section on Discrete Mathematics and Its Applications)
- Linear Relaxation for Hub Network Design Problems
- Farkasの補題と双対定理の初等的証明
- DS-1-8 Randomized Approximation Scheme for Estimating Critical Path Length of Stochastic PERT Network
- Cheating Strategies for the Gale-Shapley Algorithm with Complete Preference Lists
- 1993年Jリーグの再スケジューリング
- 0.935-Approximation Randomized Algorithm for MAX 2SAT and Its Derandomization
- スポーツのスケジューリング (スポーツの戦術とマネジメント)
- NEW APPROXIMATION ALGORITHMS FOR MAX 2SAT AND MAX DICUT
- Note on Equitable Round-Robin Tournaments
- A SURVEY OF ALGORITHMS FOR CALCULATING POWER INDICES OF WEIGHTED MAJORITY GAMES
- MAX DICUT問題の近似解法 (計算理論とアルゴリズムの新展開)
- Arrowの一般可能性定理の証明の解説
- 半正定値計画を描いた最大カット問題.878近似解法
- 和音に対するピアノ運指決定法 (最適化手法の深化と広がり)
- 2-K-7 スライディングブロックパズルを用いた画像再構築(ワークショップ「娯楽のOR-エンターテイメントの数理」)
- 数理ゲームの必勝法とイカサマの技(パズルとゲームの計算理論)
- チャネル割当問題の解法
- チャンネル割当問題の解法
- 特集にあたって(ランキングとレイティング)
- 世界の合言葉は林 : Bridge ItとConnections必勝法
- 不動点定理によるドロネー性の確認
- Is a Given Flow Uncontrollable? (Special Section on Discrete Mathematics and Its Applications)
- 1-B-5 Lower Bounds for Bruss' Odds Problem with Multiple Stoppings
- 相補スラック定理から入ってみたら
- 2×n型双行列ゲームのNash均衡点を求める図解法
- 単位円グラフ上の最大独立集合問題の近似解法
- NP-completeness of Arithmetical Restorations (Preprint)
- 2-C-3 不動点定理によるドロネー性の確認(離散最適化(2))
- 半正定値緩和法を用いた LELECUT トリプルパターニングのためのレイアウト分割手法