著者

今井 浩

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会誌 (ISSN:09135693)

巻号頁・発行日

vol.79, no.9, pp.920-926, 1996-09-25

被引用文献数

5

---

アルゴリズム・計算量分野の成果として,多くの問題が本質的に解くことが難しいことが示されている.一方,本質的に解くのが難しいからこそ,実際に現れるそのような難しい問題をなんとか現実的時間内で良い精度で解くことが要求される.難しい問題を解く近似アルゴリズムの開発の世界では,最近種々の新しいアルゴリズム設計パラダイムの登場があった.本稿では,そのような近似アルゴリズム設計手法の代表的なものとして,線形計画法の主双対アプローチを近似アルゴリズム設計に拡張したもの,線形計画・半定値計画とランダム化を組み合わせたものの二つについて,集合と論理に関する難問を例題に解説する.