AN APPROACH FOR WORST CASE ANALYSIS OF HEURISTICS : ANALYSIS OF A FLEXIBLE 0-1 KNAPSACK PROBLEM

スポンサーリンク

概要

• 論文の詳細を見る

• We introduce one technique for worst case analysis of heuristics. We use functions of continuous variables determined by the input data to represent the ratio of the solution value generated by an approximate algorithm (or a lower bound on it) over an upper bound on the optimal solution value. We then use standard mathematical techniques to analyze the function corresponding to the performance ratio. By taking the infimum of such function over all problem instances, the (tight) worst-case performance ratio of the algorithm is thus obtained. To illustrate the approach, we analyze a flexible 0-1 knapsack problem.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Lai Tsung-chyan

  College Of Management National Taiwan University

• Brandeau Margaret

  Stanford University

• Chiu Samuel

  Stanford University

関連論文

• AN APPROACH FOR WORST CASE ANALYSIS OF HEURISTICS : ANALYSIS OF A FLEXIBLE 0-1 KNAPSACK PROBLEM
• WORST-CASE ANALYSIS OF INDEXING RULES FOR SINGLE MACHINE SEQUENCING

スポンサーリンク