Goal Time consuming How to reduce the time complexity? Basic Algorithm
Goal 16 How to reduce the time complexity? Enumerate possible insertion pairs in 𝑂(𝑛 2 ) Calculate objective and check constraints in 𝑂(𝑛) Time Complexity:𝑂(𝑛 3 ) Time consuming Basic Algorithm
Outline ● Background o Problem statement o Partition-based framework e Segment-based dp algorithm ● Experiments o Conclusion
Outline ⚫ Background ⚫ Problem Statement ⚫ Partition-based Framework ⚫ Segment-based DP Algorithm ⚫ Experiments ⚫ Conclusion 17
18 Partition-based Framework Time complexity: on) Time complexity: O(n2) Calculate objective and Calculate objective and check constraints in 0(1) check constraints in O(n) Enumerate all possible insertion pairs in o(n) Enumerate possible insertion pairs in o(n2) Pre-processing in o(n2) Basic Algorithm Partition-based framework
Partition-based Framework 18 Calculate objective and check constraints in 𝑂(1) Pre-processing in 𝑂(𝑛 2 ) Enumerate all possible insertion pairs in 𝑂(𝑛 2 ) Time complexity:𝑂(𝑛 2 ) Enumerate possible insertion pairs in 𝑂(𝑛 2 ) Calculate objective and check constraints in 𝑂(𝑛) Time complexity:𝑂(𝑛 3 ) Basic Algorithm Partition-based Framework × ＋ × = =
19 Insertion(i,) insertion(i,) route SR: detour +1 insert Or/ after li insert d,/ after l
Insertion(𝒊,𝒋) 19 insertion(𝑖,𝑗) insert 𝑜𝑟 ′ after 𝑙𝑖 insert 𝑑𝑟 ′ after 𝑙𝑗
Partition-based Framework ● Basic idea o Partition the set of requests rt into four parts o R1: requests delivered before i-th location o R2: requests delivered between i-th and j-th location o R3 requests delivered after j-th location o R4: new request r Objective calculation o OBJ(Sr+)=maxmfi, mf2, mf3, mfa] mfi: the maximum flow time m of all requests in R1 route SR detour R R2 R m R
Partition-based Framework ⚫ Basic idea： ⚫ Partition the set of requests 𝑅 + into four parts o 𝑅1: requests delivered before 𝑖-𝑡ℎ location o 𝑅2: requests delivered between 𝑖-𝑡ℎ and 𝑗-𝑡ℎ location o 𝑅3: requests delivered after 𝑗-𝑡ℎ location o 𝑅4: new request 𝑟′ ⚫ Objective calculation: o OBJ 𝑆𝑅 + = max{𝑚𝑓1, 𝑚𝑓2, 𝑚𝑓3, 𝑚𝑓4} 20 𝑚𝑓1: the maximum flow time of all requests in 𝑅1 𝑚𝑓2 𝑚𝑓3 𝑚𝑓4