4810-1183: Approximation and Online Algorithms with Applications
Lecture Note 1: Course Overview, Optimization Models, Linear Programming
What do we aim at this class?
During many undergraduate courses in CS, students have a chance to join several “application-orientedcourses” such as communication networks, databases, OS, or machine learnings. On the other hand,students have a chance to learn several theoretical CS concepts such as computational complexity,hardness, and data structures. However, for some of the students, the “application-oriented courses”
and the theoretical CS concepts might look totally separated as they are in totally different worlds.
At the graduate level, we expect students to produce cutting-edge research results by merging
everything they have learnt. However, the merging is not very easy as things are taught separately.
Because of that, in this class, I will guide you to the beginning of the merging. I will raise a lotof problems in the application-oriented courses, and will show you how to solve it using theoretical CS
concepts. As some of you have not learnt enough theoretical CS concepts during the undergraduate
courses, I will try to give some more theoretical backgrounds, in particular on the hardness,
approximation algorithms, and online algorithms. For those who have already learnt the concepts, they
will be your reminders.
How to solve a problem in IST?
There are many patterns to solve problems in information science and technology. The pattern in thepicture below is one of the most common patterns.

In my opinion, the most important and the hardest step of the whole flowchart is the first step.
You have to transform what you have into some mathematical formulas with the clear goal here. Thatis not easy to do, and is more art than science. During this course, you will learn this skill by a lot ofexamples.
Step 2 is when you try to solve your mathematical model using several algorithmic toolboxes
you have learnt during undergraduate courses, such as divide and conquer, dynamic programming, orlinear programming. Because we believe that most of IST problems “cannot be solved”, we would liketo skip this step in this course.
When you want to claim that a problem cannot be solved, there is a way to state that formally,called as “NP-Hardness”. To make everyone believe that a problem cannot be solved, people usually
try to prove that the problem is NP-hard. That is Step 3, which we will discuss on next week.
There are several ways to cope with a problem that cannot be solved. One of the mostconventional ways is to use approximation algorithms (Step 4), which is the main focus of this course.
Approximation algorithms can solve almost all problems, but there are cases where we cannot
find any approximation algorithm for our problems. It is possible to claim that no one can do thatformally. That would be done in Step 5. If no approximation algorithm can solve our problems, we may
try to get back to Step 1 and reformulate the problem there.
What is online algorithm?
Another main topic of this class is online algorithm, where you have to produce some “output” while
you have not got a whole input. The most well-known problem is called as “secretary problem”. We
want to have just one secretary, and we have a number of applications for the job. We interview all
applicants, but, just after each interview, we have to tell the applicants immediately if they are hired. If
we hire one secretary, we cannot fire him/her. So, we cannot interview more applicants, although there
might be some with a better capability.
Those kind of questions happen a lot in IST, and we will try to address those problems in thiscourse.
Optimization Models
Now, it is the time to work on the first step in our flow chart. We have a problem in IST and we wantto solve the problem using some theoretical CS concepts. To kick start a whole process, we have toanswer the following 4 questions:
1)
2)
3)
4)

What do we have in real world? What are important for our problem? [input]
What do we want to have? [output]
What the output can be, what it cannot be? [constraint]
What is the most desirable output? [objective function]

After we have some answers for the 4 questions, we have to transform them into some mathematicalformulations. Then, we can devise theoretical tools for those mathematical formulations.
Let us try to illustrate you how it works by a toy example (which is unfortunately not an ISTproblem). Consider the following problems:

We can eat only Gyu-don and Melon-pan
Gyu-don and Melon-pan contain different amounts of carbohydrates and proteins

This is what you have in real world. It is your task to find the “best” way to consume Gyu-don andMelon-pan. We can formulize them by more than one ways, but let try to minimize our cost of living.
To do that, we might formulize:
Input: We can look in Google to find how much carbohydrates and proteins that Gyu-don and Melonpan give. Also, we can look there how much carbohydrates and proteins we should take every day. We
can go to some places to check the price of Gyu-don and Melon-pan.
Output: We want to find how much Gyu-don and Melon-pan we should eat in each day.
Constraint: We want to have enough proteins and carbohydrates in every day.
Objective Function: We want to find the amounts that minimize the cost we have to pay in each day.
After we have some rough ideas of our optimization models, we will now formulate it into somemathematical formulations. One way to do is as follows:
Carbohydrate amount that a Gyu-don gives 𝑎𝑐,𝑔 ∈ ℝ≥0

