tag

#approximation

28 pages tagged

Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.9 MinHash

19.9 MinHash Many large-scale systems need to compare sets. Search engines compare documents. Recommendation systems compare user interests. Security systems compare malware signatures. Data integration pipelines compare records from different sources. The obvious approach is to compute the exact similarity between every pair of sets. Unfortunately, exact comparison becomes expensive as datasets grow. A search index may contain billions of documents. A recommendation platform may store billions of user interactions....
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.5 Random Sampling

19.5 Random Sampling Random sampling is one of the most powerful techniques in algorithm design. Instead of processing an entire dataset, we examine a carefully selected subset and use it to estimate properties of the whole. When designed correctly, a sample can provide surprisingly accurate answers while requiring only a fraction of the computation, memory, and storage needed by exact algorithms. The idea appears throughout computer science. Database systems estimate...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.16 Set Cover Approximation

19.16 Set Cover Approximation Set Cover is the canonical greedy approximation problem. It is easy to describe, appears in many practical systems, and has a clean logarithmic approximation guarantee. If you understand Set Cover, you understand the basic shape of many approximation algorithms: choose the best local move, compare that move to what an optimal solution must accomplish, and accumulate a global bound. The problem is computationally hard in general,...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.7 Skip Lists Revisited

19.7 Skip Lists Revisited Balanced search trees achieve logarithmic performance by carefully maintaining structural invariants. AVL trees perform rotations to preserve height balance. Red-black trees maintain coloring rules. B-trees redistribute keys across nodes. These structures provide excellent asymptotic guarantees, but the implementation complexity can be substantial. Skip lists take a different approach. Instead of maintaining strict balance through deterministic rules, they use randomness. A skip list is essentially a hierarchy...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.13 Locality-Sensitive Hashing

19.13 Locality-Sensitive Hashing Many applications need to find similar items inside very large collections. Search engines look for near-duplicate documents. Recommendation systems search for users with similar preferences. Image retrieval systems search for visually similar images. Fraud detection systems search for related transactions. The obvious solution is to compare every item against every other item. Unfortunately, this approach scales poorly. A collection containing one million objects requires roughly: 500 billion...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.20 Streaming Algorithms

19.20 Streaming Algorithms Streaming algorithms process data one item at a time while using much less memory than the input size. They are designed for systems where the stream is too large to store, too fast to revisit, or too distributed to collect in one place. A streaming algorithm usually sees each element once. It updates a compact state and discards the raw item. Later, queries are answered from that...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.24 Randomized Algorithms in Practice

19.24 Randomized Algorithms in Practice Theoretical analysis explains why randomized algorithms work. Production systems reveal why they matter. Many randomized algorithms were originally developed to solve mathematical problems. Over time, they became essential engineering tools. Search engines use sketches to summarize web traffic. Databases use probabilistic structures to avoid unnecessary I/O. Distributed systems use randomness to coordinate millions of machines. Machine learning systems rely on random sampling and stochastic optimization...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.6 Shuffling

19.6 Shuffling Shuffling converts an ordered collection into a uniformly random permutation. This is a small operation with large consequences. A correct shuffle removes input order bias, supports randomized experiments, prepares data for training, randomizes work distribution, and provides a foundation for many randomized algorithms. The central requirement is uniformity. For an array with n distinct elements, there are n! possible permutations. A correct shuffle must make every permutation equally...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.2 Las Vegas Algorithms

19.2 Las Vegas Algorithms A randomized algorithm can use randomness in several ways. Some algorithms use random choices to improve performance while guaranteeing that every answer produced is correct. Others use random choices to reduce running time while accepting a small probability of error. The first category is known as Las Vegas algorithms. A Las Vegas algorithm always returns a correct result. Randomness affects the amount of work performed, not...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.23 Derandomization

