Randomization, approximation, and combinatorial optimization. Algorithms and techniques. 3rd international workshop on Randomization and approximation techniques in computer science, and 2nd international workshop on Approximation algorithms for combinatorial optimization problems RANDOM-APPROX '99. Berkeley, CA, USA, August 8--11, 1999. Proceedings (Q1301514)

The articles of mathematical interest will be reviewed individually. The preceding workshop (2, 1998) has been indicated (see Zbl 0898.00029) and the 1st workshop (1998) has been indicated (see Zbl 0892.00051). Indexed articles: \textit{Broder, Andrei Z.; Mitzenmacher, Michael}, Completeness and robustness properties of min-wise independent permutations, 1-10 [Zbl 0949.60017] \textit{Saks, Michael; Srinivasan, Aravind; Zhou, Shiyu; Zuckerman, David}, Low discrepancy sets yield approximate min-wise independent permutation families, 11-15 [Zbl 0949.60015] \textit{Alon, Noga; Arad, Uri; Azar, Yossi}, Independent sets in hypergraphs with applications to routing via fixed paths, 16-27 [Zbl 0949.68172] \textit{Doerr, Benjamin; Srivastav, Anand}, Approximation of multi-color discrepancy, 39-50 [Zbl 0945.05028] \textit{Kellerer, Hans}, A polynomial time approximation scheme for the multiple knapsack problem, 51-62 [Zbl 0945.90050] \textit{Halldórsson, Magnús M.; Kortsarz, Guy}, Multicoloring planar graphs and partial \(k\)-trees, 73-84 [Zbl 0945.05027] \textit{Parnas, Michal; Ron, Dana}, Testing the diameter of graphs, 85-96 [Zbl 0945.05057] \textit{Dodis, Yevgeniy; Goldreich, Oded; Lehman, Eric; Raskhodnikova, Sofya; Ron, Dana; Samorodnitsky, Alex}, Improved testing algorithms for monotonicity, 97-108 [Zbl 0949.68178] \textit{Aumann, Yonatan; Håstad, Johan; Rabin, Michael O.; Sudan, Madhu}, Linear consistency testing, 109-120 [Zbl 0951.68193] \textit{Morris, Ben}, Improved bounds for sampling contingency tables, 121-129 [Zbl 1063.62548] \textit{Baltz, Andreas; Schoen, Tomasz; Srivastav, Anand}, Probabilistic construction of small strongly sum-free sets via large Sidon sets, 138-143 [Zbl 0992.11024] \textit{Möhring, Rolf H.; Schulz, Andreas S.; Uetz, Marc}, Stochastic machine scheduling: Performance guarantees for LP-based priority policies. (Extended abstract), 144-155 [Zbl 0949.68010] \textit{Imreh, Csanád; Noga, John}, Scheduling with machine cost, 168-176 [Zbl 0949.68011] \textit{Jansen, Klaus; Solis-Oba, Roberto; Sviridenko, Maxim}, A linear time approximation scheme for the job shop scheduling problem, 177-188 [Zbl 0949.68012] \textit{Condon, Anne; Karp, Richard M.}, Algorithms for graph partitioning on the planted partition model, 221-232 [Zbl 0946.05081] \textit{Martin, Russell A.; Randall, Dana}, Pfaffian algorithms for sampling routings on regions with free boundary conditions, 257-268 [Zbl 0949.68117] \textit{Albers, Susanne; Schmidt, Günter}, Scheduling with unexpected machine breakdowns, 269-280 [Zbl 0949.68013]