Input:

Carbohydrate amount that a Melon-pan gives 𝑎𝑐,𝑚 ∈ ℝ≥0
Protein amount that a Gyu-don gives 𝑎𝑝,𝑔 ∈ ℝ≥0
Protein amount that a Melon-pan gives 𝑎𝑝,𝑚 ∈ ℝ≥0
Amount of carbohydrate that we should have per day 𝑏𝑐 ∈ ℝ≥0
Amount of protein that we should have per day 𝑏𝑝 ∈ ℝ≥0
Price of a Gyu-don 𝑐𝑔 ∈ ℝ≥0
Price of a Melon-pan 𝑐𝑚 ∈ ℝ≥0
Amount of Gyu-don we take in one day 𝑥𝑔 ∈ ℝ≥0Output:

Amount of Melon-pan we take in one day 𝑥𝑚 ∈ ℝ≥0Constraint:

𝑎𝑐,𝑔 𝑥𝑔 + 𝑎𝑐,𝑚 𝑥𝑚 ≥ 𝑏𝑐
𝑎𝑝,𝑔 𝑥𝑔 + 𝑎𝑝,𝑚 𝑥𝑝 ≥ 𝑏𝑝

Objective Function:

Minimize 𝑐𝑔 𝑥𝑔 + 𝑐𝑚 𝑥𝑚

We can leave only mathematical details without losing any information.
Input:

𝑎𝑐,𝑔 , 𝑎𝑐,𝑚 , 𝑎𝑝,𝑔 , 𝑎𝑝,𝑚 , 𝑏𝑐 , 𝑏𝑝 , 𝑐𝑔 , 𝑐𝑚 ∈ ℝ≥0

Output:𝑥𝑔 , 𝑥𝑚 ∈ ℝ≥0

Constraint:

𝑎𝑐,𝑔 𝑥𝑔 + 𝑎𝑐,𝑚 𝑥𝑚 ≥ 𝑏𝑐
𝑎𝑝,𝑔 𝑥𝑔 + 𝑎𝑝,𝑚 𝑥𝑝 ≥ 𝑏𝑝

Objective Function:

Minimize 𝑐𝑔 𝑥𝑔 + 𝑐𝑚 𝑥𝑚

The above is what we will call as “optimization model” in this course. When we can arrive to something
in this form, we are ready to take off. We can apply several algorithmic and theoretical techniques tosolve the problem. As most of you can guess, we can use a technique called as “linear programming”
to solve the problem.

Linear Programming (LP)
LP is a very powerful algorithmic toolbox. In fact, it is shown that “LP can solve all problems that canbe solved [1]”. The formulation is in the following form:
Input:

Matrix A, vectors 𝐛, 𝐜

Output:Vector 𝐱Constraint:𝐀⋅𝐱≥ 𝐛

Objective Function:

Minimize 𝐜 T ⋅ 𝐱

It is known that we can use a method called “the interior-point method” to solve LP [2]. However, aheuristic algorithm, called as “simplex method”, although cannot solve LP for some inputs, is known
to be faster in practice. There are a lot of libraries developed to solve LPs. In my experiments, CPLEX®,
developed by IBM, is one of the fastest libraries.
Let us get back to our previous example. We can reformulate the “Gyu-don & Melon-pan problem” tothe following:
Input:𝑎𝑐,𝑔
𝐀 = [𝑎Output:𝑥𝑔
𝐱 = [𝑥 ]Constraint:𝐀⋅𝐱≥ 𝐛

Objective Function:

Minimize 𝐜 𝑇 ⋅ 𝐱𝑝,𝑔𝑎𝑐,𝑚𝑐𝑔𝑏𝑐,𝐛=,𝐜=][][𝑎𝑝,𝑚𝑐𝑚 ]𝑏𝑝𝑚After the reformulation, it is clear that we can use LP algorithm to solve the problem. This course will
give you examples how problems are reformulated. We hope that we will get the skill by taking thiscourse.
What do I mean by “solve”?
Suppose that the size of our input file is 𝑛 bits. In this course, we will say that “we can solve an
optimization model” if we can find an “algorithm of which the running time is no more than apolynomial function of 𝑛”. We will call such kind of algorithms as “polynomial-time algorithm” during
this course.
The polynomial-time algorithms do not always “solve” problems in practice. Consider the case when
the running time is somewhere around 𝑛1000, which is still a polynomial function of 𝑛. The running
time we need for 10-bit input is 101000 , which is more than the number of atoms in the world. However,in our experience, when one can find an algorithm with the 𝑛1000 running time, we usually can reduce
the running time to 𝑛5 or 𝑛6 .
In the last few years, when we are in big data era, the input size 𝑛 becomes very large. The number issometimes even larger than 1012 . When we have such a large input, we cannot even scan everything
we have there. The algorithm with running time = 𝑛 is not acceptable anymore, and we have to find analgorithm with even smaller running time.
Because of that, in big data era, we have to find an alternative definition for “solve”. Those theories arestill young and we still have a lot to explore. We will sometimes mention them during this course.

