Algorithms Seminar - Spring 2002

Recommended papers include:

• Approximation algorithms:
  • Metric labeling via metric embeddings into trees [Kleinberg Tardos].
    
  • Directed multicut [Cheriyan Karloff Rabani].
    
  • Directed Steiner tree [Charikar Chekuri Cheung Dai Goel Guha Li].
  • Multiway cuts [Calinescu Karloff Rabani].
    
  • Rapidly mixing markov chains [Jerrum Sinclair].
  
  
• Algorithmic Finance:
  • Worst Case Equilibria [Koutsoupias Papadimitriou].
    
  • On the Complexity of Equiliria [Deng et. al.].
    
  • Approximating Nash Equilibrium [Kearns et. al.].
    
  • Online Algorithms for Market Clearing [Blum et. al.].
  
  
• Online Algorithms:
  • On Randomized Online Scheduling [Albers].
    
  • Entropy Characterization of Online Algorithms [Pandurangan Upfal].
  • Static optimality for Search Trees [Blum et. al.].
  
  
• Combinatorial Optimization:
  • Polynomial Time Algorithm for LP/CP via Random Walks [Bertsimas Vempala].
    
  • Fast Approximate Mixed Packing and Covering [Young].
  
  
• Algorithmic issues in Networks:
  • Web Generation Models [Fabrikant et. al.].
    
  • Optimization for Congestion Control [Karp et. al.].
  
  
• Data Mining:
  • Spectral Analysis of Data [Fiat et. al.].
  
  Other suggestions ? -- let me know.