the proceedings contains 84 papers from the 8thannualacm-siamsymposium on discretealgorithms. Topics discussed include: discretealgorithms;randomized algorithms;approximation algorithms;information retrieval algo...
详细信息
the proceedings contains 84 papers from the 8thannualacm-siamsymposium on discretealgorithms. Topics discussed include: discretealgorithms;randomized algorithms;approximation algorithms;information retrieval algorithms;graph theory problems;graph vertex partitioning;data structures;constraint theory, queueing theory;NP-hard and NP-complete problems;heuristic methods;computational geometry;sorting algorithms;search algorithms;linear programming and other optimization problems;and applications of discretealgorithms to scheduling problems, communication networks, finite element analysis, and computational molecular biology.
the proceedings contains 167 papers from the Tenthannualacm-siamsymposium on discretealgorithms. Topics discussed include: call control algorithms;motion planning;Heilbronn's triangle problems;asynchronous tra...
详细信息
the proceedings contains 167 papers from the Tenthannualacm-siamsymposium on discretealgorithms. Topics discussed include: call control algorithms;motion planning;Heilbronn's triangle problems;asynchronous transfer mode (ATM) networks;Voronoi diagrams;Petersen matching theorem;Steiner triangulation;Eucledian shortest path queries;Gantt charts;tree queries;collision detection;travelling salesman problems;monotone set systems;optical networks;hierarchical cooperative caching;scheduling problems;Burrows-Wheeler transforms;Janson inequalities;degree spanning tree problems;and hamming center problems.
the proceedings contains 79 papers from the Ninthannualacm-siamsymposium on discretealgorithms. Topics discussed include: local search heuristics;periodic scheduling problems;polynomial time approximation schemes;...
详细信息
the proceedings contains 79 papers from the Ninthannualacm-siamsymposium on discretealgorithms. Topics discussed include: local search heuristics;periodic scheduling problems;polynomial time approximation schemes;univariate polynomial greatest common divisors;Hilbert irreducibility theorem;online file caching;online throughput-competitive algorithms;kinetic binary space partitions;input/output-efficient algorithms;three-dimensional diameter problems;quickest transshipment problems;exact arithmetic;ultimate interval graph recognition algorithms;forbidden hypergraphs;directed Steiner problems;constraint satisfaction problems;maximal matching computations;multiprocessor scheduling;and noisy radio networks.
the proceedings contain 79 papers dealing withthe applications and computational methods used in solving algorithms. Topics discusssed include computation theory, automata theory, combinatorial mathematics, approxima...
详细信息
ISBN:
(纸本)0898713293
the proceedings contain 79 papers dealing withthe applications and computational methods used in solving algorithms. Topics discusssed include computation theory, automata theory, combinatorial mathematics, approximation theory, matrix algebra, geometry and other mathematical techniques used in the procedure.
the proceedings contain 135 papers. the topics discussed include: improved bounds and new techniques for Daveport-Schinzel sequences and their generalizations;perfect matchings via uniform sampling in regular bipartit...
ISBN:
(纸本)9780898716801
the proceedings contain 135 papers. the topics discussed include: improved bounds and new techniques for Daveport-Schinzel sequences and their generalizations;perfect matchings via uniform sampling in regular bipartite graphs;the ratio index for budgeted learning, with applications;approximation algorithms for restless bandit problems;better algorithms for benign bandits;comparison-based time-space lower bounds for selection;linear-time algorithms for geometric graphs with sublinearly many crossings;self-overlapping curves revisited;line transversals of convex polyhedra in R3;optimal halfspace range reporting in three dimensions;decomposition of multiple coverings into more parts;on stars and steiner stars. II;and combinatorial algorithms for nearest neighbors, near-duplicates and small-world design.
the most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithmsthat improve the state-of-the-art for provable classical/quantum algorithms for SVP. ...
详细信息
the most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithmsthat improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results: (1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 \leq q \leq root n, our algorithm takes q13n+o(n) time and requires poly(n) \cdot q16n/q2 memory. this tradeoff, which ranges from enumeration (q = root n) to sieving (q constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for SVP that runs in time 20.950n+o(n) and requires 20.5n+o(n) classical memory and poly(n) qubits. In a quantum random access memory (QRAM) model, this algorithm takes only 20.835n+o(n) time and requires a QRAM of size 20.293n+o(n), poly(n) qubits and 20.5n classical space. this improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventhannualacm on symposium on theory of Computing (STOC), 2015, pp. 733--742] that has a time and space complexity 2n+o(n). (3) A classical algorithm for SVP that runs in time 21.669n+o(n) time and 20.5n+o(n) space. this improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285--306] that has the same space complexity. the time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is 20.402n. We conjecture that for most lattices this quantity is a 2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n), and our quantum algorithm in a QRA
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 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 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 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.
暂无评论