Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Approximation algorithm

Related lectures (29)

Theory of Computation Laboratory 2: Resource Allocation and Network Design

Explores approximation algorithms for resource allocation and network design problems, competitive algorithms for the TCP acknowledgment problem, and experimental results.

Approximation Algorithms

Covers approximation algorithms for optimization problems, LP relaxation, and randomized rounding techniques.

Constraint Satisfaction: Formulation and Algorithms

Covers the formulation of constraint satisfaction problems and systematic algorithms for solving them efficiently.

Variational Method

Covers the variational method and its applications in solving mathematical problems.

Optimization and Simulation

Explores greedy heuristics in optimization, integrality constraints, and comparison of optimization methods.

Theory of Computation: Undecidable Problems

Explores the existence of functions that cannot be computed, illustrated by famous paradoxes and the concept of undecidable problems.

Taylor Series: Basics

Covers Taylor series, polynomial approximations for function behavior, coefficient finding, and error estimation.

Numerical Analysis: Quadrature Formulas

Explores the theory and application of quadrature formulas for numerical analysis.

Submodular Maximization

Covers submodular function maximization using the greedy algorithm and its approximation guarantee.

Numerical Methods: Runge-Kutta Approximation

Covers the Runge-Kutta method for approximating solutions of differential equations.

Nonlinear Truss System Analysis

Explores nonlinear truss system analysis, covering force-displacement responses, event-to-event principles, and solution algorithms.

Knapsack Problem: Optimization and Traveling Salesman

Explores the knapsack problem and the traveling salesman problem with a focus on optimization algorithms.

Laplacian Solvers

Explores Laplacian solvers, covering approximate solutions, applications, error conversion, and theoretical advancements in computational methods.

Traveling Salesman Problem: Introduction and Approximation Methods

Introduces the Traveling Salesman Problem and explores approximation methods using Markov chains.

Interpolation: Applications and Techniques

Explores interpolation applications in biological tissue and population census data analysis using the method of least squares.

Polynomial Approximation: Orthonormal Basis and Projection

Explores polynomial approximation with orthonormal bases and orthogonal projection methods.

FPTAS for Knapsack Log in to Mediaspace to watch this video

Introduces the FPTAS for the Knapsack problem, focusing on achieving an approximation of (1-ε) times the optimal solution.

Integer Optimization: Theory and Applications Log in to Mediaspace to watch this video

Covers the fundamentals of integer optimization, including integer programming, dynamic programming, and approximation algorithms.

Sparsest Subgraph: Densest Subgraph Log in to Mediaspace to watch this video

Covers Sparsest Subgraph and Densest Subgraph, focusing on correlation clustering and approximation algorithms.

Data Streams: Algorithms and Applications Log in to Mediaspace to watch this video

Covers data streams, sub-linear memory computation, document similarity, and randomized dimension reduction techniques for handling 'Big Data' challenges efficiently.