SODA 2017

102 papers
The 2017 edition of the Symposium on Discrete Algorithms (SODA) presented 130 papers, with a strong emphasis on approximation algorithms and scheduling theory. Research focused on closing approximation gaps for unrelated machine scheduling and developing online scheduling techniques. Notable contributions explored polynomial-time approximations for complex scheduling problems and the use of fractional relaxation and rounding methods. Prolific contributors during this year included Haim Kaplan, Ola Svensson, and David P. Woodruff. Distributed computing and optimization were also prominent themes. Work in these areas included hierarchical aggregation for scalable communication, self-stabilizing systems, and zeroth-order optimization for high-dimensional models. Graph-related research addressed topics such as counting proper colorings on cubic graphs, maximum weight matching in semi-streaming models, and LP-based robust algorithms for minor-free graphs. Other significant areas of study included online fair division of indivisible items, sublinear algorithms utilizing conditional sampling, and the (h, k)-server problem on bounded depth trees.

Top Research Directions

Research directions most represented by SODA 2017 papers.

The Empirical Validation Gap 4
Tightening Theoretical Bounds by Optimizing Constant Factors 3
Closing the Optimality Gap in Online Algorithms 2
How Network Topology Governs Decentralized Learning Convergence 2
Extending Structural Graph Properties to Broader Graph Classes 2
Managing Hidden Constant Overhead in Algorithm Design 2
Designing Parameter-Free Clustering Algorithms 2
Incremental Maintenance of Dynamic Graph Indices 2
Bounded Adaptivity Gaps in Stochastic Optimization 1
Mitigating Aspect Ratio Sensitivity in Geometric Algorithms 1
State Complexity and Memory Thresholds in Population Protocols 1
Adversarial Input Sequences for Online Algorithm Lower Bounds 1
Approximate Separation Oracles for Exponential Linear Programs 1
Distilling Uniform Bits from Weak Entropy Sources 1
Stochastic Probing for Combinatorial Optimization 1

Top Authors

AuthorPapers
Aviad Rubinstein3
Chandra Chekuri3
Haim Kaplan3
Niv Buchbinder3
Shi Li3
Alexandr Andoni2
Anupam Gupta2
Atri Rudra2
Benjamin Moseley2
David Woodruff2
Emanuele Natale2
Ilias Diakonikolas2
Ludwig Schmidt2
Michael Dinitz2
Monika Henzinger2
Ola Svensson2
Piotr Indyk2
Piotr Sankowski2
Rasmus Pagh2
Sahil Singla2

Impactful Papers

Papers from SODA 2017 that shaped research clusters.

Foundational

Influential

Papers

Title
Totally Unimodular Congestion Games
Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios

« prev Page 3/3