The Organization Committee (OC) and the Chairs of ALGO 2020 decided to run the conferences online in a virtual way. What is most important is that the scientific activity of the Programme Committees of the ALGO conferences is not suspended or stopped: peer review, accepted papers, camera ready and proceedings will be accomplished as usual. Instructions for authors on how to give their talks online in the virtual room will be provided.


Approximation and online algorithms are fundamental tools to deal with computationally hard problems and problems in which the input is gradually disclosed over time. Both kinds of problems arise from a large number of applications in a variety of fields. The workshop focuses on the design and analysis of approximation and online algorithms. It also covers experimental methods used to design and analyze efficient approximation and online algorithms. It is colocated with ALGO 2020, which also hosts ESA, ALGOCLOUD, ALGOSENSORS, ATMOS, and WABI. ALGO 2020 will take place 7-10 September 2020 in Pisa, Italy.

Important Dates

  • Paper submission deadline: June 27, 2020, 23:59 (AOE)
  • Notification: July 26, 2020 (AOE)
  • Camera ready: October 10, 2020 (AOE)
  • Conference: September 9-10, 2020, in Pisa, Italy

Call For Papers

Authors are invited to submit an extended abstract or full paper of at most 12 pages, including the first page but not including the references, describing original unpublished research. Simultaneous submission to other conferences with published proceedings is not permitted. The first page of the submission should include the authors' full names, addresses, e-mail addresses, and an abstract summarizing the results in roughly 100-200 words. The remainder of the submission should contain a description of the main results, an explanation of their importance, and a clear comparison with related work. The submission must include full proofs of the results. Material that cannot be included in the 12 allowed pages can be placed in an appendix, that will be read at the sole discretion of the program committee.

Submissions should be formatted for letter-size paper with reasonable margins, page numbers, and at least 11-point font. Submitted papers are not required to be in LNCS style. Papers should be submitted electronically via the EasyChair submission system at:


By submitting a paper the authors acknowledge that in case of acceptance at least one of the authors must register at ALGO 2020 and present the paper. The program committee may award a Best Paper Award to one of the accepted papers.


Papers are solicited in all research areas related to approximation and online algorithms, including, but not limited to:

  • graph algorithms
  • inapproximability results
  • network design
  • packing and covering
  • paradigms for the design and analysis of approximation and online algorithms
  • parameterized complexity
  • scheduling problems
  • algorithmic game theory
  • algorithmic trading
  • coloring and partitioning
  • competitive analysis
  • computational advertising
  • computational finance
  • cuts and connectivity
  • geometric problems
  • mechanism design
  • resource augmentation
  • real-world applications


  • Antonios Antoniadis, University of Cologne, Germany
  • Christoph Dürr, Sorbonne university, Paris, France
  • Lene Monrad Favrholdt, University of Southern Denmark, Odense, Denmark
  • Archontia Giannopoulou, National and Kapodistrian University of Athens, Greece
  • Christos Kaklamanis, University of Patras and CTI "Diophantus", Greece (co-chair)
  • Panagiotis Kanellopoulos, University of Essex, UK
  • Tamás Király, Eötvös Loránd University, Budapest, Hungary
  • Danny Krizanc, Wesleyan University, Middletown, Connecticut, USA
  • Asaf Levin, The Technion, Haifa, Israel (co-chair)
  • Bodo Manthey, University of Twente, The Netherlands
  • George Mertzios, Durham University, UK
  • Zeev Nutov, The Open University of Israel, Israel
  • Kirk Pruhs, University of Pittsburgh, USA
  • Lars Rohwedder, EPFL, Switzerland
  • Laura Sanità, University of Waterloo, Canada, and Eindhoven University of Technology, The Netherlands
  • Piotr Sankowski, University of Warsaw, Poland
  • Kevin Schewior, University of Cologne, Germany
  • Baruch Schieber, New Jersey Institute of Technology, USA
  • Melanie Schmidt, University of Cologne, Germany
  • José Verschae, Pontificia Universidad Católica, Chile
  • Pavel Veselý, University of Warwick, UK

Accepted papers

LP-based algorithms for multistage minimization problems.		
Evripidis Bampis, Bruno Escoffier and Alexander Kononov. 

A Faster FPTAS for Knapsack Problem With Cardinality Constraint.
Wenxin Li, Joohyun Lee and Ness Shroff. 

Distributed Algorithms for Matching in Hypergraphs.
Oussama Hanguir and Clifford Stein. 

Online Coloring and a New Type of Adversary for Online Graph Problems.
Yaqiao Li, Vishnu Narayan and Denis Pankratov. 

Maximum Coverage with Cluster Constraints: An LP-Based Approximation Technique.
Guido Schaefer and Bernard Zweers. 

A Constant-Factor Approximation Algorithm for Vertex Guarding a WV-Polygon.
Stav Ashur, Omrit Filtser and Matthew Katz. 

Lasserre Integrality Gaps for Graph Spanners and Related Problems.
Michael Dinitz, Yasamin Nazari and Zeyu Zhang. 

To Close Is Easier Than To Open: Dual Parameterization To k-Median.
Jaroslaw Byrka, Szymon Dudycz, Pasin Manurangsi, Jan Marcinkowski and Michal Wlodarczyk. 

Explorable Uncertainty in Scheduling with Non-Uniform Testing Times.
Susanne Albers and Alexander Eckl. 

Memoryless Algorithms for the Generalized k-server Problem on Uniform Metrics.
Dimitris Christou, Dimitris Fotakis and Grigorios Koumoutsos. 

Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems.
Marek Cygan, Magnús M. Halldórsson and Guy Kortsarz. 

Concave connection cost Facility Location and the Star Inventory Routing Problem.
Mateusz Lewandowski and Jaroslaw Byrka. 

An Improved Approximation Algorithm for the Uniform Cost-Distance Steiner Tree Problem.
Ardalan Khazraei and Stephan Held. 

A Constant-Factor Approximation Algorithm for Red-Blue Set Cover with Unit Disks.
Raghunath Reddy Madireddy and Apurva Mudgal. 

2-node-connectivity network design.
Zeev Nutov. 

Invited Speaker

Clifford Stein

University of California, Davis

Cliff's research interests include the design and analysis of algorithms, combinatorial optimization, operations research, network algorithms, scheduling, algorithm engineering and computational biology. He has published many influential papers and has occupied a variety of editorial positions. His work has been supported by the National Science Foundation and Sloan Foundation. He is the winner of several prestigious awards including an NSF Career Award, an Alfred Sloan Research Fellowship and the Karen Wetterhahn Award for Distinguished Creative or Scholarly Achievement. He is also the co-author of two popular textbooks: Introduction to Algorithms, and Discrete Math for Computer Scientists.


Proceedings will be published in the Springer series Lecture Notes in Computer Science after the workshop takes place.
Selected papers presented at WAOA 2020 will be invited to a journal special issue.