Local search and approximation for combinatorial optimization 組合せ最適化問題の局所探索と近似手法

この論文をさがす

著者

    • 下薗, 真一 シモゾノ, シンイチ

書誌事項

タイトル

Local search and approximation for combinatorial optimization

タイトル別名

組合せ最適化問題の局所探索と近似手法

著者名

下薗, 真一

著者別名

シモゾノ, シンイチ

学位授与大学

九州大学

取得学位

博士 (理学)

学位授与番号

乙第6153号

学位授与年月日

1996-02-26

注記・抄録

博士論文

目次

  1. Abstract / p1 (0003.jp2)
  2. Contents / p5 (0007.jp2)
  3. 1 Introduction / p1 (0009.jp2)
  4. 2 Combinatorial Optimization and Approximation / p7 (0015.jp2)
  5. 2.1 Combinatorial Optimization Problems / p7 (0015.jp2)
  6. 2.2 Approximation Algorithms and Approximation Classes / p10 (0018.jp2)
  7. 2.3 L-reduction and Logical Characterizations of Problems / p14 (0022.jp2)
  8. 3 Local Search Algorithms / p20 (0028.jp2)
  9. 3.1 Local Search Strategy / p20 (0028.jp2)
  10. 3.2 Local Search Algorithm and the class PLS / p21 (0029.jp2)
  11. 3.3 PLS-completeness of Local Search Problems / p24 (0032.jp2)
  12. 4 Complexity of Finding Alphabet Indexing / p26 (0034.jp2)
  13. 4.1 Alphabet Indexing for Simplifying Strings / p27 (0035.jp2)
  14. 4.2 Alphabet Indexing Problem is NP-complete / p29 (0037.jp2)
  15. 4.3 Complexity of Reducing Indexing Alphabet / p31 (0039.jp2)
  16. 4.4 Local Search Algorithm for Alphabet Indexing / p36 (0044.jp2)
  17. 4.5 Discussion / p41 (0049.jp2)
  18. 5 Knowledge Acquisition with Alphabet Indexing from Amino Acid Se-quences / p43 (0051.jp2)
  19. 5.1 Algorithmic Learning Approach to Molecular Biology / p44 (0052.jp2)
  20. 5.2 Learning Algorithm and Optimization Problem / p46 (0054.jp2)
  21. 5.3 Experiments and Results / p52 (0060.jp2)
  22. 5.4 Discussion / p64 (0072.jp2)
  23. 6 Polynomial-time Approximation Algorithm for Alphabet Indexing / p65 (0073.jp2)
  24. 6.1 Distinguish Pairs of Strings by Alphabet Indexing / p66 (0074.jp2)
  25. 6.2 Approximability of Max K-Indexing Problem / p67 (0075.jp2)
  26. 6.3 Polynomial-time Approximation Algorithm for Max Indexing / p69 (0077.jp2)
  27. 6.4 Algorithm to Distinguish Strings in Tuples / p72 (0080.jp2)
  28. 6.5 Discussion / p77 (0085.jp2)
  29. 7 Hardness of Finding Maximum Subgraphs by Local Search / p78 (0086.jp2)
  30. 7.1 Hardness of Maximum Subgraph Problems / p79 (0087.jp2)
  31. 7.2 PLS-completeness of Weighted Greedy Maximal Subgraph Problem / p80 (0088.jp2)
  32. 7.3 Tight PLS-reductions and PSPACE-completeness / p88 (0096.jp2)
  33. 7.4 Discussion / p90 (0098.jp2)
  34. References / p91 (0099.jp2)
0アクセス

各種コード

  • NII論文ID(NAID)
    500000131645
  • NII著者ID(NRID)
    • 8000000966305
  • DOI(NDL)
  • NDL書誌ID
    • 000000295959
  • データ提供元
    • NDL-OPAC
    • NDLデジタルコレクション
ページトップへ