Lecture 5: Scheduling & Exponential L.P.

  Topics covered: Scheduling, Project, Exponential L.P. and Randomized Rounding 1. Weighted Non Preemptive Scheduling on Single Machine (S3) 1.1. L.P. of S3 Variables: Let $latex C_i$ be the completion time of $latex i^{th}$ job with release date $latex r_i$, processing time $latex p_i$ and weight $latex w_i$ where $latex i \in [n]$ Objective:  $latex …

Lecture 3: Relaxation & IP Formulation

Topics Covered 1. IP/LP formulation 2. Relaxation 3. Projects Question (Previous Lecture) How do we justify the relationship between the integer program and the linear program given a maximization problem? Assume X is an IP such that $latex x_i \in \{0,1\} $, OPT(X) be value of optimal solution. Let Y be a linear program of …

Lecture 4: Scheduling Problems

Non preemptive Scheduling Problem (S1) Given $latex n$ jobs with processing times $latex p_j$ and release dates $latex r_j$, our goal is to schedule these jobs on a single machine such that only one job can be processed at each time, no job can be scheduled before its release date and all jobs must be …

HomeWork 3 – Deadline 28th Feb 2018

 In Task Scheduling Problem we studied in class you are given processing times $latex p_i,$ release dates $latex r_i$ and goal is to design non-preemptive schedule that minimises the sum of completion times. Give an algorithm to solve this problem when $latex r_i = 0$. Prove that Earliest finish time first (EFTF) algorithm to solve Pre-emptive …

Topics for Class on Feb 20/21

Hello Everyone, This week we plan to discuss LP formulation of optimization problems - we will also discuss deterministic rounding on LP solution. You should read through Chapter 4 of Williamsons book. Class timings remain same for now - Zeenat will update us regarding the new location of the class, hopefully somewhere on 6th floor. …

HomeWork2 – Deadline 20th Feb 2018

Find Integer Programming Formulations for the following problems(look up online if you need to know the definition of the problem): (a) Weighted Set Cover Problem (b) 0/1 Knapsack Problem (c) Non-preemptive scheduling with release dates and processing times on a single machine Model the following Happy Graph Problem into an integer program: Given a graph G, …

Lecture 2. Solving Vertex Cover using LP

Today we will discuss two approximation algorithms for vertex cover problem which is a well-known np-hard problem. Using linear programming, we will see two simple algorithms which will give 1-approximation and 2-approximation ratios for this problem. Before starting the vertex cover problem, let's revise some basic concepts including Convex Set, Graph, NP, NP-complete and NP-hard …

Course Outline and Grading Policy

Hi Folks ! Welcome to the Approximation Algorithm Class taught by Dr. Mudassir Shabbir. This course is intended towards a potential research body in the theory of computer science. This is an advanced course in theory so you must already be versed with discrete math, graphs, algorithms, and probability theory. The basic tentative list of topics to …

Lecture 1 – Introduction

1. P vs NP Question P : Class of problems solvable in polynomial time. NP(Non-deterministic Polynomial) : Class of problems for which a "Yes" instance can be "verified" in polynomial time. Instance is a particular input/formula and yes instance means the answer of decision problem is Yes. What is a certificate? Let's say there are …

Bonus Problem Solution:

You can put your bonus problem 1 solution in the comments to this post. The bonus problem is as below: Report an NP-Hard problem P and a corresponding approximation algorithm that is implemented in a research paper in last $latex 15$ years.