arXiv雑要約

• Top
• AI
• プログラム
• 画像・音声
• セキュリティ
• 数値解析

プログラム - 2026/03/26 公開

• 有限部分グラフの束におけるネスト構造を持たない正規形 [econ.TH, cs.AR, cs.CE, cs.ET, math.CT, cs.LO]目的：有限部分グラフの束におけるネスト条件の正規形

  • グラフ理論は，ネットワーク構造の分析に不可欠であり，様々な応用分野で重要である。
  • ネスト構造を持つ条件は，複雑で扱いづらく，効率的な処理が困難である。
  • ネスト構造を持たない正規形を確立し，条件の簡略化と処理効率の向上を目指す。
  • ネスト条件に対する，ネスト構造を持たない正規形を提示した。
  • この正規形を用いることで，条件の表現と評価が容易になる。

  Link: https://arxiv.org/abs/2601.18376

• メトリックTSPに対する厳密な完全性ギャップ計算の拡張 [math.CO, cs.DS]目的：巡回セールスマン問題の劣経路緩和における完全性ギャップの検証

  • TSPは組合せ最適化の古典的な問題であり，現実世界の様々な応用がある。
  • 劣経路緩和の完全性ギャップは，近似アルゴリズムの性能評価において重要である。
  • 本研究は，メトリックTSPに対する4/3予想の検証範囲を広げることを目指す。
  • n=10までの結果を BenoitとBoydの結果と一致させて確認した。
  • n=11とn=12において，劣経路多面体の極点リストが不完全であることを示した。
  • 一般の場合では最大14頂点，半整数頂点では最大17頂点まで極点の列挙を拡張した。

  Link: https://arxiv.org/abs/2603.12995

• 1
• 2
• 3