This collection comprises the expanded and fully refereed versions of selected papers presented at the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015) and the 19th International Workshop on Randomization and Computation (RANDOM 2015) held at Princeton University, New Jersey, U.S.A., August 24 - August 26 2015. The selection was made by the program committees of the respective meetings (listed below). Preliminary versions of the papers were presented at the workshops and the extended abstracts appeared in the proceedings of the meetings published by Dagstuhl Publishing.

The APPROX Program Committee selected 26 out of 61 submissions for presentation at the Workshop; of these, 3 were invited to this Special Issue. The RANDOM Program Committee selected 30 out of 83 submissions; of these, 2 were invited to this Special Issue. The authors of all the five selected papers accepted the invitation.

The papers selected from APPROX 2015 cover topics concerning the approximability of constraint satisfaction and scheduling problems, while the papers selected from RANDOM 2015 cover topics in streaming algorithms and random graphs.

All papers were refereed in accordance with the usual rigorous standards of Theory of Computing.

We would like to thank the authors for their contributions and the anonymous referees for their hard work that helped improve the quality of this issue. It was a pleasure to edit this special issue for Theory of Computing.

APPROX 2015 Program Committee

Parinya Chalermsook (MPII Saarbrücken, Germany)
Michael Dinitz (Johns Hopkins University, USA)
Naveen Garg (IIT Delhi, India) (Chair)
Fabrizio Grandoni (IDSIA & University of Lugano, Switzerland)
Sungjin Im (UC Merced, USA)
Amit Kumar (IIT Delhi, India)
Lap Chi Lau (Chinese University of Hong Kong)
Nicole Megow (TU Munich, Germany)
Harald Räcke (TU Munich, Germany)
Rishi Saket (IBM IRL, India)
Piotr Sankowski (University of Warsaw, Poland)
Roy Schwartz (Princeton University, USA)
René Sitters (VU Amsterdam, The Netherlands)
David Steurer (Cornell University, USA)
Chaitanya Swamy (University of Waterloo, Canada)
Andreas Wiese (MPII Saarbrücken, Germany)

RANDOM 2015 Program Committee

Dimitris Achlioptas (University of California, Santa Cruz, USA)
Alex Andoni (Columbia University, USA)
Ken Clarkson (IBM Research -- Almaden, USA)
Anindya De (Northwestern University, USA)
Hu Fu (Caltech, USA)
Nick Harvey (University of British Columbia, Canada)
Xin Li (Carnegie Mellon University, USA)
Aleksander Madry (Massachusetts Institute of Technology, USA)
Raghu Meka (University of California, Los Angeles, USA)
Eric Price (University of Texas, Austin, USA)
Anup Rao (University of Washington, USA) (Chair)
Aaron Roth (University of Pennsylvania, USA)
Mohit Singh (Microsoft Research, Redmond, USA)
Ali Sinop (Simons Institute for the Theory of Computing, USA)
Madhur Tulsiani (Toyota Technological Institute at Chicago, USA)
David Woodruff (IBM Research -- Almaden, USA)
Mary Wootters (Stanford University, USA)