Readings about Output Sensitive Complexity in Computational Geometry
- The Ultimate Planar Convex Hull Algorithm?
@article{kirkpatrick,
title = {The Ultimate Planar Convex Hull Algorithm?},
author = {David G. Kirkpatrick and Raimund Seidel},
journal = {SIAM J. Comput.},
year = {1986},
note = {15(1):287--299}
}
- Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions
Timothy M. Chan: Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions. Discrete & Computational Geometry 16(4): 361-368 (1996)
- Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems
Timothy M. Chan: Output-Sensitive Results on Convex Hulls, Extreme Points, and Related Problems. Discrete & Computational Geometry 16(4): 369-387 (1996)
- Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three.
Timothy M. Chan, Jack Snoeyink, Chee-Keng Yap: Output-Sensitive Construction of Polytopes in Four Dimensions and Clipped Voronoi Diagrams in Three. SODA 1995: 282-291
Readings about Adaptive Sorting
- A Survey of Adaptive Sorting Algorithms
@article{ estivillcastro92survey,
author = "Vladimir Estivill-Castro and Derick Wood",
title = "A Survey of Adaptive Sorting Algorithms",
journal = "ACM Computing Surveys",
volume = "24",
number = "4",
pages = "441--476",
year = "1992",
url = "citeseer.nj.nec.com/estivill-castro92survey.html"
}
- Sorting presorted files
@InProceedings{mehlhorn,
author = {Kurt Mehlhorn},
title = {Sorting presorted files},
booktitle = {Proceedings of the 4th GI-Conference on Theoretical Computer Science},
pages = {199--212},
year = {1979},
editor = {Springer},
volume = {67},
series = {Lecture Notes in Computer Science},
}
- A framework for adaptive sorting
@Article{petersson,
author = {Ola Petersson and Alistair Moffat},
title = {A framework for adaptive sorting},
journal = {Discrete Applied Mathematics},
year = {1995},
volume = {59},
pages = {153--179},
}
- Best sorting algorithm for nearly sorted lists
@Article{cook,
author = {C.R. Cook and D.J. Kim},
title = {Best sorting algorithm for nearly sorted lists},
journal = {Communication of ACM},
year = {1980},
volume = {23},
pages = {620--624},
}
Readings about Parameterized Complexity
- R. Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford, 2006.
(Habilitationsschrift)
- Parameterized Complexity Theory,
@book{parameterizedComplexityTheory,
author = {J. Flum and M. Grohe},
title = {Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)},
year = {2006},
isbn = {3540299521},
publisher = {Springer-Verlag New York, Inc.},
address = {Secaucus, NJ, USA},
}
Readings about Competitive Analysis
- A New Approach on Solving 3-Satisfiability
@inproceedings{rodosek96new,
author = "Rodosek",
title = "A New Approach on Solving 3-Satisfiability",
booktitle = "{AISMC}: International Conference on Artificial Intelligence and Symbolic Mathematical Computing",
year = "1996",
pages = "197-212",
url = "citeseer.nj.nec.com/article/rodosek96new.html"
}
- 3-Coloring in time O(1.3446^n): a no-MIS algorithm
@inproceedings{beigel95coloring,
author = "Richard Beigel and David Eppstein",
title = "3-Coloring in time ${O}(1.3446^{\textstyle n})$: a no-{MIS} algorithm",
booktitle = "36th {IEEE} Symposium on Foundations of Computer Science",
pages = "444--452",
year = "1995",
url = "citeseer.nj.nec.com/article/beigel95coloring.html" }
- On
the Separation and Equivalence of Paging Strategies", Spyros
Angelopoulos, Reza Dorrigiv, and A. Lopez-Ortiz. To appear in Proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2007.
Readings about Adaptive Intersection
- Adaptive set intersections, unions, and differences
@InProceedings{dlm,
author = {Erik~D.~Demaine and Alejandro~L{\'o}pez-Ortiz and J.~Ian~Munro},
title = {Adaptive set intersections, unions, and differences},
booktitle = {Proceedings of the $11^{th}$ ACM-SIAM Symposium on Discrete
Algorithms ({SODA})},
pages = {743--752},
year = {2000}
}
- Experiments on Adaptive Set Intersections for Text Retrieval Systems
@InProceedings{dlmAlenex,
author = {Erik~D.~Demaine and Alejandro~L{\'o}pez-Ortiz and J.~Ian~Munro},
title = {Experiments on Adaptive Set Intersections for Text Retrieval Systems},
booktitle = {Proceedings of the 3rd Workshop on Algorithm Engineering and Experiments,
Lecture Notes in Computer Science},
pages = {5--6},
year = {2001},
address = {Washington DC},
month = {January}
}
- Adaptive Intersection and t-Threshold Problems
@InProceedings{adaptiveIntersectionAndTThresholdProblems,
author = {J{\'e}r{\'e}my Barbay and Claire Kenyon},
title = {Adaptive Intersection and t-Threshold Problems},
booktitle = {Proceedings of the thirteenth ACM-SIAM Symposium On Discrete Algorithms ({SODA})},
key = {Adaptive Algorithms, Random Lower Bounds},
pages = {390--399},
year = 2002,
month = {January},
organization = {ACM-SIAM},
publisher = {ACM},
postscript = {http://www.lri.fr/~jeremy/Recherche/Intersection/Articles/intersection.ps.gz}
}
- Optimality of Randomized Algorithms for the Intersection Problem
@InProceedings{optimalityOfRandomizedAlgorithmsForTheIntersectionProblem,
author = {J{\'e}r{\'e}my Barbay},
title = {Optimality of Randomized Algorithms for the Intersection Problem},
booktitle = {Proceedings of the Symposium on Stochastic Algorithms, Foundations and Applications (SAGA)},
pages = {26--38},
year = 2003,
editor = {Andreas Albrecht },
volume = {2827 / 2003},
month = {November},
organization = {Lecture Notes in Computer Science (LNCS)},
publisher = {Springer-Verlag Heidelberg},
annote = {http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2827&spage=26}
}
Readings about Instance Optimality
-
@inproceedings{ fagin01optimal,
author = "Ronald Fagin and Amnon Lotem and Moni Naor",
title = "Optimal aggregation algorithms for middleware",
booktitle = "Symposium on Principles of Database Systems",
year = "2001",
url = "citeseer.ist.psu.edu/fagin01optimal.html"
}