This collection comprises the expanded and fully refereed versions of selected papers presented at the 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016) and the 20th International Workshop on Randomization and Computation (RANDOM 2016) held at the Institut Henri Poincaré (IHP) - Paris, France, September 7 -- September 9, 2016. 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 20 out of 40 submissions for presentation at the Workshop; of these, three were invited to this Special Issue. The RANDOM Program Committee selected 27 out of 45 submissions; of these, two were invited to this Special Issue. The authors of four of the invited papers accepted the invitation.

The papers from APPROX 2016 included in this Special Issue cover topics concerning Unique Games hardness, online sampling, oblivious rounding and the integrality gap. The paper from RANDOM 2016 covers topics concerning discrepancy and convex geometry.

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 2016 Program Committee

Anna Adamaszek (U. Copenhagen, Denmark)
Shiri Chechik (Tel Aviv U., Israel)
Anne Driemel (Eindhoven U. Technology, The Netherlands)
Lee-Ad Gottlieb (Ariel U., Israel)
Varun Kanade (Oxford U., U.K.)
Nitish Korula (Google, New York, USA)
Stefano Leonardi (La Sapienza, Roma, Italy)
Daniel Lokshtanov (U. Bergen, Norway)
Claire Mathieu (ENS Paris, France)    (Chair)
Nicole Megow (Technische U. München, Germany)
Tobias Moemke (U. Saarland, Saarbrücken, Germany)
Shayan Oveis Gharan (U. Washington, Seattle, WA, USA)
Debmalya Panigrahi (Duke U., Durham, NC, USA)
Richard Peng (Georgia Tech, Atlanta, GA, USA)
Ely Porat (Bar-Ilan U., Ramat Gan, Israel)
Adi Rosén (CNRS & Paris 7, France)
Adrian Vetta (McGill U., Montreal, QC, Canada)
Rico Zenklusen (ETH Zürich, Switzerland)

RANDOM 2016 Program Committee

Mahdi Cheraghchi (Imperial College, London, U.K.)
Elena Grigorescu (Purdue U., W. Lafayette, IN, USA)
Neeraj Kayal (MSR Bangalore, India)
Adam Klivans (U. Texas, Austin, TX, USA)
Swastik Kopparty (Rutgers U., New Brunswick, NJ, USA)
Ravi Kumar (Google, Mountain View, CA, USA)
Dana Moshkovitz (MIT, Cambridge, MA, USA)
Ashwin Nayak (U. Waterloo, ON, Canada)
Ryan O'Donnell (Carnegie Mellon U., Pittsburgh, PA, USA)
Asaf Shapira (Tel Aviv U., Israel)
Ronen Shaltiel (U. Haifa, Israel)
Alexander Sherstov (UCLA, Los Angeles, CA, USA)
Thomas Thierauf (Hochschule Aalen, Germany)
Chris Umans (Caltech, Pasadena, CA, USA)    (Chair)
Eric Vigoda (Georgia Tech, Atlanta, GA, USA)