|
 ABSTRACT
Simple, polynomial-time, heuristic algorithms for finding approximate solutions to various polynomial complete optimization problems are analyzed with respect to their worst case behavior, measured by the ratio of the worst solution value that can be chosen by the algorithm to the optimal value. For certain problems, such as a simple form of the knapsack problem and an optimization problem based on satisfiability testing, there are algorithms for which this ratio is bounded by a constant, independent of the problem size. For a number of set covering problems, simple algorithms yield worst case ratios which can grow with the log of the problem size. And for the problem of finding the maximum clique in a graph, no algorithm has been found for which the ratio does not grow at least as fast as 0(n&egr;), where n is the problem size and &egr;> 0 depends on the algorithm.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
 |
1
|
|
| |
2
|
M. R. Garey , R. L. Graham , J. D. Ullman, Worst-case analysis of memory allocation algorithms, Proceedings of the fourth annual ACM symposium on Theory of computing, p.143-150, May 01-03, 1972, Denver, Colorado, United States
[doi> 10.1145/800152.804907]
|
| |
3
|
D.S. Johnson, "Fast allocation algorithms", PROCEEDINGS 13th Annual IEEE Symp. on Switching and Automata Theory.
|
| |
4
|
D. S. Johnson, "Near-optimal bin packing algorithms", Doctoral Thesis (in preparation).
|
| |
5
|
R.M. Karp, "Reducibility among combinatorial problems", COMPLEXITY OF COMPUTER COMPUTATIONS, R.E. Miller and J.W. Thatcher, eds. Plenum Press, New York, 1972.
|
| |
6
|
J.H. Spencer, private communication.
|
| |
7
|
D.J.A. Welsh and M.B. Powell, "An upper bound to the chromatic number of a graph and its application to time-tabling problems", The Computer Journal, Vol 10 (1967), p. 85.
|
| |
8
|
D.C. Wood, "A technique for coloring a graph applicable to large scale time-tabling problems" The Computer Journal, Vol 12 (1969), p. 317.
|
CITED BY 18
|
|
M. R. Garey , D. S. Johnson , L. Stockmeyer, Some simplified NP-complete problems, Proceedings of the sixth annual ACM symposium on Theory of computing, p.47-63, April 30-May 02, 1974, Seattle, Washington, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Minho Shin , Arunesh Mishra , William A. Arbaugh, Improving the latency of 802.11 hand-offs using neighbor graphs, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA
|
|
|
Fang Yu , T. V. Lakshman , Martin Austin Motoyama , Randy H. Katz, SSA: a power and memory efficient scheme to multi-match packet classification, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
|
|
|
|
|
|
|
|
|
|
|
|
Marcin Sydow , Francesco Bonchi , Carlos Castillo , Debora Donato, Optimising topical query decomposition, Proceedings of the 2009 workshop on Web Search Click Data, p.43-47, February 09-09, 2009, Barcelona, Spain
|
|
|
Jiefeng Cheng , Jeffrey Xu Yu , Xuemin Lin , Haixun Wang , Philip S. Yu, Fast computing reachability labelings for large graphs with high compression rate, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
|
|
|
Francesco Bonchi , Carlos Castillo , Debora Donato , Aristides Gionis, Topical query decomposition, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sorabh Gandhi , Suman Nath , Subhash Suri , Jie Liu, GAMPS: compressing multi sensor data by grouping and amplitude scaling, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
G.2