19.23 Derandomization Randomized algorithms are often easier to design and analyze than deterministic algorithms. A random pivot simplifies quicksort. Randomized rounding simplifies approximation algorithms. Random sampling simplifies large-scale data analysis. A natural question follows: If randomness helps so much, can we remove it? Surprisingly, the answer is often yes. Derandomization is the process of transforming a randomized algorithm into a deterministic one while preserving most or all of its guarantees....
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.4 Randomized Quicksort

19.4 Randomized Quicksort Randomized quicksort is one of the most successful applications of randomization in algorithm design. It combines the elegance and practical efficiency of quicksort with probabilistic guarantees that eliminate dependence on particular input arrangements. The resulting algorithm is simple, fast, cache-friendly, and widely used in production systems. Classical quicksort already performs extremely well on average. Its weakness lies in pivot selection. Poor pivot choices produce highly unbalanced partitions,...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.10 HyperLogLog

19.10 HyperLogLog HyperLogLog estimates the number of distinct elements in a stream using a small, fixed amount of memory. This problem appears constantly in large systems: distinct users, distinct IP addresses, distinct search queries, distinct URLs, distinct products viewed, distinct errors, distinct devices, and distinct sessions. The exact solution is straightforward: store every distinct value in a set and return the size of the set. That works for small inputs....
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.1 Random Variables in Algorithms

19.1 Random Variables in Algorithms Randomized algorithms differ from deterministic algorithms because their behavior depends on random choices made during execution. A deterministic algorithm always follows the same sequence of operations for a given input. A randomized algorithm may produce different execution paths, different running times, or even different outputs when executed multiple times on the same input. To analyze such algorithms rigorously, we need a mathematical framework that describes...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.17 Randomized Rounding

19.17 Randomized Rounding Many optimization problems can be expressed as integer programs. Variables represent decisions, constraints describe feasibility requirements, and an objective function measures solution quality. Unfortunately, integer programs are often computationally difficult to solve exactly. A common strategy is to relax the problem. Instead of requiring variables to be integers, allow them to take fractional values. The resulting linear program can usually be solved efficiently. The challenge then becomes...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook ›

Chapter 19. Randomized and Approximate Algorithms

Chapter 19. Randomized and Approximate Algorithms
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.22 Probability Bounds

19.22 Probability Bounds Randomized algorithms rarely stop at computing an expected value. An expected value tells us what happens on average, but it does not say how often the algorithm deviates from that average. For production systems, that missing information matters. If a randomized algorithm has expected runtime: O(n log n) we may still ask: How likely is a much slower run? If a sketch estimates frequency with expected error:...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.15 Greedy Approximation

19.15 Greedy Approximation Many approximation algorithms are built around a simple principle: make the best local decision available at each step. This strategy is known as the greedy approach. Greedy algorithms are attractive because they are usually easy to understand, simple to implement, and computationally efficient. For some problems, greedy choices produce optimal solutions. For others, they do not. Even when optimality is impossible, however, a carefully designed greedy strategy...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.11 Bloom Filters Revisited

19.11 Bloom Filters Revisited A Bloom filter is one of the most widely deployed probabilistic data structures in modern computing. It answers a simple question: Have I seen this item before? The answer is not exact. A Bloom filter may occasionally report that an item is present when it is not. It never reports that a previously inserted item is absent. This asymmetry makes Bloom filters useful in systems where...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.8 Hashing with Randomness

19.8 Hashing with Randomness Hash tables are usually presented as deterministic data structures: compute a hash, reduce it to a table index, and store or retrieve the key. In practice, randomness is often part of the design. A randomized hash function can reduce collision patterns, defend against adversarial inputs, and provide strong expected-time guarantees without relying on accidental properties of the input. The main issue is collisions. A hash table...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.25 Choosing the Right Randomized Technique

19.25 Choosing the Right Randomized Technique Randomized algorithms span a wide range of techniques. Some improve runtime. Some reduce memory usage. Some provide approximate answers. Some help systems make decisions under uncertainty. Others simplify algorithm design or avoid adversarial inputs. A common challenge for practitioners is not understanding an individual algorithm. The challenge is knowing which randomized technique applies to a particular problem. This final section serves as a practical...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.14 Approximation Ratios

