LAUSR

This special issue of Theory of Computing Systems is devoted to selected papers from the 13th Workshop on Approximation and Online Algorithms (WAOA 2015), that took place in Patras, Greece, in September 2015. The guest editors selected 9 contributions presented at the conference, addressing fundamental topics related to approximation and online algorithms, which have been revised and expanded in this special issue. In their article Constant-Time Local Computation Algorithms, Yishay Mansour, Boaz Patt-Shamir, and Shai Vardi give Local Computation Algorithms for several combinatorial optimization problems, whose time complexity is independent of the input size. Sàndor P. Fekete, Kan Huang, Joseph S. B. Mitchell, Ojas Parekh, and Cynthia A. Phillips, in their contribution Geometric Hitting Set for Segments of Few Orientations, give new hardness and approximation results for several special cases of geometric hitting set problems, where the input consists of sets of line segments having a small number of distinct slopes. In their paper Scheduling Parallel Jobs Online with Convex and Concave Parallelizability, Roozbeh Ebrahimi, Samuel McCauley, and Benjamin Moseley, consider the problem of scheduling jobs with convex or concave speedup curves in an online setting, and develop a new competitive algorithm for it.