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 contain 70 papers. the topics discussed include: selecting the median;algorithms for graphic polymatroids and parametric s-sets;design of practical and provably good random number generators;a combinat...
ISBN:
(纸本)0898713498
the proceedings contain 70 papers. the topics discussed include: selecting the median;algorithms for graphic polymatroids and parametric s-sets;design of practical and provably good random number generators;a combinatorial algorithm for minimizing symmetric submodular functions;on the entropy of DNA: algorithms and measurements based on memory and rapid convergence;improved algorithms for protein motif recognition;from valid inequalities to heuristics: a unified view of primal-dual approximation algorithms in covering problems;doing two-level logic minimization 100 times faster;on the statistical dependencies of coalesced hashing and their implications for both full and limited independence;efficient parallel computations for singular band matrices;chaining multiple-alignment fragments in sub-quadratic time;finding optimal edge-rankings of trees;dihedral bounds for mesh generation in high dimensions;approximating discrete collections via local improvements;randomized rounding without solving the linear program;finding subsets maximizing minimum structures;average-case analysis of off-line and on-line knapsack problems;Voronoi diagrams of lines in 3-space under polyhedral convex distance functions;and path optimization and near-greedy analysis for graph partitioning: an empirical study.
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.
暂无评论