default search action
3rd RANDOM / 2nd APPROX 1999: Berkeley, CA, USA
- Dorit S. Hochbaum, Klaus Jansen, José D. P. Rolim, Alistair Sinclair:
Randomization, Approximation, and Combinatorial Algorithms and Techniques, Third International Workshop on Randomization and Approximation Techniques in Computer Science, and Second International Workshop on Approximation Algorithms for Combinatorial Optimization Problems RANDOM-APPROX'99, Berkeley, CA, USA, August 8-11, 1999, Proceedings. Lecture Notes in Computer Science 1671, Springer 1999, ISBN 3-540-66329-0
Session Random 1
- Andrei Z. Broder, Michael Mitzenmacher:
Completeness and Robustness Properties of Min-Wise Independent Permutations. 1-10 - Michael E. Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman:
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families. 11-15
Session Approx 1
- Noga Alon, Uri Arad, Yossi Azar:
Independent Sets in Hypergraphs with Applications to Routing via Fixed Paths. 16-27 - Joachim Gudmundsson
, Christos Levcopoulos, Giri Narasimhan
Approximating Minimum Manhattan Networks. 28-38 - Benjamin Doerr, Anand Srivastav:
Approximation of Multi-color Discrepancy. 39-50 - Hans Kellerer:
A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem. 51-62
Session Approx 2
- Milena Mihail:
Set Cover with Requirements and Costs Evolving over Time. 63-72 - Magnús M. Halldórsson
Multicoloring Planar Graphs and Partial k-Trees. 73-84
Session: Random 2
- Michal Parnas, Dana Ron
Testing the Diameter of Graphs. 85-96 - Yevgeniy Dodis, Oded Goldreich
Improved Testing Algorithms for Monotonicity. 97-108 - Yonatan Aumann, Johan Håstad, Michael O. Rabin, Madhu Sudan:
Linear Consistency Testing. 109-120 - Ben Morris:
Improved Bounds for Sampling Contingency Tables. 121-129
Invited Talk
- Avi Wigderson:
Probabilistic and Deterministic Approximations of the Permanent (abstract). 130
Session Random 3
- Oded Goldreich
Improved Derandomization of BPP Using a Hitting Set Generator. 131-137 - Andreas Baltz, Tomasz Schoen
Probabilistic Construction of Small Strongly Sum-Free Sets via Large Sidon Sets. 138-143
Session Approx 3
- Rolf H. Möhring, Andreas S. Schulz, Marc Uetz:
Stochastic Machine Scheduling: Performance Guarantees for LP-based Priority Policies. 144-155 - Dimitris Fotakis, Paul G. Spirakis:
Efficient Redundant Assignments under Fault-Tolerance Constraints. 156-167 - Csanád Imreh, John Noga:
Scheduling with Machine Cost. 168-176 - Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko:
A Linear Time Approximation Scheme for the Job Shop Scheduling Problem. 177-188
Invited Talk
- Uriel Feige:
Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example. 189-196
Session Approx 4
- Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri:
Hardness Results for the Power Range Assignmet Problem in Packet Radio Networks. 197-208 - Christine T. Cheng:
A New Approximation Algorithm for the Demand Rouring and Slotting Problem with Unit Demands on Rings. 209-220
Session Random 4
- Anne Condon, Richard M. Karp:
Algorithms for Graph Partitioning on the Planted Partition Model. 221-232 - Seth Pettie, Vijaya Ramachandran:
A Randomized Time-Work Optimal Parallel Algorithm for Finding a Minimum Spanning Forest. 233-244 - Tugkan Batu
Fast Approximate PCPs for Multidimensional Bin-Packing Problems. 245-256 - Russell A. Martin, Dana Randall:
Pfaffian Algorithms for Sampling Routings on Regions with Free Boundary Conditions. 257-268
Minisymposium on Scheduling Talks
- Susanne Albers, Günter Schmidt
Scheduling with Unexpected Machine Breakdowns. 269-280 - Foto N. Afrati, Evripidis Bampis
Scheduling on a Constant Number of Machines. 281-287
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-21 20:37 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: