Confronting hardness using a hybrid approach.
A new approach to proving upper bounds for MAX-2-SAT.
Measure and conquer: a simple O(2<sup>0.288<i>n</i></sup>) independent set algorithm.
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph.
The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity.
Local versus global properties of metric spaces.
Directed metrics and directed graph partitioning problems.
Improved embeddings of graph metrics into random trees.
Small hop-diameter sparse spanners for doubling metrics.
Metric cotype.
On nash equilibria for a network creation game.
Approximating unique games.
Computing sequential equilibria for two-player games.
A deterministic subexponential algorithm for solving parity games.
Finding nucleolus of flow game.
Predicting the "unpredictable".
A near-tight approximation lower bound and algorithm for the kidnapped robot problem.
An asymptotic approximation algorithm for 3D-strip packing.
Facility location with hierarchical facility costs.
Combination can be hard: approximability of the unique coverage problem.
Computing steiner minimum trees in Hamming metric.
Robust shape fitting via peeling and grating coresets.
Tightening non-simple paths and cycles on surfaces.
Anisotropic surface meshing.
Simultaneous diagonal flips in plane triangulations.
Morphing orthogonal planar graph drawings.
Overhang.
On the capacity of information networks.
Lower bounds for asymmetric communication channels and distributed source coding.
Self-improving algorithms.
Cake cutting really is not a piece of cake.
Testing triangle-freeness in general graphs.
Constraint solving via fractional edge covers.
Testing graph isomorphism.
Efficient construction of unit circular-arc models.
On the chromatic number of some geometric hypergraphs.
A robust maximum completion time measure for scheduling.
Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling.
Improved approximation algorithms for broadcast scheduling.
Distributed selfish load balancing.
Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management.
Rank/select operations on large alphabets: a tool for text indexing.
<i>O</i>(log log <i>n</i>)-competitive dynamic binary search trees.
The rainbow skip graph: a fault-tolerant constant-degree distributed data structure.
Design of data structures for mergeable trees.
Implicit dictionaries with <i>O</i>(1) modifications per update and fast search.
Sampling binary contingency tables with a greedy start.
Asymmetric balanced allocation with simple hash functions.
Balanced allocation on graphs.
Superiority and complexity of the spaced seeds.
Solving random satisfiable 3CNF formulas in expected polynomial time.
Analysis of incomplete data and an intrinsic-dimension Helly theorem.
Finding large sticks and potatoes in polygons.
Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting.
Vertical ray shooting and computing depth orders for fat objects.
On the number of plane graphs.
All-pairs shortest paths for unweighted undirected graphs in <i>o(mn)</i> time.
An <i>O (n log n)</i> algorithm for maximum <i>st</i>-flow in a directed planar graph.
A simple GAP-canceling algorithm for the generalized maximum flow problem.
Four point conditions and exponential neighborhoods for symmetric TSP.
Upper degree-constrained partial orientations.
On the tandem duplication-random loss model of genome rearrangement.
Reducing tile complexity for self-assembly through temperature programming.
Cache-oblivious string dictionaries.
Cache-oblivious dynamic programming.
A computational study of external-memory BFS algorithms.
Tight approximation algorithms for maximum general assignment problems.
Approximating the <i>k</i>-multicut problem.
The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema.
8/7-approximation algorithm for (1, 2)-TSP.
Improved lower and upper bounds for universal TSP in planar metrics.
Leontief economies encode nonzero sum two-player games.
Bottleneck links, variable demand, and the tragedy of the commons.
The complexity of quantitative concurrent parity games.
Equilibria for economies with production: constant-returns technologies and production planning constraints.
Approximation algorithms for wavelet transform coding of data streams.
Simpler algorithm for estimating frequency moments of data streams.
Trading off space for passes in graph streaming problems.
Maintaining significant stream statistics over sliding windows.
Streaming and sublinear approximation of entropy and information distances.
FPTAS for mixed-integer polynomial optimization with a fixed number of variables.
Linear programming and unique sink orientations.
Generating all vertices of a polyhedron is hard.
A semidefinite programming approach to tensegrity theory and realizability of graphs.
Ordering by weighted number of wins gives a good ranking for weighted tournaments.
Weighted isotonic regression under the <i>L</i><sub>1</sub> norm.
Oblivious string embeddings and edit distance approximations.
Spanners and emulators with sublinear distance errors.
Certifying large branch-width.
DAG-width: connectivity measure for directed graphs.
On the diameter of Eulerian orientations of graphs.
Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition.
Subgraph characterization of Red/Blue-Split Graph and K&ouml;nig Egerv&aacute;ry Graphs.
Critical chromatic number and the complexity of perfect packings in graphs.
On the number of crossing-free matchings, (cycles, and partitions).
Slow mixing of glauber dynamics via topological obstructions.
Quantum verification of matrix products.
Counting without sampling: new algorithms for enumeration problems using statistical physics.
Accelerating simulated annealing for the permanent and combinatorial counting problems.
Query-efficient algorithms for polynomial interpolation over composites.
New lower bounds for oblivious routing in undirected graphs.
Anytime algorithms for multi-armed bandit problems.
Robbing the bandit: less regret in online geometric optimization against an adaptive adversary.
On the competitive ratio of evaluating priced functions.
Randomized online algorithms for minimum metric bipartite matching.
Random graphs.
Analyzing BitTorrent and related peer-to-peer networks.
Oblivious network design.
The price of being near-sighted.
Scalable leader election.
Deterministic boundary recognition and topology extraction for large sensor networks.
Improved lower bounds for embeddings into <i>L</i><sub>1</sub>.
<i>l</i><sup>2</sup><sub>2</sub> spreading metrics for vertex ordering problems.
Trees and Markov convexity.
An algorithmic Friedman--Pippenger theorem on tree embeddings and applications to routing.
A tight upper bound on the probabilistic embedding of series-parallel graphs.
Single-value combinatorial auctions and implementation in undominated strategies.
An improved approximation algorithm for combinatorial auctions with submodular bidders.
Revenue maximization when bidders have budgets.
Knapsack auctions.
Single-minded unlimited supply pricing on sparse instances.
The complexity of matrix completion.
Relating singular values and discrepancy of weighted directed graphs.
Matrix approximation and projective clustering via volume sampling.
Sampling algorithms for <i>l</i><sub>2</sub> regression and applications.
The hunting of the bump: on maximizing statistical discrepancy.
A general approach for incremental approximation and hierarchical clustering.
The space complexity of pass-efficient algorithms for clustering.
Correlation clustering with a fixed number of clusters.
On <i>k</i>-Median clustering in high dimensions.
Entropy based nearest neighbor search in high dimensions.
A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries.
Efficient algorithms for substring near neighbor problem.
Many distances in planar graphs.
Pattern matching with address errors: rearrangement distances.
Squeezing succinct data structures into entropy bounds.
Dictionaries using variable-length keys and data, with applications.
Lower bounds on the size of selection and rank indexes.
Dynamic dictionary matching and compressed suffix trees.
A categorization theorem on suffix arrays with applications to space efficient text indexes.
Towards a complete characterization of tries.
Inoculation strategies for victims of viruses and the sum-of-squares partition problem.
Marriage, honesty, and stability.
Market equilibria for homothetic, quasi-concave utilities and economies of scale in production.
On the polynomial time computation of equilibria for certain exchange economies.
Computing equilibria in multi-player games.
On distance scales, embeddings, and efficient relaxations of the cut cone.
Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut.
The complexity of low-distortion embeddings between point sets.
Approximation algorithms for low-distortion embeddings into low-dimensional spaces.
A tight threshold for metric Ramsey phenomena.
The interface between computational and combinatorial geometry.
Multiple-source shortest paths in planar graphs.
Computing the shortest path: <i>A</i> search meets graph theory.
Finding large cycles in Hamiltonian graphs.
Approximating connectivity augmentation problems.
Primal-dual approach for directed vertex connectivity augmentation and generalizations.
Multidimensional balanced allocations.
Online client-server load balancing without global information.
Job shop scheduling with unit processing times.
Approximating the average response time in broadcast scheduling.
Improved schedule for radio broadcast.
On levels in arrangements of surfaces in three dimensions.
Distributions of points in the unit-square and large <i>k</i>-gons.
On geometric permutations induced by lines transversal through a fixed point.
Approximation hardness of optimization problems in intersection graphs of <i>d</i>-dimensional boxes.
Isomorphism and embedding problems for infinite limits of scale-free graphs.
Adversarial deletion in a scale free random graph process.
The influence of search engines on preferential attachment.
On the spread of viruses on the internet.
Analyzing and characterizing small-world graphs.
Substring compression problems.
Optimizing markov models with applications to triangular connectivity coding.
Dotted interval graphs and high throughput genotyping.
Algorithms for combining rooted triplets into a galled phylogenetic network.
Unknotting is in AM cup co-AM.
A constant approximation algorithm for the one-warehouse multi-retailer problem.
Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy.
Online convex optimization in the bandit setting: gradient descent without a gradient.
Adaptivity and approximation for stochastic packing problems.
Theory of semidefinite programming for sensor network localization.
An O(VE) algorithm for ear decompositions of matching-covered graphs.
Popular matchings.
Dominator tree verification and vertex-disjoint paths.
Online topological ordering.
All maximal independent sets and dynamic dominance for sparse graphs.
LP decoding achieves capacity.
Maximum-likelihood decoding of Reed-Solomon codes is NP-hard.
Collecting correlated information from a sensor network.
Deterministic network coding by matrix completion.
Network coding: does the model need tuning?
Pianos are not flat: rigid motion planning in three dimensions.
A constant-factor approximation algorithm for optimal terrain guarding.
Ray shooting amid balls, farthest point from a line, and range emptiness searching.
Space-time tradeoffs for approximate spherical range counting.
Online conflict-free coloring for intervals.
Loop quantum gravity.
Approximation algorithms for cycle packing problems.
Approximating the smallest <i>k</i>-edge connected spanning subgraph by LP-rounding.
Partial covering of hypergraphs.
Approximating vertex cover on dense graphs.
Bidimensionality: new connections between FPT algorithms and PTASs.
Limitations of cross-monotonic cost sharing schemes.
A group-strategyproof mechanism for Steiner forests.
Collusion-resistant mechanisms for single-parameter agents.
A multiple-choice secretary algorithm with applications to online auctions.
Rounds vs queries trade-off in noisy computation.
Distributed approaches to triangulation and embedding.
Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics.
Sparse source-wise and pair-wise distance preservers.
Lower bound for sparse Euclidean spanners.
New constructions of (alpha, beta)-spanners and purely additive spanners.
Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality.
Dissections and trees, with applications to optimal mesh encoding and to random sampling.
The expected value of random minimal length spanning tree of a complete graph.
Girth restrictions for the 5-flow conjecture.
Linear equations, arithmetic progressions and hypergraph property testing.
The relative worst order ratio applied to paging.
Strictly convex drawings of planar graphs.
External-memory exact and approximate all-pairs shortest-paths in undirected graphs.
Graph distances in the streaming model: the value of space.
Lower bounds for external algebraic decision trees.
On hierarchical routing in doubling metrics.
Fast convergence of selfish rerouting.
Oblivious routing on node-capacitated and directed graphs.
Distributed online call control on general networks.
An optimal online algorithm for packet scheduling with agreeable deadlines.
An optimal dynamic interval stabbing-max data structure?
Self-adjusting top trees.
An optimal Bloom filter replacement.
Efficient hashing with lookups in two memory accesses.
Improved range-summable random variable construction algorithms.
A spectral heuristic for bisecting random graphs.
Complete partitions of graphs.
Two algorithms for general list matrix partitions.
How fast is the k-means method?
On approximating the depth and related problems.
Multicoloring unit disk graphs on triangular lattice points.
An asymptotic approximation scheme for multigraph edge coloring.
Computing minimal triangulations in time O(n<sup>alpha</sup> log n) = o(n<sup>2.376</sup>).
Finding the shortest bottleneck edge in a parametric minimum spanning tree.
On the random 2-stage minimum spanning tree.
Rigorous analysis of heuristics for NP-hard problems.
An improved approximation algorithm for virtual private network design.
Network design for information networks.
On the approximability of some network design problems.
Approximating k-median with non-uniform capacities.
Improved approximation for universal facility location.
The cover time of two classes of random graphs.
Coupling with the stationary distribution and improved sampling for colorings and independent sets.
Sampling regular graphs and a peer-to-peer network.
The bin-covering technique for thresholding random geometric graph properties.
Random planar graphs with <i>n</i> nodes and a fixed number of edges.
Provably good moving least squares.
Manifold reconstruction from point samples.
Delaunay triangulations approximate anchor hulls.
Greedy optimal homotopy and homology generators.
Controlled perturbation for Delaunay triangulations.
Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group.
Matrix rounding with low error in small submatrices.
Can the TPRI structure help us to solve the algebraic eigenproblem?
Optimal random number generation from a biased coin.
A new look at survey propagation and its generalizations.
Coins make quantum walks faster.
Quantum algorithms for the triangle problem.
The hidden subgroup problem and permutation group theory.
Testing hierarchical systems.
Conformance testing in the presence of multiple faults.
Online ascending auctions for gradually expiring items.
Near-optimal online auctions.
On profit-maximizing envy-free pricing.
Improved recommendation systems.
Selfish routing with atomic players.
Succinct ordinal trees with level-ancestor queries.
Compact representations of ordered sets.
Tight bounds for the partial-sums problem.
The Bloomier filter: an efficient data structure for static support lookup tables.
Meldable RAM priority queues and minimum directed spanning trees.
Finding a long directed cycle.
A new algorithm for normal dominance constraints.
Rank-maximal matchings.
Network failure detection and graph connectivity.
The directed circular arrangement problem.
Variable length path coupling.
Linear phase transition in random linear constraint satisfaction problems.
Quantitative stochastic parity games.
On distributions computable by random walks on graphs.
Exponential bounds for DPLL below the satisfiability threshold.
Who says you have to look at the input? The brave new world of sublinear computing.
Complexity classification of network information flow problems.
An improved data stream algorithm for frequency moments.
Efficient estimation algorithms for neighborhood variance and other moments.
Optimal space lower bounds for all frequency moments.
Optimal routing in Chord.
Approximation schemes for multidimensional packing.
New approximability and inapproximability results for 2-dimensional Bin Packing.
On rectangle packing: maximizing benefits.
Optimal online bounded space multidimensional packing.
Windows scheduling as a restricted version of Bin Packing.
Special edges, and approximating the smallest directed <i>k</i>-edge connected spanning subgraph.
On colorings of squares of outerplanar graphs.
Detecting short directed cycles using rectangular matrix multiplication and dynamic programming.
Approximating Minimum Max-Stretch spanning Trees on unweighted graphs.
Approximate distance oracles for unweighted graphs in &Otilde;(n<sup>2</sup>) time.
Retroactive data structures.
Proximity Mergesort: optimal in-place sorting in the cache-oblivious model.
The number of bit comparisons used by Quicksort: an average-case analysis.
Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time.
The hyperring: a low-congestion deterministic data structure for distributed environments.
Improved upper bounds for 3-SAT.
Locally satisfiable formulas.
A stronger bound on Braess's Paradox.
Multicommodity facility location.
SRPT optimally utilizes faster machines to minimize flow time.
A faster distributed protocol for constructing a minimum spanning tree.
Experimental analysis of dynamic all pairs shortest path algorithms.
Graph decomposition and a greedy algorithm for edge-disjoint paths.
Models of greedy algorithms for graph problems.
The list partition problem for graphs.
A time efficient Delaunay refinement algorithm.
Almost-Delaunay simplices: nearest neighbor relations for imprecise points.
Output-sensitive construction of the union of triangles.
An optimal randomized algorithm for maximum Tukey depth.
Minimizing the stabbing number of matchings, trees, and triangulations.
Adaptive sampling for quickselect.
Fast mixing for independent sets, colorings and other models on trees.
Slow mixing of Glauber dynamics for the hard-core model on the hypercube.
Probabilistic analysis of knapsack core algorithms.
Torpid mixing of simulated tempering on the Potts model.
Minimum moment Steiner trees.
Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs.
Approximation schemes for Metric Bisection and partitioning.
Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks.
Correlation Clustering: maximizing agreements via semidefinite programming.
Quantum computing.
Interpolation search for non-independent data.
Dynamizing static algorithms, with applications to dynamic trees and history independence.
Caching queues in memory buffers.
LAND: stretch (1 + epsilon) locality-aware networks for DHTs.
A note on the nearest neighbor in growth-restricted metrics.
Buffer minimization using max-coloring.
On minimizing the total flow time on multiple machines.
Matrix rounding and approximation.
A general approach to online network optimization problems.
Approximate local search in combinatorial optimization.
Trade-offs on the location of the core node in a network.
On the convergence time of a path-vector protocol.
Tabulation based 4-universal hashing with applications to second moment estimation.
Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem.
Competitive analysis of organization networks or multicast acknowledgement: how much to wait?
When indexing equals compression: experiments with compressing suffix arrays and applications.
Approximate Nearest Neighbor under edit distance via product metrics.
Fast approximate pattern matching with few indels via embeddings.
Lyndon words with a fixed standard right factor.
Compression boosting in optimal linear time using the Burrows-Wheeler Transform.
Dimension reduction for ultrametrics.
Randomized <i>k</i>-server algorithms for growth-rate bounded graphs.
The pure literal rule threshold and cores in random hypergraphs.
Efficient algorithms for bichromatic separability.
On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems.
Frugality in path auctions.
An exact subexponential-time lattice algorithm for Asian options.
Structural and algorithmic aspects of massive social networks.
A determinant-based algorithm for counting perfect matchings in a general graph.
On the number of rectangular partitions.
Computing equilibria for congestion games with (im)perfect information.
Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates.
Algorithms for infinite huffman-codes.
A certifying algorithm for the consecutive-ones property.
Generic quantum Fourier transforms.
Quasiconvex analysis of backtracking algorithms.
Navigating nets: simple algorithms for proximity search.
Approximating the two-level facility location problem via a quasi-greedy approach.
A maiden analysis of Longest Wait First.
A deterministic near-linear time algorithm for finding minimum cuts in planar graphs.
Subexponential parameterized algorithms on graphs of bounded-genus and <i>H</i>-minor-free graphs.
Equivalence of local treewidth and linear local treewidth and its algorithmic applications.
Hole and antihole detection in graphs.
Testing bipartiteness of geometric intersection graphs.
Finding dominators revisited: extended abstract.
How random is the human genome?
Complexities for generalized models of self-assembly.
Invadable self-assembly: combining robustness with efficiency.
On contract-and-refine transformations between phylogenetic trees.
Reconstructing strings from random traces.
Improved bounds on sorting with length-weighted reversals.
Point containment in the integer hull of a polyhedron.
Covering minimum spanning trees of random subgraphs.
A characterization of easily testable induced subgraphs.
Bipartite roots of graphs.
Two tricks to triangulate chordal probe graphs in polynomial time.
Non-migratory online deadline scheduling on multiprocessors.
The maximum latency of selfish routing.
Minimizing migrations in fair multiprocessor scheduling of persistent tasks.
The wake-up problem in multi-hop radio networks.
A fast approximation scheme for fractional covering problems with variable upper bounds.
On broadcasting in heterogenous networks.
End-to-end packet-scheduling in wireless ad-hoc networks.
Routing and scheduling in multihop wireless networks with time-varying channels.
Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ.
Fair and efficient router congestion control.
Randomized pursuit-evasion with limited visibility.
Fault-tolerant gathering algorithms for autonomous mobile robots.
Approximate classification via earthmover metrics.
Facility location with Service Installation Costs.
On finding a guard that sees most and a shop that sells most.
On the diameter of the symmetric group: polynomial bounds.
The power of basis selection in fourier sampling: hidden subgroup problems in affine groups.
Simultaneous diophantine approximation with excluded primes.
Constructing finite field extensions with large order elements.
Polynomial interpolation from multiples.
Optimal parallel selection.
Selection with monotone comparison cost.
Property testing of data dimensionality.
Comparing top k lists.
Algorithms for power savings.
Dynamic TCP acknowledgement: penalizing long delays.
Approximately optimal control of fluid networks.
Minimum cost flows over time without intermediate storage.
Sublogarithmic approximation for telephone multicast: path out of jungle.
On the performance of user equilibria in traffic networks.
Faster approximation algorithms for the minimum latency problem.
Data migration to minimize the average completion time.
Browsing around a digital library.
Binary space partitions for 3D subdivisions.
Allocating vertex pi-guards in simple polygons via pseudo-triangulations.
Straight-skeleton based contour interpolation.
M&ouml;bius-invariant natural neighbor interpolation.
Improved bounds on the average length of longest common subsequences.
Directed scale-free graphs.
The cover time of sparse random graphs.
Perfect matchings in random graphs with prescribed minimal degree.
Certifying algorithms for recognizing interval graphs and permutation graphs.
Dominating sets in planar graphs: branch-width and exponential speed-up.
Quick and good facility location.
Chain decompositions and independent trees in 4-connected graphs.
Optimizing misdirection.
Online learning in online auctions.
An approximate truthful mechanism for combinatorial auctions with single parameter agents.
Competitiveness via consensus.
Pass efficient algorithms for approximating large matrices.
Rangesum histograms.
Approximation of functions over redundant dictionaries using coherence.
Counting inversions in lists.
Certifying and repairing solutions to large LPs how good are LP-solvers?
An improved approximation algorithm for the 0-extension problem.
Packing Steiner trees.
Integrality ratio for group Steiner trees and directed steiner trees.
The flow complex: a data structure for geometric modeling.
Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio.
On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres.
Perturbations and vertex removal in a 3D delaunay triangulation.
Root comparison techniques applied to computing the additively weighted Voronoi diagram.
Random walks on the vertices of transportation polytopes with constant number of sources.
Smaller explicit superconcentrators.
A (1+epsilon)-approximation algorithm for partitioning hypergraphs using a new algorithmic version of the Lov&aacute;sz Local Lemma.
A spectral technique for random satisfiable 3CNF formulas.
Random MAX SAT, random MAX CUT, and their phase transitions.
Space-efficient finger search on degree-balanced search trees.
Skip graphs.
Maintaining all-pairs approximate shortest paths under deletion of edges.
A faster and simpler fully dynamic transitive closure.
Data streams: algorithms and applications.
Sparse distance preservers and additive spanners.
Multi-embedding and path approximation of metric spaces.
Approximation algorithm for embedding metrics into a two-dimensional space.
On the complexity of distance-based evolutionary tree reconstruction.
Improved results for directed multicut.
Algorithms for k-colouring and finding maximal independent sets.
Equitable colorings with constant number of colors.
Better performance bounds for finding the smallest k-edge connected spanning subgraph of a multigraph.
A note on the set systems used for broadcast encryption.
Lower bounds for collusion-secure fingerprinting.
Quantum property testing.
Quantum algorithms for some hidden shift problems.
Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk.
Non-independent randomized rounding.
Minimizing weighted flow time.
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph.
Lower bounds for embedding edit distance into normed spaces.
Embedding k-outerplanar graphs into l1.
Embeddings and non-approximability of geometric problems.
Better algorithms for high-dimensional proximity problems via asymmetric embeddings.
Lower bounds for external memory dictionaries.
Online paging with arbitrary associativity.
The set-associative cache performance of search trees.
Computing strongly connected components in a linear number of symbolic steps.
On the rectilinear crossing number of complete graphs.
Matching planar maps.
Dynamic generators of topologically embedded graphs.
Computing homotopic shortest paths in the plane.
Fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time.
Edge disjoint paths revisited.
A new approximation algorithm for the asymmetric TSP with triangle inequality.
Approximating asymmetric maximum TSP.
The k-traveling repairman problem.
Directed graphs requiring large numbers of shortcuts.
Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time.
Compact representations of separable graphs.
Labeling schemes for small distances in trees.
On AC<sup>0</sup> implementations of fusion trees and atomic heaps.
Who cares about permanents?
Between O(nm) and O(n alpha).
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons.
A 5/4-approximation algorithm for minimum 2-edge-connectivity.
Fault-tolerant facility location.
Efficient sequences of trials.
Pursuit-evasion with imprecise target location.
Unconditional proof of tightness of Johnson bound.
Deterministic identity testing for multivariate polynomials.
Competitive queueing policies for QoS switches.
Dynamic routing on networks with fixed-size buffers.
Dynamic construction of Bluetooth scatternets of fixed degree and low diameter.
Scheduling techniques for media-on-demand.
Smaller core-sets for balls.
Zonotopes as bounding volumes.
Sublinear-time approximation of Euclidean minimum spanning tree.
An approximation algorithm for cutting out convex polygons.
Inferring tree topologies using flow tests.
Wavelength assignment and generalized interval graph coloring.
An improved approximation algorithm for the partial latin square extension problem.
Multirate rearrangeable clos networks and a generalized edge coloring problem on bipartite graphs.
High-order entropy-compressed text indexes.
Multidimensional matching and fast search in suffix trees.
Inplace 2D matching in compressed images.
The similarity metric.
Static optimality and dynamic search-optimality in lists and trees.
Optimal time-space trade-offs for non-comparison-based sorting.
Union-find with deletions.
A locality-preserving cache-oblivious dynamic dictionary.
Cache oblivious search trees via binary trees of small height.
An approximation algorithm for the group Steiner problem.
On directed Steiner trees.
An 8/13-approximation algorithm for the asymmetric maximum TSP.
Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems.
An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph.
Censorship resistant peer-to-peer content addressable networks.
Web caching with request reordering.
Improved algorithms for the data placement problem.
Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees.
Temporary tasks assignment resolved.
Dense point sets have sparse Delaunay triangulations: or "... but not too nasty".
Delaunay triangulation programs on surface data.
Quality meshing with weighted Delaunay refinement.
Linear-size approximate voronoi diagrams.
Motorcycle graphs and straight skeletons.
Faster approximation schemes for fractional multicommodity flow problems.
Flows over time with load-dependent transit times.
Improved bounds for the unsplittable flow problem.
NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow.
How unfair is optimal routing?
Approximation algorithms for grammar-based compression.
Improving table compression with combinatorial optimization.
Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits.
Succinct representations of lcp information and improvements in the compressed suffix arrays.
Succinct indexable dictionaries with applications to encoding k-ary trees and multisets.
Jenga.
Guessing secrets with inner product questions.
Guessing secrets efficiently via list decoding.
How to cut a cake almost fairly.
The mathematics of playing golf.
Computing shortest paths with comparisons and additions.
An optimal algorithm for checking regularity (extended abstract).
Edge dominating and hypomatchable sets.
An algorithm for counting maximum weighted independent sets and its applications.
Algorithms for quantified Boolean formulas.
Balls and bins models with feedback.
A note on random 2-SAT with prescribed literal degrees.
Mixing time and long paths in graphs.
The diameter of a long range percolation graph.
Is the internet fractal?
Center and diameter problems in plane triangulations and quadrangulations.
Symmetric drawings of triconnected planar graphs.
Layout area of the hypercube (extended abstract).
I/O-optimal algorithms for planar graphs using separators.
Polynomial time recognition of P4-structure.
Adaptive intersection and t-threshold problems.
Separable attributes: a technique for solving the sub matrices character count problem.
Tiling groups for Wang tiles.
Generating random factored numbers, easily.
Tight bounds for worst-case equilibria.
Broadcast scheduling: when fairness is fine.
Harmonic broadcasting is optimal.
Windows scheduling problems for broadcast systems.
Scheduling protocols for switches with large envelopes.
Covering shapes by ellipses.
Slice and dice: a simple, improved approximate tiling recipe.
Binary space partitions for line segments with a limited number of directions.
Closest-point problems simplified on the RAM.
Semi-online maintenance of geometric optima and measures.
Generalized clustering.
New bounds for multi-dimensional packing.
Computer assisted proof of optimal approximability results.
MAX CUT in cubic graphs.
Approximating minimum unsatisfiability of linear equations.
On-line algorithms for the dynamic traveling repair problem.
Competitive on-line switching policies.
A randomized online algorithm for bandwidth utilization.
Caching with expiration times.
On-line scheduling of a single machine to minimize total weighted completion time.
Hardware-assisted computation of depth contours.
The freeze-tag problem: how to wake up a swarm of robots.
The wake up and report problem is time-equivalent to the firing squad synchronization problem.
Tree exploration with little memory.
Efficient proper 2-coloring of almost disjoint hypergraphs.
Experimental analysis of simple, distributed vertex coloring algorithms.
On semidefinite programming relaxations for graph coloring and vertex cover.
Approximating k-cuts via network strength.
Reductions in streaming algorithms, with an application to counting triangles in graphs.
Sampling from a moving window over streaming data.
Maintaining stream statistics over sliding windows (extended abstract).
Testing satisfiability.
Efficient pattern-matching with don't cares.
Efficient algorithms for document retrieval problems.
The string edit distance matching problem with moves.
Simple approximation algorithm for nonoverlapping local alignments.
A sub-quadratic sequence alignment algorithm for unrestricted cost matrices.
On adaptive deterministic gossiping in ad hoc radio networks.
Expansion of product replacement graphs.
Explicit constructions of selectors and related combinatorial structures, with applications.
Derandomized dimensionality reduction with applications.
Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms.
Existence theorems, lower bounds and algorithms for scheduling to meet two objectives.
Scheduling split intervals.
Throughput maximization of real-time scheduling with batching.
(Incremental) priority algorithms.
Improved algorithms for stretch scheduling.
Shape dimension and approximation from samples.
Smooth-surface reconstruction in near-linear time.
Computing the writhing number of a polygonal knot.
Pseudo-line arrangements: duality, algorithms, and applications.
On the overlay of envelopes in four dimensions.
Preprocessing an undirected planar network to enable fast approximate distance queries.
Approximate distance oracles for geometric graphs.
Oracles for distances avoiding a link-failure.
Roundtrip spanners and roundtrip routing in directed graphs.
Light spanners and approximate TSP in weighted graphs with forbidden minors.
Capacitated vertex covering with applications.
Construction of probe interval models.
A new algorithm for protein folding in the HP model.
An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing.
Approximating minimum quartet inconsistency (abstract).
Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning.
Smoothed analysis of the perceptron algorithm for linear programming.
A fully combinatorial algorithm for submodular function minimization.
0/1 optimization and 0/1 primal separation are equivalent.
Labeling schemes for flow and connectivity.
Reachability and distance queries via 2-hop labels.
Improved labeling scheme for ancestor queries.
A comparison of labeling schemes for ancestor queries.
Incentive-compatible online auctions for digital goods.
Online algorithms for market clearing.
Pricing multicasting in more practical network models.
Frugal path mechanisms.
Erratum: an approximation algorithm for minimum-cost vertex-connectivity problems.
Combinatorial approximation algorithms for the maximum directed cut problem.
Approximation algorithms for the 0-extension problem.
A faster implementation of the Goemans-Williamson clustering algorithm.
Tree packing and approximating k-cuts.
Generating well-shaped Delaunay meshed in 3D.
Approximation algorithms for TSP with neighborhoods in the plane.
Dynamic skin triangulation.
Online point location in planar arrangements and its applications.
Reconciling simplicity and realism in parallel disk models.
Distribution sort with randomizing cycle.
External memory BFS on undirected graphs with bounded degree.
I/O-efficient algorithms for graphs of bounded treewidth.
Constructing worst case instances for semidefinite programming based approximation algorithms.
Randomizing combinatorial algorithms for linear programming when the dimension is moderately high.
Approximation algorithms for the metric labeling problem via a new linear programming formulation.
Lattice approximation and linear discrepency of totally unimodular matrices.
On polynomial approximation to the shortest lattice vector length.
Approximation for minimum triangulation of convex polyhedra.
Optimal covering tours with turn costs.
Maintaining approximate extent measures of moving points.
Simplified kinetic connectivity for rectangles and hypercubes.
Static and kinetic geometric spanners with applications.
Gossip is synteny: incomplete gossip and an exact algorithm for syntenic distance.
Absolute convergence: true trees from short sequences.
Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining.
A probabilistic analysis of a greedy algorithm arising from computational biology.
On the midpath tree conjuncture: a counter-example.
Distance labeling in graphs.
Steiner points in tree metrics don't (really) help.
Fast approximation of centrality.
K-pair delay constrained minimum cost routing in undirected networks.
A deterministic algorithm for the cost-distance problem.
Shape sensitive geometric permutations.
Geometric permutations of high dimensional spheres.
Inserting an edge into a planar graph.
Entropy-preserving cuttings and space-efficient planar point location.
A simple entropy-based algorithm for planar point location.
An experimental study of an opportunistic index.
Overlap matching.
A linear lower bound on index size for text retrieval.
Pattern matching for sets of segments.
Approximate subset matching with Don't Cares.
Dynamic string searching.
On approximating the achromatic number.
Coloring k-colorable graphs using smaller palettes.
Approximating coloring and maximum independent sets in 3-uniform hypergraphs.
Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
Computing optimal alpha-fat and alpha-small decompositions.
Optimal planar point location.
Polygonal path approximation with angle constraints.
Reconstructing a collection of curves with corners and endpoints.
Web caching using access statistics.
Competitive on-line stream merging algorithms for media-on-demand.
On-line restricted caching.
Approximate majorization and fair online load balancing.
Game theory, algorithms, and the Internet.
Learning Markov networks: maximum bounded tree-width graphs.
Approximately covering by cycles in planar graphs.
Practical approximation algorithms for zero- and bounded-skew trees.
Approximating the minimum strongly connected subgraph via a matching lower bound.
Improved approximation algorithms for rectangle tiling and packing.
Sublinear time approximate clustering.
Efficient oblivious transfer protocols.
Constructing pseudo-random permutations with a prescribed structure.
Robust algorithms for restricted domains.
Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract).
A polynomial time recognition algorithm for probe interval graphs.
Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width.
A new constructive root bound for algebraic expressions.
Orderly spanning trees with applications to graph encoding and graph drawing.
Alternatives to splay trees with O(log n) worst-case access times.
Worst case constant time priority queue.
Representing dynamic binary trees succinctly.
Making data structures confluently persistent.
Compact labeling schemes for ancestor queries.
Better approximation algorithms for bin covering.
New approaches to covering and packing problems.
Parallel processor scheduling with delay constraints.
Approximation algorithms for extensible bin packing.
Scheduling precedence-constrained jobs with stochastic processing times on parallel machines.
Loss-bounded analysis for differentiated services.
Stability preserving transformations: packet routing networks with edge capacities and speeds.
Distributed admission control, scheduling, and routing with stale information.
On algorithms for efficient data migration.
Fast distributed graph coloring with O(Delta) colors.
Improved algorithms for fault tolerant facility location.
Algorithms for facility location problems with outliers.
The probabilistic relationship between the assignment and asymmetric traveling salesman problems.
Approximation algorithms for data placement in arbitrary networks.
Polynomial-time approximation schemes for geometric graphs.
Morphing between polylines.
Fast implementation of depth contours using topological sweep.
Computing the depth of a flat.
Which formulae shrink under random restrictions?
Selective families, superimposed codes, and broadcasting on unknown radio networks.
Adversarial models in evolutionary game dynamics.
The phase transition in 1-in-k SAT and NAE 3-SAT.
Guessing secrets.
Can entropy characterize performance of online algorithms?.
Competitive auctions and digital goods.
Towards understanding the predictability of stock markets from the perspective of computational complexity.
Performance guarentee for online deadline scheduling in the presence of overload.
Assigning chain-like tasks to a chain-like network.
The inverse nearest neighbor problem with astrophysical applications.
Reductions among high dimensional proximity problems.
A cell probe lower bound for dynamic nearest-neighbor searching.
Shape matching using edit-distance: an implementation.
On validating planar worlds.
Improved fast integer sorting in linear space.
Single-source shortest-paths on arbitrary directed graphs in linear average-case time.
Optimal constrained graph exploration.
An efficient algorithm for the configuration problem of dominance graphs.
Linear reductions of maximum matching.
Internet packet filter management and rectangle geometry.
Faster kinetic heaps and their use in broadcast scheduling.
Finding least common ancestors in directed acyclic graphs.
On binary searching with non-uniform costs.
Soft kinetic data structures.
Testing graphs for colorable properties.
Random lifts of graphs.
IMproved results for route planning in stochastic transportation.
Hill-climbing finds random planted bisections.
On universally easy classes for NP-complete problems.
The diameter of random massive graphs.
Domatic partitions and the Lov&aacute;sz local lemma.
Equitable colorings extend Chernoff-Hoeffding bounds.
Universal configurations in light-flipping games.
On the discrete Bak-Sneppen model of self-organized criticality.
epsilon-Approximate linear programs: new bounds and computation.
Orthogonal graph drawing with constraints.
Fast practical solution of sorting by reversals.
Commuting with delay prone buses.
Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lov&aacute;sz local lemma.
On the complexity of bicoloring clique hypergraphs of graphs (extended abstract).
Weakly chordal graph algorithms via handles.
Recognizing dart-free perfect graphs.
An optimal algorithm for hyperplane depth in the plane.
On Heilbronn's problem in higher dimension.
Finding minimal triangulations of convex 3-polytopes is NP-hard.
A point-placement strategy for conforming Delaunay tetrahedralization.
Digraph minors and algorithms (abstract only).
Cooperative facility location games.
<i>K</i>-medians, facility location, and the Chernoff-Wald bound.
Improved approximation algorithms for MAX SAT.
Strengthening integrality gaps for capacitated network design and covering problems.
Towards a 4/3 approximation for the asymmetric traveling salesman problem.
Typical random 3-SAT formulae and the satisfiability threshold.
A lower bound for DLL algorithms for <i>k</i>-SAT (preliminary version).
On permutations with limited independence.
Min-Wise versus linear independence (extended abstract).
Hamiltonicity and colorings of arrangement graphs.
Testing and spot-checking of data streams (extended abstract).
Engineering the compression of massive tables: an experimental approach.
On the temporal HZY compression scheme.
Height in a digital search tree and the longest phrase of the Lempel-Ziv scheme.
Communication complexity of document exchange.
Scheduling a pipelined operator graph.
A PTAS for the multiple knapsack problem.
Approximation algorithms for data placement on parallel disks.
Movement minimization in conveyor flow shop processing.
Forcing relations for AND/OR precedence constraints.
The interlace polynomial: a new graph polynomial.
The complexity of counting graph homomorphisms (extended abstract).
A fast algorithm to generate unlabeled necklaces.
Construction of visual secret sharing schemes with almost optimal contrast.
Sharing one secret vs. sharing many secrets: tight bounds on the average improvement ratio.
Algorithmic strategies in combinatorial chemistry.
Computing the quartet distance between evolutionary trees.
A practical algorithm for recovering the best supported edges of an evolutionary tree (extended abstract).
Pattern discovery on character sets and real-valued data: linear bound on irredundant motifs and an efficient polynomial time algorithm.
Improved bounds on the sample complexity of learning.
On local search and placement of meters in networks.
Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs.
An approximation algorithm for the covering Steiner problem.
On the red-blue set cover problem.
Approximate congruence in nearly linear time.
Locally lifting the curse of dimensionality for nearest neighbor search (extended abstract).
Dimensionality reduction techniques for proximity problems.
Expected-case complexity of approximate nearest neighbor searching.
A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry.
Algorithms for optimizing production DNA sequencing.
Estimating DNA sequence entropy.
Selective mapping: a discrete optimization approach to selecting a population subset for use in a high-density genetic mapping project.
Cutting planes and the traveling salesman problem (abstract only).
Caching in networks (extended abstract).
Instability of FIFO in session-oriented networks.
The effects of temporary sessions on network performance.
Randomized greedy hot-potato routing.
On deciding stability of scheduling policies in queueing systems.
Restructuring ordered binary trees.
Faster deterministic dictionaries.
Competitive tree-structured dictionaries.
Even strongly universal hashing is pretty fast.
Word encoding tree connectivity works.
Algorithms for minimum volume enclosing simplex in R<sup>3</sup>.
Exact and approximation algorithms for minimum-width cylindrical shells.
Evaluating the cylindricity of a nominally cylindrical point set.
Approximation algorithms for layered manufacturing.
Approximation algorithms for projective clustering.
Scheduling to minimize average stretch without migration.
Minimizing maximum response time in scheduling broadcasts.
Applying extra-resource analysis to load balancing.
Balancing Steiner trees and shortest path trees online.
Generating adversaries for request-answer games.
Maintaining hierarchical graph views.
Improved classification via connectivity information.
Efficient dynamic traitor tracing.
Watermarking maps: hiding information in structured data.
Strictly non-blocking WDM cross-connects.
An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract).
A faster method for sampling independent sets.
Strong bias of group generators: an obstacle to the ``product replacement algorithm''.
Random three-dimensional tilings of Aztec octahedra and tetrahedra: an extension of domino tilings.
An algebraic method to compute a shortest path of local flips between two tilings.
Coloring powers of planar graphs.
Directed network design with orientation constraints.
A (2 + epsilon)-approximation scheme for minimum domination on circle graphs.
An approximation algorithm for finding a long path in Hamiltonian graphs.
TSP-based curve reconstruction in polynomial time.
A tree-edit-distance algorithm for comparing simple, closed shapes.
Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling.
Optimizing the sum of linear fractional functions and applications.
Edge-disjoint paths in expander graphs.
Escaping a grid by edge-disjoint paths.
Fast randomized algorithms for computing minimum {3, 4, 5, 6}-way cuts.
Adaptive set intersections, unions, and differences.
The whole genome assembly of Drosophila.
A 2+epsilon approximation algorithm for the <i>k</i>-MST problem.
The prize collecting Steiner tree problem: theory and practice.
Improved Steiner tree approximation in graphs.
The rectilinear Steiner arborescence problem is NP-complete.
Improved bandwidth approximation for trees.
Faster algorithms for string matching with <i>k</i> mismatches.
On the shared substring alignment problem.
Real scaled matching.
Inplace run-length 2d compressed search.
Pattern matching in dynamic texts.
Towards a theory of cache-efficient algorithms.
Efficient bundle sorting.
Fast concurrent access to parallel disks.
On external memory graph traversal.
Deterministic broadcasting in unknown radio networks.
New and improved algorithms for minsum shop scheduling.
Off-line admission control for general scheduling problems.
Approximating the maximum quadratic assignment problem.
Accurate approximations for Asian options.
Finite-resolution hidden surface removal.
On incremental rendering of silhouette maps of polyhedral scene.
Computing contour trees in all dimensions.
Sweeping simple polygons with a chain of guards.
Finding the closest lattice vector when it's unusually close.
A new bound for the Carath&eacute;odory rank of the bases of a matroid.
Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks.
Nearly optimal computations with structured matrices.
Beating the Logarithmic Lower Bound: Randomized Preemptive Disjoint Paths and Call Control Algorithms.
I/O-Efficient Dynamic Point Location in Monotone Planar Subdivisions.
Motion Planning of a Ball Amid Segments in Three Dimensions.
Page Replacement for General Caching Problems.
A New Way to Use Semidefinite Programming with Applications to Linear Equations mod <i>p</i>.
A Practical Clustering Algorithm for Static and Dynamic Information Organization.
Cooperative Sharing and Asynchronous Consensus Using Single-Reader Single-Writer Registers.
Using Homogenous Weights for Approximating the Partial Cover Problem.
A Lower Bound for Hellbronn's Triangle Problem in <i>d</i> Dimensions.
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions.
Fast, Fair, and Frugal Bandwidth Allocation in ATM Networks.
Kinetic Collision Detection Between Two Simple Polygons.
Locally Efficient On-Line Strategies for Routing Packets Along Fixed Paths.
Queries with Segments in Voronoi Diagrams.
Efficient Algorithms for Petersen's Matching Theorem.
Stop Minding Your p's and q's: A Simplified <i>O</i>(<i>n</i>) Planar Embedding Algorithm.
Fast Algorithms for Constructing Optimal Trees from Quartets.
A Small Universal Graph for Bounded-degree Planar Graphs.
A Near-Linear Area Bound for Drawing Binary Trees.
Greedy Local Improvement and Weighted Set Packing Approximation.
Minimizing Wirelength in Zero and Bounded Skew Clock Trees.
On Multi-Dimensional Packing Problems.
Nonplanar Topological Inference and Political-Map Graphs.
Approximate Minimum Weight Steiner Triangulation in Three Dimensions.
Two-Point Euclidean Shortest Path Queries in the Plane.
On the Parallel Time Complexity of Undirected Connectivity and Minimum Spanning Trees.
Dynamic LCA Queries on Trees.
Tree Pattern Matching and Subset Matching in Deterministic <i>O</i>(<i>n</i> log<sup>3</sup> <i>n</i>)-time.
Compact Routing with Minimum Stretch.
Recovering Evolutionary Trees Through Harmonic Greedy Triplets.
Delayed Path Coupling and Generating Random Permutations via Distributed Stochastic Processes.
On Approximability of the Minimum-Cost <i>k</i>-Connected Spanning Subgraph Problem.
Clustering in Large Graphs and Matrices.
Balanced Aspect Ratio Trees: Combining the Advantages of <i>k</i>-d Trees and Octrees.
Shortest Paths in an Arrangement with <i>k</i> Line Orientations.
Randomized Online Scheduling on Two Uniform Machines.
Separation-Sensitive Collision Detection for Convex Objects.
Simplicity and Hardness of the Maximum Traveling Salesman Problem Under Geometric Distances.
Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs.
How to Make a Square Grid Framework with Cables Rigid.
Two-Dimensional Gantt Charts and a Scheduling Algorithm of Lawler.
Cut Tree Algorithms.
The Complexity of Gene Placement.
Patience is a Virtue: The Effect of Slack on Competitiveness for Admission Control.
Estimating Interpolation Error: A Combinatorial Approach.
Fast Deterministic Construction of Static Dictionaries.
Parallel Integer Sorting is More Efficient than Parallel Comparison Sorting on Exclusive Write PRAMs.
New Algorithms for Generating Conway Polynomials Over Finite Fields.
Scheduling Multicasts on Unit-Capacity Trees and Meshes.
A 1.598 Approximation Algorithm for the Steiner Problem in Graphs.
A Small Approximately min-wise Independent Family of Hash Functions.
Geometric Matching Under Noise: Combinatorial Bounds and Algorithms.
An O(N) Oblivious Routing Algorithm for 2-D Meshes of Constant Queue-Size.
Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation.
A Primal-Dual Schema Based Approximation Algorithm for the Element Connectivity Problem.
Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks.
Eliminating Migration in Multi-Processor Scheduling.
On-line Complexity of Monotone Set Systems.
Parametric Polymatroid Optimization and Its Geometric Applications.
Optimal On-line Algorithms for an Electronic Commerce Money Distribution System.
Recovering Branches on the Tree of Life: An Approximation Algorithm.
The Data Broadcast Problem with Non-Uniform Transmission Rimes.
Interleaved Prefetching.
Wavelength Conversion in Optical Networks.
Online Resource Minimization.
Placement Algorithms for Hierarchical Cooperative Caching.
Indexing Schemes for Random Points.
Roundness Estimation via Random Sampling.
Cache Performance Analysis of Traversals and Random Accesses.
Trade-offs Between Speed and Processor in Hard-Deadline Scheduling.
Distinguishing String Selection Problems.
New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning.
Empirical Investigation of the Markov Reference Model.
A Deterministic Approximation Algorithm for a Minmax Integer Programming Problem.
An Analysis of the Burrows-Wheeler Transform.
Dual-Issue Scheduling with Spills for Binary Trees.
I/O-Complexity of Graph Algorithms.
All-to-All Optical Routing in Optimal Chordal Rings of Degree Four.
Combinatorial Approximation Algorithms for Generalized Flow Problems.
Certified Computation of the Sign of a Matrix Determinant.
Rendering Equation Revisited: How to Avoid Explicit Visibility Computations.
Approximation Algorithms for the Asymmetric Postman Problem.
On the Bidirected Cut Relaxation for the Metric Steiner Tree Problem.
An Efficient Algorithm for Generating Necklaces with Fixed Density.
Preemptive Scheduling with Job-Dependent Setup Times.
An Efficient Algorithm for Computing the <i>i</i>th letter of 4<sup>n</sup>a.
Median Bounds and Their Application.
Rectangular Tiling in Multi-dimensional Arrays.
A Generalization of Janson Inequalities and its Application to Finding Shortest Paths.
Approximation Algorithms for Bipartite and Non-Bipartite Matching in the Plane.
A New Property and a Faster Algorithm for Baseball Elimination.
When Does a Dynamic Programming Formulation Guarantee the Existence of an FPTAS?
Analysis of a Bounding Box Heuristic for Object Intersection.
Inverse Inbreeding Coefficient Problems with an Application to Linkage Analysis of Recessive Diseases in Inbred Populations.
Exploring Unknown Environments with Obstacles.
Playing Twenty Questions with a Procrastinator.
Improved Bicriteria Existence Theorems for Scheduling.
Group Signatures <i>&Aacute; la carte</i>.
Computing Morse Functions on Triangulated Manifolds.
Algorithms for Total Weighted Completion Time Scheduling.
Parameterized diff.
Finding Maximum Independent Sets in Sparse and General Graphs.
Optimal Multichannel Communication Under Failure.
A Wide-Range Efficient Algorithm for Minimal Triangulation.
Polygon-containment and Translational min-Hausdorff-Distance between segment Sets are 3SUM-hard.
The Full Degree Spanning Tree Problem.
Locked and Unlocked Polygonal Chains in 3D.
A Formal Treatment of Remotely Keyed Encryption.
Unscrambling Address Lines.
Some Graphic Uses of an Even Number of Odd Nodes.
Minimizing Weighted Completion Time on a Single Machine.
Improved Approximation Algorithms for a Capacitated Facility Location Problem.
Fluid Limits, Bin Packing, and Stochastic Analysis of Algorithms.
LP-based Analysis of Greedy-dual-size.
Scheduling Calls for Multicasting in Tree-Networks.
LBFS Orderings and Cocomparability Graphs.
Compact Roundtrip Routing for Digraphs.
Optimal Node-Degree Bounds for the Complexity of Nonplanarity Parameters.
Parallel Virtual Memory.
Folding and One Straight Cut Suffice.
A Simple Provable Algorithm for Curve Reconstruction.
Existence of Multiplicative Secret Sharing Schemes with Polynomial Share Expansion.
The 2-Catalog Segmentation Problem.
Incremental and Decremental Maintenance of Planar Width.
Checking Priority Queues.
Randomized Splay Trees.
Efficient Approximation Algorithms for the Hamming Center Problem.
Algorithms for Compile-Time Memory Optimization.
Synopsis Data Structures for Massive Data Sets.
Stability of Networks and Protocols in the Adversarial Queueing Model for Packet Routing.
Combinatorial Algorithms Test Sets [CATS]: The ACM/EATCS Platform for Experimental Research.
Reconstructing Set Partitions.
Online Coloring Known Graphs.
Dynamical System Representation of Open Address Hash Functions.
Efficient Exact Sampling from the Ising Model Using Swendsen-Wang.
Fully Dynamic Algorithms for Chordal Graphs.
The Phase Transition in Random Horn Satisfiability and Its Algorithmic Implications.
What are the Least Tractable Instances of max Tndependent Set?
A Generalized <i>q</i><sup>th</sup> Root Algorithm.
Computing Nearest Neighbors for Moving Points and Applications to Clustering.
Designing Proxies for Stock Market Indices is Computationally Hard.
Just the Fax - Differentiating Voice and Fax Phone Lines Using Call Billing Data.
A Uniform Framework for Approximating Weighted Connectivity Problems.
The Advantages of Forward Thinking in Generating Rooted and Free Trees.
An Algorithm to Symbolically Describe Flows on Surfaces.
On the Optimality of Parsing in Dynamic Dictionary Based Data Compression.
Approximation Algorithms for Protein Folding Prediction.
Compass Permits Leader Election.
Combinatorics Helps for Hexahedral Mesh Generation in CAD.
Approximating Multiroot 3-Outconnected Subgraphs.
Using Stopping Times to Bound Mixing Times.
Greedy Algorithms for Optimized DNA Sequencing.
Emulations Between QSM, BSP, and LogP: A Framework for General-Purpose Parallel Algorithm Design.
Sampling Spin Configurations of an Ising System.
Approximability of Scheduling with Fixed Jobs.
Optimal Scheduling of Multiclass Parallel Machines.
Colouring Graphs with Prescribed Induced Cycle Lengths.
An Oracle-Polynomial Time Augmentation Algorithm for Integer Programming.
Packet Filtering in High Speed Networks.
A Slique Size Bounding Technique with Application to Non-Linear Codes.
Lower Bounds for SRPT-Subsequence Algorithms for Nonpreemptive Scheduling.
A Convex Relaxation for the Asymmetric TSP.
Computational Complexity of Compaction to Cycles.
Exact Solutions to Large-scale Plane Steiner Tree Problems.
Faster Approximation Algorithms for Generalized Flow.
Experimental Performance of Shared RSA Modulus Generation.
Fast and Effective Stripification of Polygonal Surface Models.