CS计算机代考程序代写 algorithm Local Search Paradigm

Local Search Paradigm
2021-03-31 CSC373 Winter 2021 – Sam Toueg 1

Local Search
• A heuristic paradigm for solving complex problems
• Idea:
Ø Start with some solution 𝑆
Ø While there is a better solution 𝑆′ in the local neighborhood of 𝑆
switch to 𝑆′
• Need to define:
Ø what is “better”, and
Ø what is a “local neighborhood”
2021-03-31 CSC373 Winter 2021 – Sam Toueg 2

Local Search
• Sometimes local search gives an optimal solution • We already saw such an example: network flow
Ø Start with zero flow
Ø “Local neighborhood”
o Set of all flows which can be obtained by augmenting the current flow along a path in the residual graph
Ø“Better”
o Higher flow value
2021-03-31 CSC373 Winter 2021 – Sam Toueg 3

Local Search
• But sometimes it doesn’t return an optimal solution, and “gets stuck” in a local maxima
2021-03-31 CSC373 Winter 2021 – Sam Toueg 4

Local Search
• In that case, we want to bound the ratio between: (a) the optimal solution, and
(b) the worst solution that local search might return
Worst ratio
2021-03-31 CSC373 Winter 2021 – Sam Toueg 5

Max-Cut
2021-03-31 CSC373 Winter 2021 – Sam Toueg 6

Max-Cut
• Problem
Ø Input: An undirected graph 𝐺 = (𝑉, 𝐸)
Ø Output: A partition (𝐴, 𝐵) of 𝑉 that maximizes the number of edges going across the (𝐴, 𝐵) cut, i.e., maximizes|𝐸!|where𝐸! = 𝑢,𝑣 ∈𝐸 𝑢∈𝐴,𝑣∈𝐵}
𝐴
𝐵
Example of (𝐴, 𝐵) with fewer cross edgesJ
5 edges across cut (𝐴, 𝐵)
Find partition with max # of
2021-03-31
CSC373 Winter 2021 – Sam Toueg 8
cross edges

Max-Cut
• Problem
Ø Input: An undirected graph 𝐺 = (𝑉, 𝐸)
Ø Output: A partition (𝐴, 𝐵) of 𝑉 that maximizes the number of edges going across the (𝐴, 𝐵) cut, i.e., maximizes|𝐸!|where𝐸! = 𝑢,𝑣 ∈𝐸 𝑢∈𝐴,𝑣∈𝐵}
Ø This is known to be an NP-hard problem
Ø What is a natural local search algorithm for this problem?
o Given a current partition, what small change to the partition you can do to try to improve the objective value
(i.e., to increase the number of edges that cross the partition)?
Ø Let’s see an example…
2021-03-31 CSC373 Winter 2021 – Sam Toueg 9

2021-03-31 CSC373 Winter 2021 – Sam Toueg 10

Say the current (A,B) partition is:
𝐴
𝐵
2021-03-31
CSC373 Winter 2021 – Sam Toueg 11

Say the current (A,B) partition is:
𝐴
𝐵
6 edges across cut (𝐴, 𝐵)
2021-03-31
CSC373 Winter 2021 – Sam Toueg 12

Say the current (A,B) partition is:
𝐴
𝐵
𝑢
6 edges across cut (𝐴, 𝐵) Node 𝑢 of 𝐵 has
• •
2 cross edges
3 edges within 𝐵
2021-03-31
CSC373 Winter 2021 – Sam Toueg
13

Say the current (A,B) partition is:
𝐴
𝐵
𝑢
6 edges across cut (𝐴, 𝐵) Node 𝑢 of 𝐵 has
•
•
2 cross edges
3 edges within 𝐵
2021-03-31
CSC373 Winter 2021 – Sam Toueg
14

Say the current (A,B) partition is:
𝐴
𝐵
𝑢
6 edges across cut (𝐴, 𝐵) Node 𝑢 of 𝐵 has
• •
2 cross edges
3 edges within 𝐵
2021-03-31
CSC373 Winter 2021 – Sam Toueg
15

Say the current (A,B) partition is:
𝐴
𝐵
𝑢
6 edges across cut (𝐴, 𝐵)
Node 𝑢 of 𝐵 has
• 2 cross edges
• 3 edges within 𝐵
So: moving 𝑢 to 𝐴 increases number of cross edges (by 1)
2021-03-31
CSC373 Winter 2021 – Sam Toueg 16

𝐴
𝐵
𝑢
6 edges across cut (𝐴, 𝐵)
Node 𝑢 of 𝐵 has
• 2 cross edges
• 3 edges within 𝐵
So: moving 𝑢 to 𝐴 increases number of cross edges (by 1)
2021-03-31
CSC373 Winter 2021 – Sam Toueg 17

𝐴
𝐵
7 edges across cut (𝐴, 𝐵)
Node 𝑢 of 𝐵 has
• 2 cross edges
• 3 edges within 𝐵
So: moving 𝑢 to 𝐴 increases number of cross edges (by 1)
𝑢
2021-03-31
CSC373 Winter 2021 – Sam Toueg
18

𝐴
𝐵
7 edges across cut (𝐴, 𝐵)
Node 𝑢 of 𝐵 has
• 2 cross edges
• 3 edges within 𝐵
So: moving 𝑢 to 𝐴 increases number of cross edges (by 1)
𝑢
2021-03-31
CSC373 Winter 2021 – Sam Toueg
19

𝐴
𝐵
7 edges across cut (𝐴, 𝐵)
Node 𝑢 of 𝐵 has
• 2 cross edges
• 3 edges within 𝐵
So: moving 𝑢 to 𝐴 increases number of cross edges (by 1)
Node 𝑣 of 𝐴 has
• 1 cross edges
• 3 edges within 𝐴
So: moving 𝑣 to 𝐵 increases number of cross edges (by 2)
𝑣
2021-03-31
CSC373 Winter 2021 – Sam Toueg 20