I also want to mention that big data is an opportunity for online algorithms. Because we cannot scan awhole input, we have to output the best things we “learn” from the partial information. Online
algorithms can do that, so it is fit to the setting.
Exercises
At international center for information science and technology, we have a mission to make allcommunications between students possible. Unfortunately, there is still a language barrier between
students. Let a language ability of Student 1 and Student 2 be ℓ1 and ℓ2 respectively. By a research result,
we found that a communication between them will happen when ℓ1 + ℓ2 is no smaller than a given
integer 𝛼 ≥ 1. We know the current language ability of all students. We increase the language ability ofstudents so that all pairs of students can communicate together. However, increasing students’ language
ability is not free. If we increase a cost of a student from ℓ to ℓ′, it will cost us 10000 ⋅ (ℓ ′ − ℓ) yen. We
want to minimize our cost.
Question 1: Suppose that we have 3 students. The language abilities of Student 1, 2, 3 are 2, 3, 1
respectively, and 𝛼 is 5. Which students should we improve their language ability? And, how muchshould we improve?
Question 2: What is the optimization model for solving Question 1?
Question 3: Construct a linear program to solve the optimization model in Question 2.
Hand-on exercises
CPLEX® is free only for academics and installing it is not a very easy task. The easiest way to use thepackage software is to use the online tool at https://neos-server.org/neos/solvers/milp:CPLEX/LP.html.
Load a file with the following text to the file box “LP file” at the “Web submission form”.
Maximizex1 + 2x2 + 3x3
st-x1 + x2 + x3 <= 20x1 - 3x2 + x3 <= 30x1 <= 40
end

Question 4: Which LP we are aiming to solve by the above text file? What is matrix A, vectors b,c inthis case. What are inputs, outputs, constraints, and objective functions here?
Also, load a file with the following text to the file box “Display file” at the “Web submission form”.
The command tells CPLEX to give the value of x1, x2, and x3 that satisfy the constraint and optimize
the objective function.
display solution variables -You have to put your e-mail address here. This is to notify you the results in case that it takes a longtime to solve the linear program and your web browser terminates before the solver finishes. I havenever received a spam mail from this website.
Question 5: What is the value of x1, x2, and x3 that satisfy the constraint and optimize the objectivefunction? What do you have from the solver?
Question 6: Create an LP file to solve the “Gyu-don Melon-pan problem” when 𝑎𝑐,𝑔 = 30, 𝑎𝑐,𝑚 =50, 𝑎𝑝,𝑔 = 40, 𝑎𝑝,𝑚 = 60, 𝑏𝑐 = 200, 𝑏𝑝 = 200, 𝑐𝑔 = 300, 𝑐𝑚 = 500. What is the solution that you
have from LP?

Question 7: Discuss why the solution in Question 6 is not practical.
References[1] S. Miyano, S. Shiraishi, and T. Shoudai, “A List of P-Complete Problems”, Kyushu University,
RIFIS-TR-CS-17, 1990.
[2] N. Karmarkar, "A new polynomial-time algorithm for linear programming", Combinatorica, Vol. 4,No. 4. Pages 373-395. 1984.