prof: Hamid, call by name
exam: oral
NP (nondeterministic polynomial time) - problems that are conputationaly expencive
NP-hard refers to a class of problems that are at least as hard as the hardest problems in NP. These problems may not have efficient solutions, and solving them efficiently would also solve all NP problems.
Approximation solution needs to be:
Analysis of online algorithms is called competitive analysis.
Adversarial model - we assume that the input is chosen by an adversary, and we need to find a solution that is as good as possible. Adversary is a person that is trying to make our life harder and knows our algorithm.
Optimal online algorithm - algorithm that is the best online algorithm for a given problem and given sequence of requests. Competitive ratio of the best online algorithm is considered an lower bound and upper bound.
| what | offline | online |
|---|---|---|
| example | traveling salesman | |
| input | u have all input at the begining | classic: requests come one by one, so we need to return solution before next request |
| dynamic input: next request can arive even before the previous one has been served |
In two cities are EMSes, we need to choose where from to send the ambulance to the patience imidiatly after the call.
Solution: move each ambulance to the caller, first one to arrive will be the one that will serve the call. Second one does not go back to the station, but waits for the next call.
We have only one EMS in two cities. We can not answer imidiatly, but we need to pay waiting time for the ambulance. Need to minimize waiting cost and movement.
Solution: do not move until the cost of delay is the same as cost of moving.
Offline optimization problem (P) - 4 - tuple ( I, Sol, C, type )
Alg - aproximation algorithm for P - computes fizible solution for P belonging to Sol. Alg(I) = c(I, Sol(I)) - cost of the solution.
OPT - optimal offline solution, can be not unique.
cost OPT(I) = min(c(I, Sol(I))) - cost of the optimal solution
ALG is a r-approximation algorithm with const alpha >= 0 if for all i in I if ALF(I) <= r * OPT(I) + alpha
__r is just some multiplier, alpha is a constant.__
if we say that r is approximation factor for ALG that means that we took some minimal r from set of all possible r for ALG. infimum over all possible r for ALG.
Infimum - 2 for (2; 100]
Online optimization problem (P) = tuple( R, Sig, A, C )
A deterministic online algorithm ALG
ALF[I] : (a1, a2, ... an) - sequence of answers for requests belongin to An
fi: Ri -> A
ai = fi(I <= i) - answer for request i
cost ALG(I) = c(Ii, ALG[i])
ALGi(I) - cost of the algorithm for the ith request
ALG(I) = ALG(I OPT[I] = argmin(Cn(I, a')); a' is in An ALG is r-competitive algorithm for all I in Sig if ALG (I) <= r * OPT(I) + alpha
where r is a constant and alpha >= 0 if alpha = 0, r is __strict__ The competitive ratio of problem P is the infimum of all r for all I in Sig.