臺灣博碩士論文加值系統

PASS是一個新的想法，用來分析跟設計演算法。
在PASS想法中，就是想要跳脫出用問題大小來判斷近似演算法的好壞。
利用最佳解去猜測近似解，但NP困難的問題通常不好找到最佳解，
所以PASS就是想利用可行解去得到近似解比例，
而我們這篇論文就是將所提到的理論比例拿出來探討，並且利用實驗的方式去實作。
我們利用PASS去分析貪婪演算法，並且去觀察實驗及理論的落差為何。

PASS approximation is a new framework to analyze and design algorithm.
There are two approximation ratios are proved from PASS approximation,
approximation ratio with the signature on optimal solution, and approximation
ratio with the signature on feasible solution. We verify the both approximation
ratio by implementing PASS approximation on maximum facility
location problem.Besides, we use PASS approximation to analyze greedy-rate
algorithm, and do experiments to compare approximation ratio and theoretical
ratio. We have interest in the theoretical ratio proved by PASS approximation
and verify the ratio via experiments.

1 Introduction
2 Related Work
2.1 Banner Advertising
2.2 Maximum Facility Location problem
2.3 Maximum Independent set problem
2.4 Maximizing Non-monotone Submodular Functions
3 A Framework for Analyzing and Design Heuristics
3.1 Maximum Facility Location and Minimum Facility Location
3.2 PASS approximation on Maximum Facility Location Problem
3.3 Approximation Ratio with Optimal Solution
4 PASS Approximation by Greedy-Rate Algorithm
4.1 Greedy-Rate Algorithm
5 Simulation
5.1 Environmental Setting
5.2 Experimental Result
5.2.1  value is small
5.2.2  value is large
6 Conclusion

[1] Uriel Feige, Nicole Immorlica, PVahab S. Mirrokni, Hamid Nazerzadeh,
“PASS Approximation: A Framework for Analyzing and Designing
Heuristics,” Algorithmica, 2013.
[2] Uriel Feige, Nicole Immorlica, PVahab S. Mirrokni, Hamid Nazerzadeh,
“A combinatorial allocation mechanism with penalties for banner advertising,”
In: Proceedings of the 17th International World Wide Web
Conference (WWW), 2008
[3] Uriel Feige, Nicole Immorlica, PVahab S. Mirrokni, Hamid Nazerzadeh,
“PASS Approximation: A Framework for Analyzing and Designing
Heuristics, Proceedings of 19th International Workshop Approximation
Algorithms for Combinatorial Optimization (APPROX), 2009.
[4] Hoefer, Martin. “Experimental comparison of heuristic and approximation
algorithms for uncapacitated facility location.” Experimental and
Efficient Algorithms. Springer Berlin Heidelberg, 2003.
[5] Uriel Feige, Vahab S. Mirrokni, Jan Vondrak, “Maximizing nonmonotone
submodular functionsF, SIAM Journal on Computing, 2011.
25
[6] Uriel Feige, Daniel Reichman,“Recoverable Values for Independent
SetsF, International Colloquium on Automata, Languages and Programming,
2011.
[7] Krause, Andreas, and Daniel Golovin. “Submodular function maximization.”
Tractability: Practical Approaches to Hard Problems 3 (2012).
[8] Kleinberg, Jon, Christos Papadimitriou, and Prabhakar Raghavan. “Segmentation
problems.” Proceedings of the thirtieth annual ACM symposium
on Theory of computing. ACM, 1998.
[9] Gerard Cornuejols, Marchall L.Fisher, George L. Nemhauser, ,“Location
of Bank Accounts to Optimize Float An Analytic Study of Exact and
Approximate AlgorithmsF, Management Science, 1977.
[10] Ageev, Alexander A., and M. I. Sviridenko. “An 0.828-approximation
algorithm for the uncapacitated facility location problem.” Discrete Applied
Mathematics 93.2 (1999): 149-156.
[11] LI, Shi. “A 1.488 approximation algorithm for the uncapacitated