Approximating the bandwidth via volume respecting embeddings (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximating the bandwidth via volume respecting embeddings (extended abstract)

Full text

Pdf (1.44 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 90 - 99

Year of Publication: 1998

ISBN:0-89791-962-9

Author

Uriel Feige

Department of Applied Math and Computer Science, The Weizmann Institute, Rehovot 76100, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 45, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/276698.276716 What is a DOI?

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	S, Assman, G. Peck, M. Syslo, J Zah. "The bandwidth of caterpillars with hairs of length 1 and 2". SIAM Y. Al#ebraic Discrete Methods 2 (1981), 387-393.
	2	Gunter Blache , Marek Karpinski , Wirtgen, J\urgen, On Approximation Intractability of the Bandwidth Problem, University of Bonn, 1997
	3	Avrim Blum , Goran Konjevod , R. Ravi , Santosh Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.100-105, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276717]
	4	Hans L. Bodlaender , Michael R. Fellows , Michael T. Hallett, Beyond NP-completeness for problems of bounded width (extended abstract): hardness for the W hierarchy, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.449-458, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195229]
	5	J, Bourgain, "On Lipschitz embedding of finite metric spaces in Iiilbert space". Israel J. Math. 52 (1985) 46- 5~o,
	6	P. China, J. Chvatalova, A. Dewdney, N. Gibbs. "The bandwidth problem for graphs and matrices- a survey''. Journal of Graph Theory, 6 (198~), ~~$-~5~.
	7	F. R. Chung , P. D. Seymour, Graphs with small bandwidth and cutwidth, Discrete Mathematics, v.75 n.1-3, p.113-119, 1989 [doi>10.1016/0012-365X(89)90083-6]
	8	:I. Chvatalova. On the bandwidth problem for graphs, Ph.D. dissertation, University of Waterloo, 1980.
	9	E. Cuthill , J. McKee, Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th national conference, p.157-172, August 26-28, 1969 [doi>10.1145/800195.805928]
	10	P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
	11	M. Garey, It. Graham, D. Johnson, D. Knuth. "Cornplexity results for bandwidth minimization". SIAM J. Appl. Math. $4 (197a), 477-495.
	12	Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
	13	M. Grotschel, L. Lovasz, A. Schrijver. Geometric .4,1- gorithms and Combinatorial Optimization. Springer- Verlag, Berlin, 1987.
	14	E. Ourari, I. Sudborough. "Improved dynamic programming algorithms for bandwidth minimization and the rain-cut linear arrangement problems". J. A19orithms, 5 (I98j), 531-546.
	15	J. Haralambides, F. Makedon, B. Monien. ~Bandwidth minimization: an approximation algorithm for caterpillass". Math Systems Theory 24, 169.177 (1991).
	16	Marek Karpinski , Wirtgen, J\urgen , Alexander Zelikovsky, An Approximation Algorithm for the Bandwidth Problem on Dense Graphs, University of Bonn, 1997
	17	Ton Kloks , Dieter Kratsch , Haiko Müller, Approximating the Bandwidth for Asteroidal Triple-Free Graphs, Proceedings of the Third Annual European Symposium on Algorithms, p.434-447, September 25-27, 1995
	18	Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
	19	Dieter Kratsch, Finding the minimum bandwidth of an interval graph, Information and Computation, v.74 n.2, p.140-158, Aug. 1987 [doi>10.1016/0890-5401(87)90028-9]
	20	P. M. Gruber, C. G. Lekkerkerker. Geometry of Numbers. Second edition, 1987. North Holland Mathematical Library, Volume 37.
	21	Jeffrey C. Lagarias, Point lattices, Handbook of combinatorics (vol. 1), MIT Press, Cambridge, MA, 1996
	22	N. Linial, E. London, Y. Rabinovich. "The geometry of graphs and some of its algorithmic applications". Combinatorica 15 (~) (1995) ~15-~~45.
	23	Burkhard Monien, The bandwidth minimization problem for caterpillars with hair length 3 is NP-complete, SIAM Journal on Algebraic and Discrete Methods, v.7 n.4, p.505-512, Oct. 1986 [doi>10.1137/0607057]
	24	C. Papadimitriou. "The NP-completeness of the bandwidth minimization problem". Computing 16 (1976), ~65-~70.
	25	L. A. Santalo. Integral Geometry and Geometric Probability. Encydopedia of Mathematics and its Applications, Volume 1, Addison Wesley, 1976.
	26	j. Saxe. ~Dynamic programming algorithms for recognizing small-bandwidth graphs in polynomial time". SIAM Journal on Algebraic Methods 1 (1980), $65-869.
	27	G. Strang. Linear Algebra and its Applications, Third Edition. Saunders College PublisMng, Harcourt Brace Jovanovich College Publishers, 1988.
	28	Jonathan S Turner, On the probable performance of Heuristics for bandwidth minimization, SIAM Journal on Computing, v.15 n.2, p.561-580, May 1986 [doi>10.1137/0215041]

CITED BY 11

	Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States
	Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000
	Ilan Newman , Yuri Rabinovich, A lower bound on the distortion of embedding planar metrics into Euclidean space, Proceedings of the eighteenth annual symposium on Computational geometry, p.94-96, June 05-07, 2002, Barcelona, Spain
	Sanjeev Arora, The approximability of NP-hard problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.337-348, May 24-26, 1998, Dallas, Texas, United States
	Anupam Gupta, Improved bandwidth approximation for trees, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.788-793, January 09-11, 2000, San Francisco, California, United States
	Avrim Blum , Goran Konjevod , R. Ravi , Santosh Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.100-105, May 24-26, 1998, Dallas, Texas, United States
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, Approximating metrics by tree metrics, ACM SIGACT News, v.35 n.2, June 2004
	Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Journal of Computer and System Sciences, v.69 n.3, p.485-497, November 2004
	Adam Kalai , Santosh Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, v.71 n.3, p.291-307, October 2005
	Moses Charikar , Konstantin Makarychev , Yury Makarychev, A divide and conquer algorithm for d-dimensional arrangement, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.541-546, January 07-09, 2007, New Orleans, Louisiana