近似アルゴリズムの研究

点击翻译按钮获取中文摘要

戸ヶ崎光敬,山崎浩一:"R上のpropre区間表現をZ上のunit区間表現へ変換するアルゴリズムについて",概要:区間グラフの区間表現において,区間の長さが全て等しいならばunit区間グラフと言い,また,どの区間も他の区間に真に含まれることがないとき,proper区間グラフと言う.数値線上の議論でproper区間グラフとunit区間グラフが等しいことは示されているが区間の長さを抑えた区間の両端点が整数になるような配置での証明はまだない.そこで我々は,実数上でのproper区間表現から,区間の端数が整数かつ区間の長さが高々n(nは頂点数)のunit区間表現を出力する,O(n^2)時間アルゴリズムを示した.戸ヶ崎光敬,山崎浩一:"Pathwidthがk,strong pathwidthがkのグラフに対するページナンバー",概要:pathwidthが高々kのグラフの集合に対するページナンバーがkであることと,strong pathwidthが高々kのグラフの集合に対するページナンバーは(3(k-1))/2と3[k/2]の間にあることを示した.長島弘幸,山崎浩一:"3次元直方体のintersection graphに対する独立点集合問題の近似困難について",概要:2次元直方体におけるintersection graphの最大独立点集合問題に対し,何も制限がつかない場合はNP困難でO(log n)近似可能,弱非包含の制限がつくと定数近似可能,サイズが全て等しいという制限の下では,PTASを持つことが知られている.弱非包含の制限の下で,PTASを持つか否かはまだ知られていない.本論分で,3次元において弱非包含の制限の下でもPTASを持たないことを示した.