Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete AlgorithmsSIAM, 01.01.2003 - 874 Seiten From the January 2003 symposium come just over 100 papers addressing a range of topics related to discrete algorithms. Examples of topics covered include packing Steiner trees, counting inversions in lists, directed scale-free graphs, quantum property testing, and improved results for directed multicut. The papers were not formally refereed, but attempts were made to verify major results. Annotation (c)2003 Book News, Inc., Portland, OR (booknews.com) |
Inhalt
Selection with Monotone Comparison Costs | 10 |
Comparing Top k Lists | 28 |
Penalizing Long Delays | 47 |
Minimum Cost Flows over Time without Intermediate Storage | 66 |
On the Performance of User Equilibria in Traffic Networks | 86 |
Invited Plenary Abstract | 99 |
StraightSkeleton Based Contour Interpolation | 119 |
Directed ScaleFree Graphs | 132 |
Equitable Colorings with Constant Number of Colors | 458 |
Lower Bounds for CollusionSecure Fingerprinting | 472 |
Quantum Algorithms for Some Hidden Shift Problems | 489 |
Nonindependent Randomized Rounding | 506 |
Session | 523 |
Embedding kOuterplanar Graphs into l₁ | 527 |
Lower Bounds for External Memory Dictionaries | 546 |
The SetAssociative Cache Performance of Search Trees | 565 |
Perfect Matchings in Random Graphs with Prescribed Minimal Degree | 148 |
BranchWidth and Exponential Speedup | 168 |
Chain Decompositions and Independent Trees in 4Connected Graphs | 186 |
Online Learning in Online Auctions | 202 |
An Approximate Truthful Mechanism for Combinatorial Auctions with Single | 205 |
Session | 223 |
Approximation of Functions over Redundant Dictionaries Using Coherence | 243 |
An Improved Approximation Algorithm for the 0Extension Problem | 257 |
Integrality Ratio for Group Steiner Trees and Directed Steiner Trees | 275 |
Graded Conforming Delaunay Tetrahedralization with Bounded RadiusEdge | 295 |
Perturbations and Vertex Removal in a 3D Delaunay Triangulation | 313 |
Root Comparison Techniques Applied to Computing the Additively Weighted | 320 |
Smaller Explicit Superconcentrators | 340 |
A Spectral Technique for Random Satisfiable 3CNF Formulas | 357 |
Session | 374 |
Maintaining AllPairs Approximate Shortest Paths under Deletion of Edges | 394 |
Invited Plenary Abstract | 413 |
Approximation Algorithm for Embedding Metrics into a TwoDimensional Space | 434 |
On the Complexity of DistanceBased Evolutionary Tree Reconstruction | 444 |
Session | 583 |
Dynamic Generators of Topologically Embedded Graphs | 599 |
FullyDynamic Two Dimensional Orthogonal Range and Line Segment | 618 |
A New Approximation Algorithm for the Asymmetric TSP with Triangle | 638 |
Approximating Asymmetric Maximum | 646 |
Directed Graphs Requiring Large Numbers of Shortcuts | 665 |
Compact Representations of Separable Graphs | 679 |
On ACO Implementations of Fusion Trees and Atomic Heaps | 699 |
Fast Distributed Algorithms for Weakly Connected Dominating Sets and Linear | 717 |
FaultTolerant Facility Location | 735 |
Unconditional Proof of Tightness of Johnson Bound | 754 |
Dynamic Routing on Networks with FixedSize Buffers | 771 |
Scheduling Techniques for MediaonDemand | 791 |
SublinearTime Approximation of Euclidean Minimum Spanning Tree | 813 |
Session | 828 |
HighOrder EntropyCompressed Text Indexes | 841 |
The Similarity Metric | 863 |
Häufige Begriffe und Wortgruppen
adversary apply approximation algorithm assume auction block cache cell clauses combinatorial competitive ratio complexity Computer Science connected consider constant construction contains convex cost data structure define Delaunay Delaunay triangulation deletion denote diagram distance dynamic edge elements embedding endpoints exists factor fast memory flow follows function given graph G Hence histogram implies inequality input insertion integer interval least Lemma linear program lower bound matrix maximum metric spaces minimum node Note NP-hard O(log obtain online algorithm optimal packets pair partition permutation planar planar graphs points polynomial probability problem Proc Proof prove queries random random graph result rithm root sample satisfies sequence skip graph solution Steiner tree subgraph subset Symposium T₁ Theorem tion triangulation update upper bound v₁ variables vectors vertex vertices Voronoi Voronoi cell Voronoi diagram weight