Sampling from Discrete Distributions and Computing Frechet Distances

No abstract is available for this paper.

• Publication year

  2015

• Venue

  Bull. EATCS

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.22028/D291-25417
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Computational Geometry

  2018cited by this paper
• Parameterized complexity dichotomy for Steiner Multicut

  2014cited by this paper
• The Discrete Fréchet Distance with Shortcuts via Approximate Distance Counting and Selection

  2014cited by this paper
• Finding orthogonal vectors in discrete structures

  2014cited by this paper
• Internal DLA: Efficient Simulation of a Physical Growth Model - (Extended Abstract)

  2014influential reference
• Improved Approximation for Fréchet Distance on c-Packed Curves Matching Conditional Lower Bounds

  2014influential reference
• Two-dimensional subset selection for hypervolume and epsilon-indicator

  2014cited by this paper
• Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails

  2014cited by this paper
• Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems

  2014cited by this paper
• De-anonymization of Heterogeneous Random Graphs in Quasilinear Time

  2014cited by this paper
• Threesomes, Degenerates, and Love Triangles

  2014cited by this paper
• Generic Postprocessing via Subset Selection for Hypervolume and Epsilon-Indicator

  2014cited by this paper
• Parameterized average-case complexity of the hypervolume indicator

  2013cited by this paper
• Bringing Order to Special Cases of Klee's Measure Problem

  2013cited by this paper
• Exact Sublinear Binomial Sampling

  2013cited by this paper
• Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems

  2013cited by this paper
• Counting Triangulations Approximately

  2013cited by this paper
• Fréchet Queries in Geometric Trees

  2013cited by this paper
• Minimizing Maximum (Weighted) Flow-Time on Related and Unrelated Machines

  2013cited by this paper
• Succinct sampling from discrete distributions

  2013cited by this paper
• Exact and Efficient Generation of Geometric Random Variates and Random Graphs

  2013influential reference
• Online Checkpointing with Improved Worst-Case Guarantees

  2013cited by this paper
• A Simple Sweep Line Algorithm for Counting Triangulations and Pseudo-triangulations

  2013cited by this paper
• Approximation quality of the hypervolume indicator

  2013cited by this paper
• Balls into bins via local search: Cover time and maximum load

  2013cited by this paper
• Speeding up many-objective optimization by Monte Carlo approximations

  2013cited by this paper
• Fast approximation algorithms for the diameter and radius of sparse graphs

  2013cited by this paper
• Efficient Sampling Methods for Discrete Distributions

  2012cited by this paper
• Counting crossing-free structures

  2012cited by this paper
• Remarks on Category-Based Routing in Social Networks

  2012cited by this paper
• Efficient Generation ε-close to G(n,p) and Generalizations

  2012cited by this paper
• Computing the Discrete Fréchet Distance in Subquadratic Time

  2012cited by this paper
• An improved algorithm for Kleeʼs measure problem on fat boxes

  2012cited by this paper
• Convergence of hypervolume-based archiving algorithms ii: competitiveness

  2012cited by this paper
• Four Soviets Walk the Dog - with an Application to Alt's Conjecture

  2012cited by this paper
• The fréchet distance revisited and extended

  2012cited by this paper
• Are We There Yet? When to Stop a Markov Chain while Generating Random Graphs

  2012cited by this paper
• On Problems as Hard as CNF-SAT

  2011cited by this paper
• Approximate Map Matching with respect to the Fréchet Distance

  2011cited by this paper
• Lower bounds based on the Exponential Time Hypothesis

  2011cited by this paper
• Lower bounds on fluctuations for internal DLA

  2011cited by this paper
• Jaywalking Your Dog: Computing the Fréchet Distance with Shortcuts

  2011cited by this paper
• Convergence of hypervolume-based archiving algorithms I: effectiveness

  2011cited by this paper
• Fréchet distance with speed limits

  2011cited by this paper
• A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees

  2011cited by this paper
• Efficient Generation of Networks with Given Expected Degrees

  2011influential reference
• Approximation-Guided Evolutionary Multi-Objective Optimization

  2011cited by this paper
• The logarithmic hypervolume indicator

  2011cited by this paper
