{"id":33,"date":"2022-11-23T09:08:00","date_gmt":"2022-11-23T08:08:00","guid":{"rendered":"https:\/\/algo-conference.org\/2023\/?page_id=33"},"modified":"2025-10-16T12:33:04","modified_gmt":"2025-10-16T12:33:04","slug":"waoa","status":"publish","type":"page","link":"https:\/\/algo-conference.org\/2025\/waoa\/","title":{"rendered":"WAOA"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\" id=\"scope\">Scope<\/h3>\n\n\n\n<p>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 types of problems arise from a myriad of applications in various fields. The Workshop on Approximation and Online Algorithms (WAOA) focuses on the design and analysis of approximation and online algorithms. It is co-located with&nbsp;<a href=\"http:\/\/algo-conference.org\/2025\">ALGO 2025<\/a>, which also hosts <a href=\"https:\/\/algo-conference.org\/2025\/esa\/\" data-type=\"page\" data-id=\"60\">ESA<\/a>, <a href=\"https:\/\/algo-conference.org\/2025\/algocloud\/\" data-type=\"page\" data-id=\"10\">ALGOCLOUD<\/a>, <a href=\"https:\/\/algo-conference.org\/2025\/algowin\" data-type=\"page\" data-id=\"47\">ALGOWIN<\/a>, <a href=\"https:\/\/algo-conference.org\/2025\/atmos\/\" data-type=\"page\" data-id=\"49\">ATMOS<\/a> and <a href=\"https:\/\/algo-conference.org\/2025\/ipec\/\" data-type=\"page\" data-id=\"51\">IPEC<\/a>.&nbsp;<a href=\"http:\/\/algo-conference.org\/2025\">ALGO 2025<\/a>&nbsp;will take place in the beautiful city of Warsaw in Poland.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Important dates<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Paper submission deadline: <strong>July 6<\/strong>, <strong>2025, 23:59 AoE<\/strong><br>(<a href=\"https:\/\/easychair.org\/conferences\/?conf=waoa2025\" data-type=\"link\" data-id=\"https:\/\/easychair.org\/conferences\/?conf=waoa2025\">EasyChair submission page<\/a>)<\/li>\n\n\n\n<li>Notification: August 7, 2025<\/li>\n\n\n\n<li>Camera-ready version: <s>August 12, 2025<\/s> August 14, 2025<\/li>\n\n\n\n<li>Conference dates: September 18-19, 2025<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Invited speaker<\/h3>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" width=\"948\" height=\"1024\" src=\"https:\/\/algo-conference.org\/2025\/wp-content\/uploads\/2025\/08\/myselfPrinceton-1-948x1024.jpg\" alt=\"\" class=\"wp-image-2209\" style=\"width:207px;height:auto\" srcset=\"https:\/\/algo-conference.org\/2025\/wp-content\/uploads\/2025\/08\/myselfPrinceton-1-948x1024.jpg 948w, https:\/\/algo-conference.org\/2025\/wp-content\/uploads\/2025\/08\/myselfPrinceton-1-278x300.jpg 278w, https:\/\/algo-conference.org\/2025\/wp-content\/uploads\/2025\/08\/myselfPrinceton-1-768x829.jpg 768w, https:\/\/algo-conference.org\/2025\/wp-content\/uploads\/2025\/08\/myselfPrinceton-1.jpg 1065w\" sizes=\"auto, (max-width: 948px) 100vw, 948px\" \/><\/figure>\n\n\n\n<p><strong>Speaker:<\/strong> <a href=\"https:\/\/faculty.cc.gatech.edu\/~ssingla7\/\" data-type=\"link\" data-id=\"https:\/\/faculty.cc.gatech.edu\/~ssingla7\/\">Sahil Singla<\/a>, Georgia Tech<\/p>\n\n\n\n<p><strong>Title<\/strong>: &nbsp;Beyond Competitive Analysis for Online Algorithms<\/p>\n\n\n\n<p><strong>Abstract:<\/strong><\/p>\n\n\n\n<p>Competitive analysis has long been the standard framework for evaluating online algorithms under worst-case inputs. While powerful, it often yields weak or even vacuous bounds for central problems\u2014such as online matchings, load balancing, and network design. Yet many of these problems become far more tractable once we move beyond the purely worst-case lens. This has motivated a range of beyond worst-case models that exploit additional structure or information to achieve stronger guarantees.<\/p>\n\n\n\n<p>In this talk, I will survey several such models and their algorithmic implications: stochastic arrival processes and prophet-type inequalities; algorithms with sample access to the input; recourse models that allow limited revisions to past decisions; and optimal policy design as a benchmark beyond the offline optimum. I will emphasize unifying ideas across these approaches and highlight recent advances that overcome long-standing worst-case barriers.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Accepted papers<\/h3>\n\n\n\n<p>Proceedings: <a href=\"https:\/\/link.springer.com\/book\/10.1007\/978-3-032-06706-7\">Approximation and Online Algorithms (LNCS 16077)<\/a><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><span style=\"text-decoration: underline;\">Bob Krekelberg<\/span> and Alison Hsiang-Hsuan Liu. <em>On the FirstFit Algorithm for Online Unit-Interval Coloring<\/em><\/li>\n\n\n\n<li>Yann Disser, Max Klimm, <span style=\"text-decoration: underline;\">Annette Lutz<\/span> and Lea Strubberg. <em>Incremental\u2013Decremental Maximization<\/em><\/li>\n\n\n\n<li><span style=\"text-decoration: underline;\">Hiroshi Fujiwara<\/span>, Rina Atsumi and Hiroaki Yamamoto. <em>Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem<\/em><\/li>\n\n\n\n<li>Fritz B\u00f6kler, Markus Chimani and <span style=\"text-decoration: underline;\">Henning Jasper<\/span>. <em>Simple Approximations for General Spanner Problems<\/em><\/li>\n\n\n\n<li><span style=\"text-decoration: underline;\">David Fischer<\/span>, Hauke Brinkop and Klaus Jansen. <em>Robust Scheduling on Uniform Machines<\/em><\/li>\n\n\n\n<li><span style=\"text-decoration: underline;\">Martijn van Ee<\/span> and Rene Sitters. <em>Approximation algorithms for graph search with imperfect detection<\/em><\/li>\n\n\n\n<li>D Ellis Hershkowitz and <span style=\"text-decoration: underline;\">Niklas Dahlmeier<\/span>. <em>Low Recourse Arborescence Forests Under Uniformly Random Arcs<\/em><\/li>\n\n\n\n<li><span style=\"text-decoration: underline;\">Shamisa Nematollahi<\/span> and Daniel Vaz. <em>Buy-at-Bulk Facility Location on Trees<\/em><\/li>\n\n\n\n<li>Andreas Abels, <span style=\"text-decoration: underline;\">Mariia Anapolska<\/span> and Christina B\u00fcsing. <em>Interval-Constrained Bipartite Matching over Time<\/em><\/li>\n\n\n\n<li><span style=\"text-decoration: underline;\">Qiming Cui<\/span> and Michael Dinitz. <em>Controlling Tail Risk in Two-Slope Ski Rental<\/em><\/li>\n\n\n\n<li><span style=\"text-decoration: underline;\">Yan Couto<\/span> and Cristina Fernandes. <em>Hardness of Dynamic Core and Truss Decompositions<\/em><\/li>\n\n\n\n<li>Kanstantsin Pashkovich and <span style=\"text-decoration: underline;\">Thomas Snow<\/span>. <em>Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three<\/em><\/li>\n\n\n\n<li><span style=\"text-decoration: underline;\">Jubayer Nirjhor<\/span> and Nicole Wein. <em>Improved Online Sorting<\/em><\/li>\n\n\n\n<li><span style=\"text-decoration: underline;\">Elisabet Burjons<\/span> and Matthias Gehnen. <em>Online General Knapsack with Reservation Costs<\/em><\/li>\n\n\n\n<li>Riju Bindua, Minati De, Naveen Garg and <span style=\"text-decoration: underline;\">Kanav Singla<\/span>. <em>The Online Piercing Set Problem With Recourse<\/em><\/li>\n<\/ul>\n\n\n\n<p>(presenting authors at WAOA 2025 <span style=\"text-decoration: underline;\">underlined<\/span>)<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Program committee&nbsp;<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Umang Bhaskar, Tata Institute of Fundamental Research<\/li>\n\n\n\n<li>Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign<\/li>\n\n\n\n<li>Yann Disser, TU Darmstadt<\/li>\n\n\n\n<li>Franziska Eberle, TU Berlin<\/li>\n\n\n\n<li>Yuri Faenza, Columbia University<\/li>\n\n\n\n<li>Cristina Fernandes, Universidade de S\u00e3o Paulo<\/li>\n\n\n\n<li>Thekla Hamm, TU Eindhoven<\/li>\n\n\n\n<li>Lisa Hellerstein, New York University<\/li>\n\n\n\n<li>Sungjin Im, University of California, Santa Cruz<\/li>\n\n\n\n<li>Naonori Kakimura, Keio University<\/li>\n\n\n\n<li>Kim-Manuel Klein, Universit\u00e4t zu L\u00fcbeck<\/li>\n\n\n\n<li>Jannik Matuschke, KU Leuven (co-chair)<\/li>\n\n\n\n<li>Arturo Merino, Universidad de O&#8217;Higgins<\/li>\n\n\n\n<li>Malin Rau, Chalmers University of Technology<\/li>\n\n\n\n<li>Rebecca Reiffenh\u00e4user, Universiteit van Amsterdam<\/li>\n\n\n\n<li>Melanie Schmidt, Heinrich-Heine-Universit\u00e4t D\u00fcsseldorf<\/li>\n\n\n\n<li>Seeun William Umboh, The University of Melbourne<\/li>\n\n\n\n<li>Jos\u00e9 Verschae, Pontificia Universidad Cat\u00f3lica de Chile (co-chair)<\/li>\n\n\n\n<li>Yu Yokoi, Institute of Science Tokyo<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Call for papers<\/h3>\n\n\n\n<p>Papers are solicited in all research areas related to approximation and online algorithms, including, but not limited to:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Algorithmic game theory<\/li>\n\n\n\n<li>Coloring and partitioning<\/li>\n\n\n\n<li>Computational economics and mechanism design<\/li>\n\n\n\n<li>Experimental methods for approximation and online algorithms<\/li>\n\n\n\n<li>FPT-approximation algorithms<\/li>\n\n\n\n<li>Geometric problems<\/li>\n\n\n\n<li>Graph algorithms and network design<\/li>\n\n\n\n<li>Inapproximability results<\/li>\n\n\n\n<li>Packing and covering<\/li>\n\n\n\n<li>Matroids and submodular functions<\/li>\n\n\n\n<li>New paradigms in approximation and online optimization<\/li>\n\n\n\n<li>Online selection problems<\/li>\n\n\n\n<li>Resource augmentation<\/li>\n\n\n\n<li>Relaxations and tightness of formulations<\/li>\n\n\n\n<li>Robust and stochastic problems<\/li>\n\n\n\n<li>Scheduling problems<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">Submission guidelines<\/h4>\n\n\n\n<p>Authors are invited to submit an extended abstract or full paper of at most 10 pages, excluding the title page, references, and an optional appendix. The submission should be typeset using a 10-point or larger font in a single-column format and 2cm margins all around on A4-size paper. The appendix must contain all omitted proofs or, alternatively, a full version of the paper. The appendix will be read by the program committee at their discretion but is not going to be published in the proceedings. The central part of the submission should, therefore, contain a clear technical presentation of the merits of the paper, including a discussion of the paper\u2019s importance within the context of prior work and a description of the key technical and conceptual ideas used to achieve its main claims.<\/p>\n\n\n\n<p>Results previously published (or scheduled for publication) in another conference proceedings or journal will not be accepted. Simultaneous submission to journals or other conferences with published proceedings is not permitted. By submitting a paper, the authors acknowledge that in case of acceptance, at least one of the authors must register at ALGO 2025, attend the conference onsite and present the paper. The program committee may award a Best Paper Award to one of the accepted papers.<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Double-blind reviewing&nbsp;<\/h4>\n\n\n\n<p>The conference will employ a lightweight double-blind reviewing process. Submissions <strong>should not reveal the identity of the authors<\/strong> in any way. In particular, authors\u2019 names, affiliations, and email addresses should not appear at the beginning or in the body of the submission. Authors should ensure that any references to their own related work is in the third person (e.g., \u201cWe build on the work of \u2026\u201d instead of \u201cWe build on our previous work \u2026\u201d). The purpose of the double-blind reviewing is to help PC members and external reviewers come to an initial judgment about the paper without bias, not to make it impossible for them to discover the authors if they were to try. Nothing should be done in the name of anonymity that weakens the submission or hinders the reviewing process. In particular, important references should not be omitted or anonymized. Authors should feel free to disseminate their ideas (e.g., via talks) or draft versions of their paper (e.g., on arXiv or other repositories).<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">COI with PC members&nbsp;<\/h4>\n\n\n\n<p>At submission, authors will be asked to indicate a Conflict of Interest (COI) with members of the program committee. A COI is limited to the following categories:&nbsp;<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>A family member or close friend.&nbsp;<\/li>\n\n\n\n<li>Ph.D. advisor or advisee (no time limit), or postdoc or undergraduate mentor or mentee within the past 5 years.&nbsp;<\/li>\n\n\n\n<li>A person with the same affiliation.&nbsp;<\/li>\n\n\n\n<li>A person involved in an alleged incident of harassment. (It is not required that the incident is reported.)&nbsp;<\/li>\n\n\n\n<li>A PC member who owes the author a favor (e.g., who recently requested a reference letter).<\/li>\n\n\n\n<li>A frequent or recent collaborator (within the last 5 years) who you believe cannot objectively review your work.<\/li>\n<\/ul>\n\n\n\n<h4 class=\"wp-block-heading\">PC submissions&nbsp;<\/h4>\n\n\n\n<p>Submissions authored or co-authored by members of the program committee are allowed but will be subject to a stricter review process.&nbsp;<\/p>\n\n\n\n<h4 class=\"wp-block-heading\">Paper submission and proceedings&nbsp;<\/h4>\n\n\n\n<p>Papers should be submitted electronically via the EasyChair submission system. The WAOA 2025 proceedings will be published by Springer in the Lecture Notes in Computer Science (LNCS) series. A subset of the accepted articles might be invited for a special issue of Acta Informatica.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Steering committee&nbsp;<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Roberto Solis-Oba, University of Western Ontario, CA&nbsp;<\/li>\n\n\n\n<li>Evripidis Bampis, Sorbonne Universit\u00e9, FR&nbsp;<\/li>\n\n\n\n<li>Thomas Erlebach, Durham University, UK&nbsp;<\/li>\n\n\n\n<li>Christos Kaklamanis, University of Patras, GR&nbsp;<\/li>\n\n\n\n<li>Nicole Megow, Universit\u00e4t Bremen, DE&nbsp;<\/li>\n\n\n\n<li>Laura Sanit\u00e0, Bocconi University, IT<\/li>\n\n\n\n<li>Martin Skutella, Technische Universit\u00e4t Berlin, DE&nbsp;<\/li>\n<\/ul>\n\n\n\n<p><\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Scope 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 types of problems arise from a myriad of applications in various fields. The Workshop on Approximation and Online Algorithms (WAOA) focuses on the design and analysis of approximation and [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"wp-custom-template-page-1","meta":{"footnotes":""},"class_list":["post-33","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/algo-conference.org\/2025\/wp-json\/wp\/v2\/pages\/33","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/algo-conference.org\/2025\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/algo-conference.org\/2025\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/algo-conference.org\/2025\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/algo-conference.org\/2025\/wp-json\/wp\/v2\/comments?post=33"}],"version-history":[{"count":23,"href":"https:\/\/algo-conference.org\/2025\/wp-json\/wp\/v2\/pages\/33\/revisions"}],"predecessor-version":[{"id":2352,"href":"https:\/\/algo-conference.org\/2025\/wp-json\/wp\/v2\/pages\/33\/revisions\/2352"}],"wp:attachment":[{"href":"https:\/\/algo-conference.org\/2025\/wp-json\/wp\/v2\/media?parent=33"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}