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.
Top Authors
Impactful Papers
Papers from SODA 2017 that shaped research clusters.
Foundational
LP-Based Robust Algorithms for Noisy Minor-Free and Bounded Treewidth Graphs
foundational
Tuning the Smoothing Parameter for Certi
Influential
The (h, k)-Server Problem on Bounded Depth Trees
influential
Adversarial Input Sequences for Online A
Computing Walrasian equilibria: fast algorithms and structural properties
influential
The Empirical Validation Gap
Proximity in the Age of Distraction: Robust Approximate Nearest Neighbor Search
influential
The Empirical Validation Gap
ETH Hardness for Densest-k-Subgraph with Perfect Completeness
influential
Proving Algorithmic Optimality via Compl
Polylogarithmic Bounds on the Competitiveness of Min-cost Perfect Matching with Delays
influential
Mitigating Aspect Ratio Sensitivity in G
Papers
| Title |
|---|
| Totally Unimodular Congestion Games |
| Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios |
« prev Page 3/3