𝐴
𝐵
9 edges across cut (𝐴, 𝐵)
Node 𝑢 of 𝐵 has
• 2 cross edges
• 3 edges within 𝐵
So: moving 𝑢 to 𝐴 increases number of cross edges (by 1)
Node 𝑣 of 𝐴 has
• 1 cross edges
• 3 edges within 𝐴
So: moving 𝑣 to 𝐵 increases number of cross edges (by 2)
𝑣
2021-03-31
CSC373 Winter 2021 – Sam Toueg 21

Node 𝑟 of 𝐵 has
• 1 cross edges
• 2 edges within 𝐵
So: moving 𝑟 to A increases number of cross edges (by 1)
𝐴
𝐵
𝑟
9 edges across cut (𝐴, 𝐵)
Node 𝑢 of 𝐵 has
• 2 cross edges
• 3 edges within 𝐵
So: moving 𝑢 to 𝐴 increases number of cross edges (by 1)
Node 𝑣 of 𝐴 has
• 1 cross edges
• 3 edges within 𝐴
So: moving 𝑣 to 𝐵 increases number of cross edges (by 2)
2021-03-31
CSC373 Winter 2021 – Sam Toueg
23

𝐴
𝑟
𝐵
10 edges across cut (𝐴, 𝐵)
Node 𝑢 of 𝐵 has
• 2 cross edges
• 3 edges within 𝐵
So: moving 𝑢 to 𝐴 increases number of cross edges (by 1)
Node 𝑣 of 𝐴 has
• 1 cross edges
• 3 edges within 𝐴
So: moving 𝑣 to 𝐵 increases number of cross edges (by 2)
Node 𝑟 of 𝐵 has
• 1 cross edges
• 2 edges within 𝐵
So: moving 𝑟 to A increases number of cross edges (by 1)
2021-03-31
CSC373 Winter 2021 – Sam Toueg 24

Max-Cut
• Local Search Algorithm
Ø Initialize (𝐴, 𝐵) arbitrarily
Ø While there is a vertex 𝑢 such that moving 𝑢 to the other side increases the number of edges across the cut:
o Move 𝑢 to the other side
Ø Moving 𝑢, say from 𝐴 to 𝐵, increases the number of
edges across the cut iff:
𝑢 has more incident edges going within its side of the cut
than across the cut
2021-03-31 CSC373 Winter 2021 – Sam Toueg 26

Max-Cut
• Local Search Algorithm
Ø Initialize (𝐴, 𝐵) arbitrarily
Ø While there is a vertex 𝑢 such that moving 𝑢 to the other side increases the number of edges across the cut:
o Move 𝑢 to the other side
Ø Why does this algorithm stop?
oEvery iteration increases the number of edges across the cut by at least 1,
oso the algorithm must stop in at most |𝐸| iterations
2021-03-31 CSC373 Winter 2021 – Sam Toueg 27

Max-Cut
• Local Search Algorithm
Ø Initialize (𝐴, 𝐵) arbitrarily
Ø While there is a vertex 𝑢 such that moving 𝑢 to the other side increases the number of edges across the cut:
o Move 𝑢 to the other side
Ø Approximation ratio (vs. optimal)?
o At the end of this algorithm, every vertex has at least as many edges going across the cut as within the cut
o As will prove next, this implies that at the end of the algorithm: at least half of all the edges in the graph go across the cut
o No Max-Cut algo can find a cut with more cross edges than
all edgesJ, so this local search algo is a 2-approximate solution!
2021-03-31 CSC373 Winter 2021 – Sam Toueg 28

Max-Cut
Claim: At the end of the algorithm, at least half of all edges go across the cut
Proof: Let (𝐴, 𝐵) be the cut found by the algo Ø Let 𝐸% be the set of edges that cross (𝐴, 𝐵) Ø Let 𝐸 be the set of all edges ØWewanttoshow: 𝐸% ≥ 𝐸 /2
Ø For each node 𝑣, de/ine:
o 𝐸!: edges incident to 𝑣
o 𝐸!”: edges incident to 𝑣 that cross the cut
o 𝐸!# : edges incident to 𝑣 that do not cross the cut Ø 𝐸 & = 𝐸 &% ∪ 𝐸 &’
because at the end of the algorithm, 𝑣 has at least as many edges going across the cut as within the cut
Ø | 𝐸 & | = | 𝐸 &% | + | 𝐸 &’ |
Ø | 𝐸 &% | ≥ | 𝐸 &’ | %
Ø |𝐸&| ≤ 2 ⋅ |𝐸& | Ø∑&|𝐸&|≤2⋅∑& 𝐸&% Ø2⋅ 𝐸 ≤ 2⋅(2⋅|𝐸%|)
Ø 𝐸≤2⋅|𝐸%| 2021-03-31
o ∑ | 𝐸 | = 2 ⋅ 𝐸 ! !
o ∑!|𝐸!”|=2⋅|𝐸”| So: 𝐸% ≥ 𝐸 /2
CSC373 Winter 2021 – Sam Toueg
Q.E.D.
31

Weighted Max-Cut
• Number of iterations?
Ø In the unweighted case, the number of edges going across the cut increases by at least 1 in each iteration, so the algorithm takes at most |𝐸| iterations
Ø In the weighted case, the total weight of edges going across the cut increases by at least 1 in each iteration, but this could take up to ∑/∈1 𝑤/ iterations now!
Ø Note: this is exponential in the input length.
o There are examples where this algorithm indeed takes
exponentially many steps in the weighted case
2021-03-31 CSC373 Winter 2021 – Sam Toueg 33

Related Posts