Geometric lower bounds for parametric matroid optimization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Geometric lower bounds for parametric matroid optimization

Full text

Pdf (758 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 662 - 671

Year of Publication: 1995

ISBN:0-89791-718-9

Author

David Eppstein

Department of Information and Computer Science, University of California, Irvine, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 14, Citation Count: 4

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/225058.225284 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	Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
	2	Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, The complexity and construction of many faces in arrangements of lines and of segments, Discrete & Computational Geometry, v.5 n.2, p.161-196, 1990 [doi>10.1007/BF02187784]
	3	D. Eppstein and D. S. Hirschberg. Choos-ing subsets with maximum weighted aver-age. Unpublished manuscript, 1995.
	4	P. Erdos, L. Lov&z, A. Simmons, and E. G. Straus. Dissection graphs of planar point sets. In A Survey of Com-binatorial Theory, pages 139-149. North-Holland, 1973.
	5	David Fernández-Baca , Giora Slutzki, Parametric Problems on Graphs of Bounded Tree-Width, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.304-316, July 08-10, 1992
	6	David Fernández-Baca , Giora Slutzki, Linear-Time Algorithms for Parametric Minimum Spanning Tree Problems on Planar Graphs, Proceedings of the Second Latin American Symposium on Theoretical Informatics, p.257-271, April 03-07, 1995
	7	Andrew V. Goldberg , Robert E. Tarjan, Finding minimum-cost circulations by canceling negative cycles, Journal of the ACM (JACM), v.36 n.4, p.873-886, Oct. 1989 [doi>10.1145/76359.76368]
	8	D. Gusfield. Bounds for the parametric spanning tree problem. In Proc. Humbolt Conf. Graph Theory, Combinatorics and Computmg, pages 173-183. Utilitas Math-ematical, 1979.
	9	Dan Halperin , Micha Sharir, On disjoint concave chains in arrangements of (pseudo) lines, Information Processing Letters, v.51 n.1, p.53-56, July 12, 1994 [doi>10.1016/0020-0190(94)00057-3]
	10	S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
	11	John Hershberger , Jack Snoeyink, Convex Polygons Made from Few Lines and Convex Decompositions of Polyhedra, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.376-387, July 08-10, 1992
	12	N. Katoh and T. Ibaraki. On the total number of pivots required for certain para-metric combinatorial optimization prob-lems. Technical Report Working Paper 71, Inst. Econ. Res., Kobe Univ. Commerce, 1983.
	13	N. Katoh, T. Tokuyama, and T. Ibaraki. On minimum and maximum spanning trees of linearly moving points. In Proc. 33rd IEEE Symp. Foundations of Com-puter Science, pages 396-405, 1992.
	14	L. Loviisz. On the number of halving lines. Ann. Univ. Sci. Budapest, Eotvos, Sect. Math., 14:107-108, 1971.
	15	George S. Lueker , Nimrod Megiddo , Vijaya Ramachandran, Linear programming with two variables per inequality in poly-log time, SIAM Journal on Computing, v.19 n.6, p.1000-1010, Dec. 1990 [doi>10.1137/0219068]
	16	János Pach , William Steiger , Endre Szemerédi, An upper bound on the number of planar K-sets, Discrete & Computational Geometry, v.7 n.2, p.109-123, 1992 [doi>10.1007/BF02187829]
	17	S. Toledo. Maximizing non-linear concave functions in fixed dimension. In Proc. 33rd IEEE Symp. Foundations of Com-puter Science, pages 676-685, 1992.
	18	Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]

CITED BY 4

	Hisao Tamaki , Takeshi Tokuyama, How to cut pseudo-parabolas into segments, Proceedings of the eleventh annual symposium on Computational geometry, p.230-237, June 05-07, 1995, Vancouver, British Columbia, Canada
	Takeshi Tokuyama, Minimax parametric optimization problems and multi-dimensional parametric searching, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.75-83, July 2001, Hersonissos, Greece
	David Fernández-Baca , Giora Slutzki , David Eppstein, Using sparsification for parametric minimum spanning tree problems, Nordic Journal of Computing, v.3 n.4, p.352-366, Winter 1996
	Naoki Katoh , Hisao Tamaki , Takeshi Tokuyama, Parametric polymatroid optimization and its geometric applications, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.517-526, January 17-19, 1999, Baltimore, Maryland, United States