Combinatorial Optimization: Exact and Approximate Algorithms

Lecture notes from the class CS261: Optimization and Algorithmic Paradigms taught at Stanford. They cover topics in approximation algorithms, exact optimization, and online algorithms.

**Publication date**: 11 Mar 2011

**ISBN-10**:
n/a

**ISBN-13**:
n/a

**Paperback**:
139 pages

**Views**: 9,433

**Type**: Lecture Notes

**Publisher**:
n/a

**License**:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported

**Post time**: 23 Oct 2016 03:00:00

Combinatorial Optimization: Exact and Approximate Algorithms

Lecture notes from the class CS261: Optimization and Algorithmic Paradigms taught at Stanford. They cover topics in approximation algorithms, exact optimization, and online algorithms.

You are free to:

Share — copy and redistribute the material in any medium or format

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click**here** to read the full license.

Share — copy and redistribute the material in any medium or format

The licensor cannot revoke these freedoms as long as you follow the license terms.

Click

Note:

More resources are available at the course webpage.

From the Introduction:

More resources are available at the course webpage.

From the Introduction:

Trevisan wrote:In this course we study algorithms for combinatorial optimization problems. Those are the type of algorithms that arise in countless applications, from billion-dollar operations to everyday computing task; they are used by airline companies to schedule and price their flights, by large companies to decide what and where to stock in their warehouses, by delivery companies to decide the routes of their delivery trucks, by Netflix to decide which movies to recommend you, by a gps navigator to come up with driving directions and by word-processors to decide where to introduce blank spaces to justify (align on both sides) a paragraph.

In this course we will focus on general and powerful algorithmic techniques, and we will apply them, for the most part, to highly idealized model problems.

Some of the problems that we will study, along with several problems arising in practice, are NP-hard, and so it is unlikely that we can design exact efficient algorithms for them. For such problems, we will study algorithms that are worst-case efficient, but that output solutions that can be sub-optimal. We will be able, however, to prove worst-case bounds to the ratio between the cost of optimal solutions and the cost of the solutions provided by our algorithms. Sub-optimal algorithms with provable guarantees about the quality of their output solutions are called approximation algorithms.

Tweet

About The Author(s)

Professor of Electrical Engineering and Computer Science at U.C. Berkeley and senior scientist at the Simons Institute for the Theory of Computing. Studied at the Sapienza University of Rome, advised by Pierluigi Crescenzi. Took a post-doc at MIT (with the Theory of Computing Group) and at DIMACS, joined as an assistant professor at Columbia University and a professor at Stanford. Interested in Theoretical Computer Science.

Book Categories

Computer Science
Introduction to Computer Science
Introduction to Computer Programming
Algorithms and Data Structures
Artificial Intelligence
Computer Vision
Machine Learning
Neural Networks
Game Development and Multimedia
Data Communication and Networks
Coding Theory
Computer Security
Information Security
Cryptography
Information Theory
Computer Organization and Architecture
Operating Systems
Image Processing
Parallel Computing
Concurrent Programming
Relational Database
Document-oriented Database
Data Mining
Big Data
Data Science
Digital Libraries
Compiler Design and Construction
Functional Programming
Logic Programming
Object Oriented Programming
Formal Methods
Software Engineering
Agile Software Development
Information Systems
Geographic Information System (GIS)

Mathematics
Mathematics
Algebra
Abstract Algebra
Linear Algebra
Number Theory
Numerical Methods
Precalculus
Calculus
Differential Equations
Category Theory
Proofs
Discrete Mathematics
Theory of Computation
Graph Theory
Real Analysis
Complex Analysis
Probability
Statistics
Game Theory
Queueing Theory
Operations Research
Computer Aided Mathematics

Supporting Fields
Web Design and Development
Mobile App Design and Development
System Administration
Cloud Computing
Electric Circuits
Embedded System
Signal Processing
Integration and Automation
Network Science
Project Management

Operating System
Programming/Scripting
Ada
Assembly
C / C++
Common Lisp
Forth
Java
JavaScript
Lua
Rexx
Microsoft .NET
Perl
PHP
R
Python
Rebol
Ruby
Scheme
Tcl/Tk

Miscellaneous
Sponsors