Search this site
Embedded Files
  • Home
  • Teaching
  • Publications
  • Extras
 
  • Home
  • Teaching
  • Publications
  • Extras
  • More
    • Home
    • Teaching
    • Publications
    • Extras

Books:

  1. [WS]The Design of Approximation Algorithms by David Williamson and David Shmoys, Cambridge University Press, 2011.        https://www.designofapproxalgs.com/book.pdf

  2. [VV]Approximation Algorithms by Vijay Vazirani, Springer-Verlag, 2004. https://www.ics.uci.edu/~vazirani/book.pdf 


 My lecture notes

 INTRODUCTION 

Greedy Paradigm

GREEDY-MINIMUM VERTEX COVER

GREEDY-MAXIMUM K-COVERAGE

GREEDY-MINIMUM SET COVERAGE

GREEDY-2 factor TSP

CHRISTOFIDES 3/2-FACTOR for TSP

INAPPROXIMABILITY for GENERAL TSP

GREEDY-METRIC STEINER TREE  

APPROXIMATION PRESERVING REDUCTION FOR GENERAL STEINER TREE

GREEDY-K CENTER PROBLEM and INAPPROXIMABILITY OF K CENTER

GREEDY-MINIMIZING MAKESPAN 

BIN PACKING

Local Search Paradigm

LOCAL SEARCH-MAXCUT

LOCAL SEARCH-MINIMIZING MAKESPAN 

Scaling and Rounding

0/1 KNAPSACK

APTAS: Bin Packing 

Random Sampling

MAXCUT

MAXSAT, MAXE3SAT

Linear Programming Paradigm

VERTEX COVER LP

LP-Duality

SETCOVER LP

RANDOMIZED ROUNDING MAX SAT  

RANDOMIZED ROUNDING MIN SET COVER

RANDOMIZED ROUNDING MAX INDEPENDENT SET

COMPLEMENTARY SLACKNESS

PRIMAL DUAL - VERTEX COVER and SET COVER

PRIMAL DUAL - STEINER FOREST

PRIMAL DUAl - PRIZE COLLECTING VERTEX COVER


 ....

Google Sites
Report abuse
Google Sites
Report abuse