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

Access this Article

Search this Article

Author

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

Bibliographic Information

Title

Local search and approximation for combinatorial optimization

Other Title

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

Author

下薗, 真一

Author(Another name)

シモゾノ, シンイチ

University

九州大学

Types of degree

博士 (理学)

Grant ID

乙第6153号

Degree year

1996-02-26

Note and Description

博士論文

Table of Contents

  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)
1access

Codes

  • NII Article ID (NAID)
    500000131645
  • NII Author ID (NRID)
    • 8000000966305
  • DOI(NDL)
  • NDLBibID
    • 000000295959
  • Source
    • NDL ONLINE
    • NDL Digital Collections

Export

Page Top