Our research
Content type
+
Downloads (441)
+
Events (396)
 
Groups (150)
+
News (2592)
 
People (804)
 
Projects (1066)
+
Publications (12006)
-
Videos (5238)
Labs
Research areas
Algorithms and theory47205 (58)
Communication and collaboration47188 (57)
Computational linguistics47189 (8)
Computational sciences47190 (69)
Computer systems and networking47191 (111)
Computer vision208594 (17)
Data mining and data management208595 (7)
Economics and computation47192 (24)
Education47193 (81)
Gaming47194 (21)
Graphics and multimedia47195 (62)
Hardware and devices47196 (62)
Health and well-being47197 (28)
Human-computer interaction47198 (146)
Machine learning and intelligence47200 (80)
Mobile computing208596 (9)
Quantum computing208597 (16)
Search, information retrieval, and knowledge management47199 (61)
Security and privacy47202 (24)
Social media208598 (5)
Social sciences47203 (37)
Software development, programming principles, tools, and languages47204 (31)
Speech recognition, synthesis, and dialog systems208599 (5)
Technology for emerging markets208600 (2)
1–18 of 18
Sort
Show 25 | 50 | 100
1
Video details
Date: 17 December 2012
Duration: 01:25:39
Collection: MSR India Winter School 2012
R. Ravi
How to Approximate it? Introduction and Greedy Algorithms - Part 1The lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.
Video details
Date: 17 December 2012
Duration: 01:36:20
Collection: MSR India Winter School 2012
R. Ravi
Greedy Algorithms - Part 2The lecture starts with an outline of the topics proposed to be covered, followed by an introduction to greedy algorithms illustrated using the set cover problem (logarithmic ratio approximation). The homework assigned was to analyze the greedy method applied to Uncapacitated Facility Location, and the Generalized Steiner Forest problems.
Video details
Date: 18 December 2012
Duration: 00:44:49
Collection: MSR India Winter School 2012
Video details
Date: 18 December 2012
Duration: 01:41:05
Collection: MSR India Winter School 2012
Video details
Date: 18 December 2012
Duration: 01:28:03
Collection: MSR India Winter School 2012
Video details
Date: 18 December 2012
Duration: 01:37:33
Collection: MSR India Winter School 2012
Video details
Date: 19 December 2012
Duration: 00:57:07
Collection: MSR India Winter School 2012
R. Ravi
Local SearchThe Local Search method was illustrated using three problems: Maximum cut (2-approximation), Maximum leaf spanning trees (10-approximation) and the metric k-median problem (3-approximation).
Video details
Date: 19 December 2012
Duration: 01:38:19
Collection: MSR India Winter School 2012
Video details
Date: 19 December 2012
Duration: 01:22:34
Collection: MSR India Winter School 2012
Video details
Date: 19 December 2012
Duration: 01:33:12
Collection: MSR India Winter School 2012
R. Ravi
Linear Programs and Deterministic RoundingLinear and integer programs were introduced and simple deterministic rounding was demonstrated for the vertex cover problem (2-approximation). The homework assigned was to design a deterministic rounding algorithm for the prize-collecting vertex cover problem.
Video details
Date: 20 December 2012
Duration: 01:32:07
Collection: MSR India Winter School 2012
Video details
Date: 20 December 2012
Duration: 01:31:38
Collection: MSR India Winter School 2012
Video details
Date: 20 December 2012
Duration: 01:36:28
Collection: MSR India Winter School 2012
R. Ravi
Filtering and the Primal-Dual Method - Part 1Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.
Video details
Date: 21 December 2012
Duration: 01:03:44
Collection: MSR India Winter School 2012
R. Ravi
Filtering and the Primal-Dual Method - Part 2Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.
Video details
Date: 21 December 2012
Duration: 01:38:08
Collection: MSR India Winter School 2012
Video details
Date: 21 December 2012
Duration: 01:01:19
Collection: MSR India Winter School 2012
R. Ravi
Metric Rounding of LP RelaxationsLP relaxations interpreted as metrics (or distance functions in graphs) are useful in designing approximation algorithms for cut problems. This was illustrated by designing an exact algorithm for minimum s-t cut, a 2-approximation for multiway cut in graphs, a 2-approximation for the multicut problem in trees and finally a logarithmic approximation for the multicut problem in general graphs.
Video details
Date: 21 December 2012
Duration: 01:40:32
Collection: MSR India Winter School 2012
Video details
Date: 22 December 2012
Duration: 01:29:01
Collection: MSR India Winter School 2012
1–18 of 18
Sort
Show 25 | 50 | 100
1
> Our research