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 180 papers. the topics discussed include: dynamic algorithms for graph coloring;incremental DFS algorithms: a theoretical and experimental study;decremental transitive closure and shortest path...
ISBN:
(纸本)9781611975031
the proceedings contain 180 papers. the topics discussed include: dynamic algorithms for graph coloring;incremental DFS algorithms: a theoretical and experimental study;decremental transitive closure and shortest paths for planar digraphs and beyond;polycubes with small perimeter defect;the classical complexity of boson sampling;race detection and reachability in nearly series-parallel DAGs;the complexity of independent set reconfiguration on bipartite graphs;metric violation distance: hardness and approximation;a submodular measure and approximate Gomory-Hu theorem for packing odd trails;and minor-matching hypertree width.
the proceedings contain 65 papers. the topics discussed include: a better approximation algorithm for finding planar subgraphs;improving biconnectivity approximation via local optimization;sequential and parallel subq...
ISBN:
(纸本)0898713668
the proceedings contain 65 papers. the topics discussed include: a better approximation algorithm for finding planar subgraphs;improving biconnectivity approximation via local optimization;sequential and parallel subquadratic work algorithms for constructing approximately optimal binary search trees;time and space efficient method-lookup for object-oriented programs;worst-case efficient priority queues;on-line generalized steiner problem;randomized robot navigation algorithms;and scheduling with conflicts, and applications to traffic signal control.
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 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.
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.
暂无评论