The proceedings contain 192 papers. The topics discussed include: prior-independent auctions for heterogeneous bidders;impossibilities for obviously strategy-proof mechanisms;revenue maximization for buyers with costl...
The proceedings contain 192 papers. The topics discussed include: prior-independent auctions for heterogeneous bidders;impossibilities for obviously strategy-proof mechanisms;revenue maximization for buyers with costly participation;breaking the 3/4 barrier for approximate maximin share;combinatorial contracts beyond gross substitutes;on supermodular contracts and dense subgraphs;sorting pattern-avoiding permutations via 0–1 matrices forbidding product patterns;vertical decomposition in 3D and 4D with applications to line nearest-neighbor searching in 3D;dynamic dictionary with subconstant wasted bits per key;dynamic time warping;and dynamically maintaining the persistent homology of time series.
The proceedings contain 189 papers. The topics discussed include: dynamic algorithms for packing-covering LPs via multiplicative weight updates;maintaining expander decompositions via sparse cuts;fully dynamic exact e...
ISBN:
(纸本)9781611977554
The proceedings contain 189 papers. The topics discussed include: dynamic algorithms for packing-covering LPs via multiplicative weight updates;maintaining expander decompositions via sparse cuts;fully dynamic exact edge connectivity in sublinear time;faster deterministic worst-case fully dynamic all-pairs shortest paths via decremental hop-restricted shortest paths;dynamic matching with better-than-2 approximation in polylogarithmic update time;dynamic algorithms for maximum matching size;closing the gap between directed hopsets and shortcut sets;maximal k-edge-connected subgraphs in weighted graphs via local random contraction;faster and unified algorithms for diameter reducing shortcuts and minimum chain cover;near-linear time approximations for cut problems via fair cuts;fast discrepancy minimization with hereditary guarantees;a tight quasi-polynomial bound for global label min-cut;a tight quasi-polynomial bound for global label min-cut;a nearly-tight analysis of multipass pairing heaps;a tight analysis of slim heaps and smooth heaps;and short synchronizing words for random automata.
The proceedings contain 148 papers. The topics discussed include: compact redistricting plans have many spanning trees;online Nash social welfare maximization with predictions;robust load balancing with machine learne...
ISBN:
(纸本)9781611977073
The proceedings contain 148 papers. The topics discussed include: compact redistricting plans have many spanning trees;online Nash social welfare maximization with predictions;robust load balancing with machine learned advice;online graph algorithms with predictions;learning-augmented weighted paging;a faster algorithm for quickest transshipments via an extended discrete newton method;the popular assignment problem: when cardinality is more important than popularity;nested dissection meets IPMs: planar min-cost flow in nearly-linear time;improved strongly polynomial algorithms for deterministic MDPs, 2VPI feasibility, and discounted all-pairs shortest paths;Hopcroft’s problem, log-star shaving, 2D fractional cascading, and decision trees;untangling planar graphs and curves by staying positive;and computational topology in a collapsing universe: Laplacians, homology, cohomology.
The proceedings contain 180 papers. The topics discussed include: explicit two-deletion codes with redundancy matching the existential bound;efficient linear and affine codes for correcting insertions/deletions;beatin...
ISBN:
(纸本)9781611976465
The proceedings contain 180 papers. The topics discussed include: explicit two-deletion codes with redundancy matching the existential bound;efficient linear and affine codes for correcting insertions/deletions;beating the probabilistic lower bound on perfect hashing;the impact of heterogeneity and geometry on the proof complexity of random satisfiability;polynomial-time trace reconstruction in the smoothed complexity model;non-linear Hamilton cycles in linear quasi-random hypergraphs;the connectivity threshold for dense graphs;how many vertices does a random walk miss in a network with moderately increasing the number of vertices?;rolling backwards can move you forward: on embedding problems in sparse expanders;tight bounds for parallel paging and green paging;efficient computation of representative weight functions with applications to parameterized counting (extended version);and directed shortest paths via approximate cost balancing.
The proceedings contain 181 papers. The topics discussed include: an almost 2-approximation for all-pairs of shortest paths in subquadratic time;truly subcubic min-plus product for less structured matrices, with appli...
ISBN:
(纸本)9781611975994
The proceedings contain 181 papers. The topics discussed include: an almost 2-approximation for all-pairs of shortest paths in subquadratic time;truly subcubic min-plus product for less structured matrices, with applications;equivalences between triangle and range query problems;new algorithms and lower bounds for all-pairs max-flow in undirected graphs;tight running time lower bounds for strong inapproximability of maximum k-coverage, unique set cover and related problems (via t-wise agreement testing theorem);learning from satisfying assignments under continuous distributions;a tight analysis of greedy yields subexponential time approximation for uniform decision tree;and nearly optimal edge estimation with independent set queries.
The proceedings contain 183 papers. The topics discussed include: fine-grained complexity meets IP = PSPACE;an equivalence class for orthogonal vectors;seth-based lower bounds for subset sum and bicriteria path;fast m...
The proceedings contain 183 papers. The topics discussed include: fine-grained complexity meets IP = PSPACE;an equivalence class for orthogonal vectors;seth-based lower bounds for subset sum and bicriteria path;fast modular subset sum using linear sketching;a subquadratic approximation scheme for partition;metrical task systems on trees via mirror descent and unfair gluing;a nearly-linear bound for chasing nested convex bodies;dynamic double auctions: towards first best;and multi-unit supply-monotone auctions with Bayesian valuations.
暂无评论