Date
|
Time
|
Event
|
Location
|
Saturday, January 11, 2003 | |||
7:30 AM - 6:30 PM | Registration |
Pre-Function Area
|
|
6:00 PM - 8:00 PM | Welcome Reception |
Maryland Suite
|
|
Sunday January 12, 2003 | |||
7:30 AM - 4:30 PM | Registration |
Pre-Function Area
|
|
8:30 AM - 9:20 AM | Continental Breakfast |
Constellation A
|
|
9:30 AM - 11:10 AM |
CONCURRENT SESSIONS
|
||
Session 1A 9:30 AM - Optimal Parallel Selection 9:55 AM - Selection with Monotone Comparison Costs 10:20 AM - Property Testing of Data Dimensionality 10:45 AM - Comparing Top K Lists |
Constellation C
|
||
Session 1B 9:30 AM - Algorithms for Power Savings 9:55 AM - Dynamic TCP Acknowledgement: Penalizing
Long Delays 10:20 AM - Approximately Optimal Control of Fluid
Networks 10:45 AM - Minimum Cost Flows Over Time without Intermediate
Storage |
Constellation D
|
||
Session 1C
9:30 AM - Sublogarithmic Approximation for Telephone
Multicast: Path out of Jungle 9:55 AM - On the Performance of User Equilibria in
Traffic Networks 10:20 AM - Faster Approximation Algorithms for the
Minimum Latency Problem 10:45 AM - Data Migration to Minimize the Average
Completion Time |
Constellation E
|
||
11:10 AM - 11:30 AM | Coffee Break |
Constellation A
|
|
11:30 AM - 12:30 PM |
Session 2 - IP#1 Browsing Around a Digital Library |
Constellation B
|
|
12:30 PM - 2:00 PM | Luncheon |
Constellation A
|
|
2:00 PM - 3:40 PM |
CONCURRENT SESSIONS
|
||
Session 3A 2:00 PM - Binary Space Partitions for 3D Subdivisions 2:25 PM - Allocating Vertex pi-guards in Simple Polygons
via Pseudo-Triangulations 2:50 PM - Straight-Skeleton Based Contour Interpolation 3:15 PM - Mobius-Invariant Natural Neighbor Interpolation |
Constellation C
|
||
Session 3B
2:00 PM - Improved Bounds on the Average Length of
Longest Common Subsequences 2:25 PM - Directed Scale-Free Graphs 2:50 PM - The Cover Time of Sparse Random Graphs 3:15 PM - Perfect Matchings in Random Graphs with
Prescribed Minimal Degree |
Constellation D
|
||
Session 3C
2:00 PM - Certifying Algorithms for Recognizing Interval
Graphs and Permutation Graphs 2:25 PM - Dominating Sets in Planar Graphs: Branch-Width
and Exponential Speed-up 2:50 PM - Quick and Good Facility Location 3:15 PM - Chain Decompositions and Independent Trees
in 4-Connected Graphs |
Constellation E
|
||
3:40 PM - 4:05 PM |
Coffee Break |
Constellation A
|
|
4:05 PM - 5:45 PM |
CONCURRENT SESSIONS
|
||
Session 4A - Constellation C
4:05 PM - Optimizing Misdirection 4:30 PM - Online Learning in Online Auctions 4:55 PM - An Approximate Truthful Mechanism for Combinatorial
Auctions with Single Parameter Agents 5:20 PM - Competitiveness via Consensus |
Constellation C
|
||
Session 4B
4:05 PM - Pass Efficient Algorithms for Approximating
Large Matrices 4:30 PM - Rangesum Histograms 4:55 PM - Approximation of Functions Over Redundant
Dictionaries Using Coherence 5:20 PM - Counting Inversions in Lists |
Constellation D
|
||
Session 4C
4:05 PM - Certifying and Repairing Solutions to Large
LPs -- How Good are LP-Solvers? 4:30 PM - An Improved Approximation Algorithm for
the 0-Extension Problem 4:55 PM - Packing Steiner Trees 5:20 PM - Integrality Ratio for Group Steiner Trees
and Directed Steiner Trees |
Constellation E
|
||
Monday January 13, 2003 | |||
7:30 AM - 4:30 PM | Registration |
Pre-Function Area
|
|
8:00 AM - 8:50 AM | Continental Breakfast |
Constellation A
|
|
9:00 AM - 11:05 AM |
CONCURRENT SESSIONS
|
||
Session 5A
9:00 AM - The Flow Complex: A Data Structure for Geometric
Modeling 9:25 AM - Graded Conforming Delaunay Tetrahedralization
with Bounded Radius-Edge Ratio 9:50 AM - On the Combinatorial Complexity of Euclidean
Voronoi Cells and Convex Hulls of d-Dimensional Spheres 10:15 AM - Perturbations and Vertex Removal in a 3D
Delaunay Triangulation 10:40 AM - Root Comparison Techniques Applied to Computing
the Additively Weighted Voronoi diagram |
Constellation C
|
||
Session 5B
9:00 AM - Random Walks on the Vertices of Transportation
Polytopes with Constant Number of Sources 9:25 AM - Smaller Explicit Superconcentrators 9:50 AM - A (1+\epsilon)Ε-Approximation Algorithm
for Partitioning Hypergraphs Using a New AlgorithmicVersion of the Lovász
Local Lemma 10:15 AM - A Spectral Technique for Random Satisfiable
3CNF Formulas 10:40 AM - Random MAX 2-SAT and MAX CUT |
Constellation D
|
||
Session 5C
9:00 AM - Space-Efficient Finger Search on Degree-Balanced
Search Trees 9:25 AM - Skip Graphs 9:50 AM - Maintaining All-Pairs Approximate Shortest
Paths under Deletion of Edges 10:15 AM - A Faster and Simpler Fully Dynamic Transitive
Closure |
Constellation E
|
||
11:05 AM - 11:30 AM | Coffee Break |
Constellation A
|
|
11:30 AM - 12:30 PM |
Session 6 - IP#2 Data Streams: Algorithms and Applications |
Constellation B
|
|
12:30 PM - 2:00 PM | Lunch (Attendees on their own) | ||
2:00 PM - 3:40 PM |
CONCURRENT SESSIONS
|
||
Session 7A
2:00 PM - Sparse Distance Preservers and Additive
Spanners 2:25 PM - Multi-Embedding and Path Approximation of
Metric Spaces 2:50 PM - Approximation Algorithm for Embedding Metrics
into a Two-Dimensional Space 3:15 PM - On the Complexity of Distance-based Evolutionary
Tree Reconstruction |
Constellation C
|
||
Session 7B
2:00 PM - Improved Results for Directed Multicut 2:25 PM - Algorithms for k-Colouring and Finding Maximal
Independent Sets 2:50 PM - Equitable Colorings with Constant Number
of Colors 3:15 PM - Better Performance Bounds for Finding the
Smallest $k$-Edge Connected Spanning Subgraph of a Multigraph |
Constellation D
|
||
Session 7C
2:00 PM - A Note on the Set Systems used for Broadcast
Encryption 2:25 PM - Lower Bounds for Collusion-Secure Fingerprinting 2:50 PM - Quantum Property Testing 3:15 PM - Quantum Algorithms for Some Hidden Shift
Problems |
Constellation E
|
||
3:40 PM - 4:05 PM | Coffee Break |
Constellation A
|
|
4:05 PM - 5:45 PM |
CONCURRENT SESSIONS
|
||
Session 8A
4:05 PM - Simultaneous Optimization for Concave Costs:
Single Sink Aggregation or Single Source Buy-at-Bulk 4:30 PM - Non-independent Randomized Rounding 4:55 PM - Minimizing Weighted Flow Time 5:20 PM - A Combinatorial Algorithm for Computing
a Maximum Independent Set in a t-Perfect Graph |
Constellation C
|
||
Session 8B
4:05 PM - Lower Bounds for Embedding of Edit Distance
into Normed Spaces 4:30 PM - Embedding k-Outerplanar Graphs into ell_1 4:55 PM - Embeddings and Non-approximability of Geometric
Problems 5:20 PM - Better Algorithms for High-dimensional Proximity
Problems via Asymmetric Embeddings |
Constellation D
|
||
Session 8C
4:05 PM - Lower Bounds for External Memory Dictionaries 4:30 PM - Online Paging with Limited Associativity 4:55 PM - The Set-Associative Cache Performance of
Search Trees 5:20 PM - Computing Strongly Connected Components
in a Linear Number of Symbolic Steps |
Constellation E
|
||
6:00 PM - 7:00 PM | SIAM Business Meeting |
Constellation A
|
|
Tuesday January 14, 2003 | |||
7:30 AM - 4:00 PM | Registration |
Pre-Function Area
|
|
8:30 AM - 9:20 AM | Continental Breakfast |
Constellation A
|
|
9:00 AM - 11:05 AM |
CONCURRENT SESSIONS
|
||
Session 9A 9:00 AM - On the Rectilinear Crossing Number of Complete
Graphs 9:25 AM - Matching Planar Maps 9:50 AM - Dynamic Generators of Topologically Embedded
Graphs 10:15 AM - Computing Homotopic Shortest Paths in the
Plane 10:40 AM - Fully-Dynamic Two Dimensional Orthogonal
Range and Line Segment Intersection Reporting in Logarithmic Time |
Constellation C
|
||
Session 9B
9:00 AM - Edge Disjoint Paths Revisited 9:25 AM - A New Approximation Algorithm for the Asymmetric
TSP with Triangle Inequality 9:50 AM - Approximating Asymmetric Maximum TSP 10:15 AM - The k-Traveling Repairman Problem 10:40 AM - Directed Graphs Requiring
Large Numbers of Shortcuts |
Constellation D
|
||
Session 9C
9:00 AM - Implicit Dictionaries Supporting Searches
and Amortized Updates in O(\log n \log\log n) Time 9:25 AM - Compact Representations of Separable Graphs 9:50 AM - Labeling Schemes for Small Distances in
Trees 10:15 AM - On AC0 Implementations of Fusion Trees
and Atomic Heaps |
Constellation E
|
||
11:05 AM - 11:30 AM | Coffee Break |
Constellation A
|
|
11:30 AM - 12:30 PM |
Session 10 - IP#3 Who Cares About Permanents? |
Constellation B
|
|
12:30 PM - 2:00 PM | Lunch (Attendees on their own) | ||
2:00 PM - 3:40 PM |
CONCURRENT SESSIONS
|
||
Session 11A 2:00 PM - Between O(nm) and O(n^\alpha) 2:25 PM - Fast Distributed Algorithms for (Weakly)
Connected Dominating Sets and Linear-Size Skeletons 2:50 PM - A 5/4-Approximation Algorithm for Minimum
2-Edge-Connectivity 3:15 PM - Fault-Tolerant Facility Location |
Constellation C
|
||
Session 11B
2:00 PM - Efficient Sequences of Trials 2:25 PM - Pursuit-Evasion with Imprecise Target Location 2:50 PM - Unconditional Proof of Tightness of Johnson
Bound 3:15 PM - Deterministic Identity Testing for Multivariate
Polynomials |
Constellation D
|
||
Session 11C
2:00 PM - Competitive Queueing Policies for QoS Switches 2:25 PM - Dynamic Routing on Networks with Fixed-Size
Buffers 2:50 PM - Dynamic Construction of Bluetooth Scatternets
of Fixed Degree and Low Diameter 3:15 PM - Scheduling Techniques for Media-on-Demand |
Constellation E
|
||
3:40 PM - 4:05 PM | Coffee Break |
Constellation A
|
|
4:05 PM - 5:45 PM |
CONCURRENT SESSIONS
|
||
Session 12A
4:05 PM - Smaller Core-Sets for Balls 4:30 PM - Zonotopes as Bounding Volumes 4:55 PM - Sublinear Approximation of Euclidean Minimum
Spanning Tree 5:20 PM - An Approximation Algorithm for Cutting Out
Convex Polygons |
Constellation C
|
||
Session 12B
4:05 PM - Inferring Tree Topologies Using Flow Tests 4:30 PM - Wavelength Assignment and Generalized Interval
Graph Coloring 4:55 PM - An Improved Approximation Algorithm for
the Partial Latin Square Extension Problem 5:20 PM - Multirate Rearrangeable Clos Networks and
a Generalized Bipartite Graph Edge Coloring Problem |
Constellation D
|
||
Session 12C
4:05 PM - High-Order Entropy-Compressed Text Indexes 4:30 PM - Multidimensional Matching and Fast Search
in Suffix Trees 4:55 PM - Inplace 2D Matching in Compressed Images 5:20 PM - The Similarity Metric |
Constellation E
|