19.14 Approximation Ratios Some optimization problems are easy to state and hard to solve exactly. We may want the smallest set of servers that covers all regions, the cheapest route visiting every city, the best subset of ads under a budget, or the minimum number of machines needed to schedule jobs. For many such problems, exact algorithms are too expensive for large inputs. Approximation algorithms address this situation directly. Instead...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.12 Count-Min Sketch Revisited

19.12 Count-Min Sketch Revisited A Count-Min Sketch estimates item frequencies in a stream using fixed memory. It answers questions such as: How many times has this key appeared? The answer is approximate. Unlike a hash map, a Count-Min Sketch does not store every key. It stores counters arranged in a small table and updates several counters for each observed item. The key property is one-sided error. A Count-Min Sketch never...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.21 The Power of Randomization

19.21 The Power of Randomization Throughout this chapter, we have encountered a recurring theme: A small amount of randomness can dramatically simplify a difficult problem. Randomization appears in sorting, graph algorithms, approximation algorithms, streaming systems, sketching structures, online decision-making, and distributed computing. Sometimes randomness improves performance. Sometimes it simplifies implementation. Sometimes it makes a problem tractable that would otherwise be infeasible. This concluding section examines the broader principles behind randomized...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.19 Online Algorithms

19.19 Online Algorithms Most algorithms assume complete knowledge of the input before computation begins. Sorting algorithms see the entire array. Graph algorithms receive the complete graph. Dynamic programming algorithms assume all problem data is available from the start. Many real systems do not operate this way. A web server receives requests one at a time. A scheduler receives jobs continuously. A network router sees packets as they arrive. A cloud...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.3 Monte Carlo Algorithms

19.3 Monte Carlo Algorithms Las Vegas algorithms always return correct answers and use randomness to influence resource consumption. Monte Carlo algorithms take the opposite approach. They place strict bounds on resource usage and allow a small probability of error. This trade-off has become increasingly important in modern computing. Large-scale search systems, distributed databases, streaming analytics engines, machine learning pipelines, and cryptographic protocols frequently process data volumes that make exact computation...
algorithms randomized approximation Jun 1, 2026
Programming › Algorithm Cookbook › Chapter 19. Randomized and Approximate Algorithms ›

19.18 Primal-Dual Approximation

19.18 Primal-Dual Approximation Primal-dual approximation algorithms use linear programming structure to design fast approximate solutions. The method starts from an optimization problem, writes a linear-programming relaxation, examines its dual, and then builds a solution while maintaining information about both sides. The central idea is simple: the dual solution gives a bound on the optimum. If the algorithm constructs a feasible primal solution whose cost is at most some factor times...
algorithms randomized approximation Jun 1, 2026
Maths › 00. General Mathematics ›

09.3 Exact vs Approximate Computation

9.3 Exact vs Approximate Computation Not all computations are the same. Some problems ask for an exact answer, while others accept an approximation. Understanding the difference is important, because it affects how we design algorithms and how we interpret results. Exact computation An exact computation produces a result with no error. The answer is precise and fully correct within the rules of mathematics. For example, adding two integers is exact:...
mathematics computation approximation numerical methods May 2, 2026
Maths ›

41. Approximations and Expansions

This volume studies approximation of functions and data by simpler objects such as polynomials, splines, and rational functions. It develops both theoretical bounds and computational methods. Part I. Foundations of Approximation Chapter 1. Approximation Problems 1.1 Function approximation setup 1.2 Norms and error measures 1.3 Best approximation 1.4 Existence and uniqueness 1.5 Examples Chapter 2. Normed Function Spaces 2.1 Metric and normed spaces 2.2 Uniform norm 2.3 Lp norms 2.4...
analysis approximation May 2, 2026