The symposium materials contain 54 papers. The topics covered include fast deterministic processor allocation, min-cut algorithms, random weighted Laplacians, combinatorial algorithms, dynamic point location, ray shoo...
详细信息
The symposium materials contain 54 papers. The topics covered include fast deterministic processor allocation, min-cut algorithms, random weighted Laplacians, combinatorial algorithms, dynamic point location, ray shooting, iterated nearest neighbors, repeated median line estimator, biconnected subgraphs approximation, vertex colored graphs triangulation, scapegoat trees, shortest path problem, submodular flow problems, geometric graph problems, greedy matching algorithm, physical mapping of chromosomes, non-clairvoyant scheduling, dynamic closest-pair problem, cow-path problem, parallel programs implementation, traveling salesman problem, optimistic sorting and information-theoretic complexity, unconditionally secure secret key, polynomial algorithms, and minimum-cost paths in periodic graphs.
The proceedings contain 135 papers. The topics discussed include: approximating independent sets in sparse graphs;spider covers for prize-collecting network activation problem;on survivable set connectivity;a note on ...
The proceedings contain 135 papers. The topics discussed include: approximating independent sets in sparse graphs;spider covers for prize-collecting network activation problem;on survivable set connectivity;a note on the ring loading problem;new approximation schemes for unspittable flow on a path;welfare maximization with production costs: a primal dual approach;pricing online decisions: beyond actions;on the complexity of computing an equilibrium in combinatorial actions;combinatorial actions via posted prices;minimum forcing sets for miura patterns;universal computation with arbitrary polyomino tiles in non-cooperative self-assembly;efficient and robust persistent homology for measures;zigzag persistence via reflections and transpositions;and more applications of the polynomial method in algorithm design.
The proceedings contain 136 papers. The topics discussed include: a constant factor approximation algorithm for fault-tolerant k-median;improved approximation algorithm for two-dimensional bin packing;a mazing 2+eps a...
ISBN:
(纸本)9781611973389
The proceedings contain 136 papers. The topics discussed include: a constant factor approximation algorithm for fault-tolerant k-median;improved approximation algorithm for two-dimensional bin packing;a mazing 2+eps approximation for unsplittable flow on a path;better approximation bounds for the joint replenishment problem;better algorithms and hardness for broadcast scheduling via a discrepancy approach;an excluded grid theorem for digraphs with forbidden minors;finding small patterns in permutations in linear time;minimum common string partition parameterized by partition size is fixed-parameter tractable;interval deletion is fixed-parameter tractable;efficient computation of representative sets with applications in parameterized and exact algorithms;and on the computational complexity of betti numbers: reductions from matrix rank.
The proceedings contain 135 papers. The topics discussed include: mixing times of Markov chains for self-organizing lists and biased permutations;convergence of multivariate belief propagation, with applications to cu...
ISBN:
(纸本)9781611972511
The proceedings contain 135 papers. The topics discussed include: mixing times of Markov chains for self-organizing lists and biased permutations;convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing;approximate counting via correlation decay on planar graphs;correlation decay up to uniqueness in spin systems;online mixed packing and covering;randomized primal-dual analysis of ranking for online bipartite matching;matroid secretary for regular and decomposable matroids;a new approach to online scheduling: approximating the optimal competitive ratio;weighted flowtime on capacitated machines;weighted graph Laplace operator under topological noise;twisted tabulation hashing;compressed static functions with applications;and adaptive and approximate orthogonal range counting.
The proceedings contain 133 papers. The topics discussed include: an improved competitive algorithm for reordering buffer management;how to meet asynchronously (almost) everywhere;towards the randomized k-server conje...
ISBN:
(纸本)9780898717013
The proceedings contain 133 papers. The topics discussed include: an improved competitive algorithm for reordering buffer management;how to meet asynchronously (almost) everywhere;towards the randomized k-server conjecture: a primal-dual approach;property testing and parameter testing for permutations;on the cell probe complexity of dynamic membership;decomposition, approximation, and coloring of odd-minor-free graphs;the edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs;an (almost) linear time algorithm for odd cycles transversal;a quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing;asymmetric traveling salesman path and directed latency problems;compact ancestry labeling schemes for XML trees;algorithms for ray class groups and Hilbert class fields;data structures for range minimum queries in multidimensional arrays;and counting inversions, offline orthogonal range counting, and related problems.
The proceedings contain 133 papers. The topics discussed include: optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error;the streaming complexity of cycle counting, sorting ...
ISBN:
(纸本)9780898719932
The proceedings contain 133 papers. The topics discussed include: optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with sub-constant error;the streaming complexity of cycle counting, sorting by reversals, and other problems;streaming k-means on well-clusterable data;exponential time improvement for mm-wise based algorithms;a simple and fast 2-approximation algorithms for the one-warehouse multi-retailers problem;generalized machine activation problems;online scheduling on identical machines using SRPT;a complete resolution of the Keller maximum clique problem;on independent sets in random graphs;coloring random graphs online without creating monochromatic subgraphs;a subexponential lower bound for the random facet algorithm for parity games;on minmax theorems for multiplayer games;near-optimal no-regret algorithms for zero-sum games;shortest non-crossing walks in the plane;and computing shortest paths amid pseudodisks.
The proceedings contain 139 papers. The topics discussed include: a PTAS for TSP with neighborhoods among fat regions in the plane;squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition;a ...
ISBN:
(纸本)9780898716245
The proceedings contain 139 papers. The topics discussed include: a PTAS for TSP with neighborhoods among fat regions in the plane;squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition;a near linear time constant factor approximation for Euclidean bichromatic matching (cost);compacting cuts: a new linear formulation for minimum cut;linear programming relaxations of maxcut;efficient solutions to relaxations of combinatorial problems with submodular penalties via the Lovász extension and non-smooth convex optimization;efficient algorithms for computing all low s-t edge connectivities and related problems;the approximation complexity of win-lose games;convergence to approximate Nash equilibria in congestion games;efficient contention resolution protocols for selfish agents;considering suppressed packets improves buffer management in QoS switches;and instability of FIFO in the permanent sessions model at arbitrarily small network loads.
The proceedings contain 181 papers. The topics discussed include: a framework for similarity search with space-time tradeoffs using locality-sensitive filtering;LSH forest: practical algorithms made theoretical;faster...
ISBN:
(纸本)9781611974782
The proceedings contain 181 papers. The topics discussed include: a framework for similarity search with space-time tradeoffs using locality-sensitive filtering;LSH forest: practical algorithms made theoretical;faster approximation schemes for the two-dimensional knapsack problem;split packing: an algorithm for packing circles with optimal worst-case density;local search for max-sum diversification;maximum scatter tsp in doubling metrics;exploring an infinite space with finite memory scouts;parameter-free locality sensitive hashing for spherical range reporting;distance sensitive bloom filters without false negatives;optimal approximate polytope membership;and massively-parallel similarity join, edge-isoperimetry, and distance correlations on the hypercube.
The proceedings contain 129 papers. The topics discussed include: union-find with deletions;on directed Steiner trees;cache oblivious search trees via binary trees of small height;a locality-preserving cache-oblivious...
ISBN:
(纸本)089871513X
The proceedings contain 129 papers. The topics discussed include: union-find with deletions;on directed Steiner trees;cache oblivious search trees via binary trees of small height;a locality-preserving cache-oblivious dynamic dictionary;optimal time-space trade-offs for non-comparison-based sorting;an approximation algorithm for the group Steiner problem;static optimality and dynamic search-optimality in lists and trees;improved algorithms for the data placement problem;web caching with request reordering;censorship resistant peer-to-peer content addressable networks;an ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph;undiscretized dynamic programming: faster algorithms for facility location and related problems on trees;Delaunay triangulation programs on surface data;dense point sets have sparse Delaunay triangulations;and quality meshing with weighted Delaunay refinement.
The proceedings contain 146 papers. The topics discussed include: locality-sensitive hashing without false negatives;new directions in nearest neighbor searching with applications to lattice sieving;phase transitions ...
ISBN:
(纸本)9781510819672
The proceedings contain 146 papers. The topics discussed include: locality-sensitive hashing without false negatives;new directions in nearest neighbor searching with applications to lattice sieving;phase transitions in group testing;tight bounds for the distribution-free testing of monotone conjunctions;designing networks with good equilibria under uncertainty;characterization of strongly stable matchings;learning and efficiency in games with dynamic population;on dynamic approximate shortest paths for planar graphs with worst case costs;error amplification for pairwise spanner lower bounds;on notions of distortion and an almost minimum spanning tree with constant average distortion;approximately efficient double auctions with strong budget balance;and interpolating between truthful and non-truthful mechanisms for combinatorial auctions.
暂无评论