Lecturer Lap, Chi Lau, Scribe Chun, Kong Yung, Xin Sui
In the previous lectures we have seen how linear programming provide a systematic way of obtaining a good lower bound on the optimal value (for minimization problem), for numerous NP-hard problems....
Lecturer Lap, Chi Lau, Scribe Li Xu, Jianing Chen, Junpu Cai
In this lecture, we study network design problems, where the goal is to find a good subgraph (e.g. low cost, low maximum degree, etc) satisfying given connectivity requirements (e.g. reliability,...
Lecturer Lap, Chi Lau, Scribe Josh Borts, Guiming Qin, Lin Yang, Shannon Capacity
In communication, we usually encode our messages using the letters in a particular alphabet for transmission in some kind of channels. However, with the presence of noise in the channel, it might be...
Lecturer Lap, Chi Lau, Scribe Wei Wei, Haiqin Yang
In this lecture, we study the topic of Job Scheduling. The problem of job scheduling is that if we have n jobs and m machines and we have a processing time pij of each machine i for each job j, the...
Lecturer Lap, Chi Lau, Scribe Zhaorong Li, Xuan Yang
In this lecture, the focus is on primal dual method and its application in designing exact algorithms and approximation algorithms for combinatorial optimization problems. It is a general framework...
Lecturer Lap, Chi Lau, Scribe Yingze Wang, Wei Zhang
This lecture gives a general introduction of graph partitioning problems. We will begin with the definitions of some classic graph partitioning problems (e.g. multiway cut, multicut, sparsest cut),...
Lecturer Lap, Chi Lau, Scribe Leung, Ka Lun, Cheung Siu Ming
In this lecture, we proved that the bipartite matching and the stable matching problems can be solved using linear programming in polynomial time. We first relaxed the integral constraint to give a...
Lecturer Lap, Chi Lau, Scribe Wei Zhang, Wujie Zheng
In previous chapters we have seen the definition of a constant factor approximation algorithm. In this chapter, we will introduce the notion of a polynomial time approximation scheme (PTAS), which...
Lecturer Lap, Chi Lau, Scribe Yuk, Hei Chan, Ling Ding, Xiaobing Wu
In this lecture, the focus is on general perfect matching problem where the goal is to prove that it can be solved in polynomial time by linear programming. Based on the LP formulation for bipartite...
Lecturer Lap, Chi Lau, Scribe Shi Xingang, Jia Lu
In this lecture, the focus is on LP duality, where the goal is to show that we can obtain min-max theorems for linear programming, which means the min of a primal problem equals the max of its dual...
Lecturer Lap, Chi Lau, Scribe Lam, Chi Ho
In this lecture, we focus on the Maximum Flow problem, which is to send as much data as possible from a source to a destination through a network. This problem is polynomial time solvable, and is the...
11.1 Bipartite Perfect Matching 11.1.1 Problem Formulation (2008)
Lecturer Lap, Chi Lau, Scribe Xiao Linfu, Li Liang
In Lecture 10, we have used the “shifting ” technique to show that basic solutions are integral. In this lecture, we will introduce another technique, the “rank ” argument, to analyze the...
Lecturer Lap, Chi Lau, Scribe Jennifer, X. M. Wu
In this lecture, we discuss matchings in general graph. Following the same structure of bipartite matching, we first introduce the min-max theorem for general matching. Then we present Edmonds’...
Lecturer Lap, Chi Lau, Scribe Qian Wang, Yongzhi Wang
In this lecture, we show the applications of the strong duality theorem, and discuss how to obtain min-max theorems and combinatorial algorithms from linear programming. We first introduce the 2...
Lecturer Lap, Chi Lau, Scribe Jerry, Jilin Le
This lecture gives a general introduction of P, NP and NP-complete problems. We will study the definition and some classic examples of NP-complete problems (e.g. SAT, 3-SAT, Vertex Cover). More...
Lecturer Lap, Chi Lau, Scribe Sean, X. Peng, Yingyi Bu
In this lecture, the focus is on submodular function in combinatorial optimizations. The first class of submodular functions which was studied thoroughly was the class of matroid rank functions. The...
Lecturer Lap, Chi Lau, Scribe Qian Zaichen, Fung Ching Johnny
Starting from this lecture, the focus is on NP-hard optimization problems, where the goal is to find approximation algorithms for NP-hard problems. There are other alternatives to deal with NP-hard...
Lecturer Lap, Chi Lau, Scribe Shu, Tong Tse, Tony Wing, Hong Wong
In this lecture, we will talk about the technique of using Linear Programming (LP) to solve combinatorial optimization problems. The lecture is divided into two parts. In the first part, we discuss...