O
O Mi
g I
T’t
it I234
iii
the TiffTt
Ti f z This is a 2
T
approximation
it
2 ti
i
tmt
tight
Ti
Else
ft’t 5T
ti
as
approximation
z2
aoe.a.TT
0
o
FIE
O
aetrinate
fright 3 hand
rectory unknown squffin
00
e
i
O
o
Instant
i
I
ni
init
Ni
is a decision variable for eachnode i
is ieS
i.e
I wit ni
t
m
integerprogramming
Minimize
FE
e
mIka i
00
MeO IFS
ni’t a Say
i EE
eS k
lieu niE
Say S W
approx So l
is on Sf2
WEI wep swCs
WSf2 2
wks approximation
0
our variables
dull day
shortestdistancefrom veV S to V is da foreach
andda i
t dots
d dcutw de
objective function
freak edge
a
v.v
v.v
EE
II
maximise Midtt
Discussion 12
1. The bin packing problem is as follows. You have an infinite supply of bins, each of which can hold M maximum weight. You also have n objects, each of which has a (possibly distinct) weight wi (any given wi is at most M). Our goal is to partition the objects into bins, such that no bin holds more than M total weight, and that we use as few bins as possible. This problem in general is NP-hard.
Give a 2-approximation to the bin packing problem. That is, give an algorithm that will compute a valid partitioning of objects into bins, such that no bin holds more than M weight, and our algorithm uses at most twice as many bins as the optimal solution. Prove that the approximation ratio of your algorithm is two.
2. Suppose you are given a set of positive integers A: a1 a2 … an and a positive integer B. A subset S A is called feasible if the sum of the numbers in S does not exceed B.
The sum of the numbers in S will be called the total sum of S. You would like to select a feasible subset S of A whose total sum is as large as possible.
Example: If A = {8, 2, 4} and B = 11 then the optimal solution is the subset S = {8, 2}.
Give a linear-time algorithm for this problem that finds a feasible set S A whose total sum is at
least half as large as the maximum total sum of any feasible set S’ A. Prove that your algorithm achieves this guarantee.
You may assume that each ai < B.
3. A cargo plane can carry a maximum weight of 100 tons and a maximum volume of 60 cubic meters. There are three materials to be transported, and the cargo company may choose to carry any amount of each, up to the maximum available limits given below.
Material 1 has density 2 tons/cubic meter, maximum available amount 40 cubic meters, and revenue $1,000 per cubic meter.
Material 2 has density 1 ton/cubic meter, maximum available amount 30 cubic meters, and revenue $1,200 per cubic meter.
Material 3 has density 3 tons/cubic meter, maximum available amount 20 cubic meters, and revenue $12,000 per cubic meter.
Write a linear program that optimizes revenue within the constraints. You do not need to solve the linear program.
4. Recall the 0/1 knapsack problem:
Input: n items, where item i has profit pi and weight wi, and knapsack size is W.
Output: A subset of the items that maximizes profit such that the total weight of the set ≤ W.
You may also assume that all pi 0, and 0 < wi ≤ W.
We have created the following greedy approximation algorithm for 0/1 knapsack: Sort items according to decreasing pi/wi (breaking ties arbitrarily).
While we can add more items to the knapsack, pick items in this order.
Show that this approximation algorithm has no nonzero constant approximation ratio.
In other words, if the value of the optimal solution is P*, prove that there is no constant (1 > > 0), where we can guarantee our greedy algorithm to achieve an approximate solution with total profit P*.
EET
UH
First FitDecreqsing
e
HEES
t
i22approa
2
valveofopt so
b
Itis Ti
variables willrepresent materialrowmen M Mz M3 volumes ofmat’s 1,2 3
objective function
GO
Maximize subjectto M
1,000 M 1,200Mzt14000Mz
M e Mat 3 S
2M t OfM
13Mz S G
Mz OfMz G 30
O
3
20
100 40
Ii
m
sont first find media
in
oCn
OG
b are
t
O 0
Tr O
Ln dht si
n
n Oca
Tcn
X
Algorithms Twogeneral typesofrandomization
1
natureofinput
relies on random Algorithm behaves randomly
Algorithm 2
Two types ofResults
f Some randomizedalgorithms alwaysproduce
incorrect solutions but we try to bound theprobabilityofsuchan incorrecstolution
correctresults the runtime
Randomization onlyaffects 2 Somerandomizedalgorithmsmayproduce
E
0
J
aabe f O
aEBEggqzfE
Biff
I tE.EESE
I
o
oe
Geez
Core algorithmicTechniques Greedy
Divide
Dynamic Programming
Conquer Brute force
Algorithms can also beclassified as Exact vs Approximate
Deterministic
vs
Non learning vs
Offline
Randomized Online
Learning lmachinelearningDeepLearning
vs
Otherfieldsgroupings withinalgorithmdesign
Graph algorithms Numericalmethods algorithms
Computationagl eometry algorithms
algorithms
Cryptography
sub fields within Sciences
Computational
Chemistry
c a
Biology Neuroscience
physics
Industries
on developmentof algorithms
Automotive
Aerospace Healthcare
Defense Energy
Typesofalgorithms basedon computers used
new
relying
Conventional
sequential vs parallel
computers
shared vs Distributedmemory
Quantum Computers
DNA Computers 9