Union algorithms, for $k=2$ and larger, by Jeremy
Jérémy Barbay 27 Abr 201027/04/10 a las 16:48 hrs.2010-04-27 16:48:27
**** Union algorithms, for $k=2$ and larger, by Jeremy
<2010-04-27 Tue 14:30-16:00>
1) Union algorithms for $k=2$
- Hwang Lin's algorithm
- DLM/Alternation algorithm
- Relation to compression of sets
2) Union algorithms for $k>2$
- SVS (trivial)
- DLM Gap encoding of certificates: LB of $\Omega(C)$
(works on B-Trees too)
- DLM Algorithm: UB of $O(C)$
3) Trying to generalize it to the Intersection
- Certificate of an Intersection $C$
- Lower bound for Intersection $\Omega(C)$
- Other Lower Bound for Intersection $\Omega(kG)$
***** References
@Article{optimalMergingOf2ElementsWithNElements,
author = {F. K. Hwang and S. Lin},
title = {Optimal merging of 2 elements with n elements},
journal = {Acta Informatica},
year = {1971},
key = {},
OPTvolume = {1},
OPTnumber = {},
pages = {145--158},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
@Article{aSimpleAlgorithmForMergingTwoDisjointLinearlyOrderedSets,
author = {F. K. Hwang and S. Lin},
title = {A simple algorithm for merging two disjoint linearly ordered sets},
journal = {SIAM Journal of Computing},
year = {1972},
OPTkey = {},
volume = {1},
number = {1},
pages = {31--39},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
@Article{significantImprovementsToTheHwangLinMergingAlgorithm,
author = {G. K. Manacher},
title = {Significant improvements to the Hwang-Ling merging algorithm},
journal = {JACM},
year = {1979},
volume = {26},
number = {3},
pages = {434--440},
}
@article{twoProbabilisticResultsOnMerging,
author = {Wenceslas Fernandez de la Vega and Sampath Kannan and Miklos Santha},
title = {Two probabilistic results on merging},
journal = {SIAM J. Comput.},
volume = {22},
number = {2},
year = {1993},
issn = {0097-5397},
pages = {261--271},
doi = {dx.doi.org/10.1137/0222019},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
@article{averageCaseAnalysisOfTheMergingAlgorithmOfHwangAndLin,
author = "Wenceslas Fernandez de la Vega and Alan M. Frieze and Miklos Santha",
title = "Average-Case Analysis of the Merging Algorithm of Hwang and Lin",
journal = "Algorithmica",
volume = "22",
number = "4",
pages = "483-489",
year = "1998",
url = "citeseer.ist.psu.edu/274734.html"
}
@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}
}
<2010-04-27 Tue 14:30-16:00>
1) Union algorithms for $k=2$
- Hwang Lin's algorithm
- DLM/Alternation algorithm
- Relation to compression of sets
2) Union algorithms for $k>2$
- SVS (trivial)
- DLM Gap encoding of certificates: LB of $\Omega(C)$
(works on B-Trees too)
- DLM Algorithm: UB of $O(C)$
3) Trying to generalize it to the Intersection
- Certificate of an Intersection $C$
- Lower bound for Intersection $\Omega(C)$
- Other Lower Bound for Intersection $\Omega(kG)$
***** References
@Article{optimalMergingOf2ElementsWithNElements,
author = {F. K. Hwang and S. Lin},
title = {Optimal merging of 2 elements with n elements},
journal = {Acta Informatica},
year = {1971},
key = {},
OPTvolume = {1},
OPTnumber = {},
pages = {145--158},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
@Article{aSimpleAlgorithmForMergingTwoDisjointLinearlyOrderedSets,
author = {F. K. Hwang and S. Lin},
title = {A simple algorithm for merging two disjoint linearly ordered sets},
journal = {SIAM Journal of Computing},
year = {1972},
OPTkey = {},
volume = {1},
number = {1},
pages = {31--39},
OPTmonth = {},
OPTnote = {},
OPTannote = {}
}
@Article{significantImprovementsToTheHwangLinMergingAlgorithm,
author = {G. K. Manacher},
title = {Significant improvements to the Hwang-Ling merging algorithm},
journal = {JACM},
year = {1979},
volume = {26},
number = {3},
pages = {434--440},
}
@article{twoProbabilisticResultsOnMerging,
author = {Wenceslas Fernandez de la Vega and Sampath Kannan and Miklos Santha},
title = {Two probabilistic results on merging},
journal = {SIAM J. Comput.},
volume = {22},
number = {2},
year = {1993},
issn = {0097-5397},
pages = {261--271},
doi = {dx.doi.org/10.1137/0222019},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA},
}
@article{averageCaseAnalysisOfTheMergingAlgorithmOfHwangAndLin,
author = "Wenceslas Fernandez de la Vega and Alan M. Frieze and Miklos Santha",
title = "Average-Case Analysis of the Merging Algorithm of Hwang and Lin",
journal = "Algorithmica",
volume = "22",
number = "4",
pages = "483-489",
year = "1998",
url = "citeseer.ist.psu.edu/274734.html"
}
@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}
}
| Última Modificación | 27 Abr 201027/04/10 a las 16:53 hrs.2010-04-27 16:53:27 |
|---|---|
| Vistas Únicas | 0 |
| Compartir |