• The maximum hypervolume set yields near-optimal approximation

  2010cited by this paper
• Speed-constrained geodesic fréchet distance inside a simple polygon

  2010cited by this paper
• Cell-probe lower bounds for succinct partial sums

  2010cited by this paper
• Changing base without losing space

  2010cited by this paper
• Fast simulation of large‐scale growth models

  2010cited by this paper
• Approximating the Fréchet Distance for Realistic Curves in Near Linear Time

  2010influential reference
• On the possibility of faster SAT algorithms

  2010cited by this paper
• An Efficient Algorithm for Computing Hypervolume Contributions

  2010cited by this paper
• Tight Bounds for the Approximation Ratio of the Hypervolume Indicator

  2010cited by this paper
• On Space Efficient Two Dimensional Range Minimum Data Structures

  2010cited by this paper
• Klee's measure problem on fat boxes in time ∂(n(d+2)/3)

  2010cited by this paper
• Logarithmic fluctuations for internal DLA

  2010cited by this paper
• From logarithmic to subdiffusive polynomial fluctuations for internal DLA and related growth models

  2010cited by this paper
• Heterogeneous Subset Sampling

  2010cited by this paper
• Modern Computer Arithmetic (version 0.5.1)

  2010cited by this paper
• Random Walk: A Modern Introduction

  2010influential reference
• Concentration of Measure for the Analysis of Randomized Algorithms

  2009cited by this paper
• Hash, Displace, and Compress

  2009cited by this paper
• Don't be greedy when calculating hypervolume contributions

  2009cited by this paper
• Exact algorithms for partial curve matching via the Fréchet distance

  2009cited by this paper
• On Buffon machines and numbers

  2009cited by this paper
• The Computational Geometry of Comparing Shapes

  2009cited by this paper
• Worst-Case Upper Bounds

  2009cited by this paper
• Fast integer multiplication using modular arithmetic

  2008cited by this paper
• Walking your dog in the woods in polynomial time

  2008cited by this paper
• Universally utility-maximizing privacy mechanisms

  2008cited by this paper
• On the Redundancy of Succinct Data Structures

  2008cited by this paper
• Approximating the least hypervolume contributor: NP-hard in general, but fast in practice

  2008cited by this paper
• INTERNAL DIFFUSION-LIMITED AGGREGATION ON NON-AMENABLE GRAPHS

  2008cited by this paper
• Geodesic Fréchet distance inside a simple polygon

  2008cited by this paper
• Approximating the volume of unions and intersections of high-dimensional geometric objects

  2008cited by this paper
• Detecting Commuting Patterns by Clustering Subtrajectories

  2008cited by this paper
• Exploring Network Structure, Dynamics, and Function using NetworkX

  2008cited by this paper
• A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array

  2007cited by this paper
• Can We Compute the Similarity between Surfaces?

  2007cited by this paper
• Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets

  2007cited by this paper
• Faster integer multiplication

  2007cited by this paper
• How Difficult is it to Walk the Dog ?

  2007cited by this paper
• A duality between clause width and clause density for SAT

  2006cited by this paper
• Optimal lower bounds for rank and select indexes

  2006cited by this paper
• Fréchet Distance for Curves, Revisited

  2006cited by this paper
• On a conditionally Poissonian graph process

  2006cited by this paper
• Efficient generation of large random networks.

  2005cited by this paper
• Networks and epidemic models

  2005cited by this paper
• A new algorithm for optimal 2-constraint satisfaction and its implications

  2005influential reference
• On Map-Matching Vehicle Tracking Data

  2005cited by this paper
• A study of drift analysis for estimating computation time of evolutionary algorithms

  2004cited by this paper
• Comparison of Distance Measures for Planar Curves

  2003cited by this paper
• Fast simulation of new coins from old

  2003cited by this paper
• Generating Random Regular Graphs

  2003cited by this paper
• Network motifs: simple building blocks of complex networks.

  2002cited by this paper
• Approximate nearest neighbor algorithms for Frechet distance via product metrics

  2002cited by this paper

• Tight(er) bounds for similarity measures, smoothed approximation and broadcasting

  2016cites this paper
• 1 Sampling from Discrete Distributions

  2015cites this paper