Algorithm代做 | Objective – Algorithm

2023-06-19

Algorithm

Algorithm代做 | Objective – 该题目是一个常规的Algorithm的练习题目代写, 涉及了Algorithm/Objective等代写方面

算法代写 代写算法 Algorithm代写 代写Algorithm 算法作业代写

i. F Consider the graph S -> a -> T where (S, a) and (a, T) both have capacity 1. The maximum flow has value 1. Increasing of either edge will not help to increase maximum flow value.

ii. T. This is what weak duality for minimization.

iii F It should be always a polynomial time algorithm.

iv.T The max-cut problem is NP-Complete. If P=NP, then it’s also P, and vise versa.

2

i. True We can do the following to adjust an LP problem if some part violates the requirement:

Objective Function If the Objective Function is we convert it into

Constraints where A is an expression with variables, becomes where is introduced as a new variable that never appeared becomes

Variable range for we introduce and (and substitute each with it) for we introduce and and substitution

for we introduce and and substitution For the variable extraction process we do the reverse to extract each

ii. False We can have a polynomial time 2-approximation Algorithm for Matrix TSP such that Calculate the MST of the graph Duplicate each edge of MST and find an Euler cycle The cycle may have duplicate vertices other than start and end, remove duplicate vertices We now get a Hamilton cycle whose length is at most twice the optimal. The time is a polynomial time since the first two is in polynomial time for example. Prim for the first and BFS for the second Deduplicate takes scan and in which at most querying.

4

(a) On input W > 0 and , and n items each with integer weight > 0, and a real value > 0, do we have a subset of items such that

and

Knapsack is in NP

  1. Certificate: a subset C of items
  2. Verification: calculate the sum of weights and values of C check total weights and total value The verification is scan and sum and checking Therefore it’s a polynomial time verifier thus Knapsack is in NP Knapsack is NP-Hard Via Subset-SUM (S, Target)

we map = = for each and Then a valid solution C of Knapsack shows

Since They together shows

On the converse: If Subset-SUM has a solution then

That is to say

That is to say

Showing there is also a valid solution that can be derived from this solution. Therefore the mapping is a valid reduction. The reduction takes a polynomial time scan to build and Therefore Subset-sum Since Subset-sum is NP-Complete, therefore is NP-Hard

In total, is NP and NP-Hard. Therefore it’s NP-Complete.

(b) The variables: is 1 or 0 denoting whether we choose item or not. The objective function: maximize the chosen value sum. The constraints: The sum of weights does not exceed W and ‘s domain. The IP:

5

Maximum Flow approach: Algorithm

from to capacity Note
S k Can hold up to k containers

T (^1) the same time Can be hold by at most one truck at^ 1 if otherwise no such edge can only take if

  1. Build the graph. Vertex are: S, T : source and sink : the truck node ( ) : the container node ( ) Edges are:
  2. Run Edmond Karp algorithm on it
  3. If the maximum flow has a value answer yes, otherwise no Time Vertex size: Edge size: The total time is mainly governed by Edmond-Karp which is Correctness The table shows why the maximum flow solution is a valid plan if we put each to corresponding if On the converse, if there is a solution to match all pairs of , then it’s also a valid flow when taking and