Prove that MUTINY-FREE-ALLOCATION is in NP

Reference no: EM132313104

Math Assignment - Algorithms

Need help with a couple of NP hardness proofs.

Task 1 -

You are a pirate captain. After looting a cargo ship, you need to divide up the n treasure chests among k pirates in an egalitarian manner to avoid mutiny. A reasonable way to model this is that the happiness of a pirate is the total value of his allocation, and the goal is to find an allocation such that least-happy pirate is as happy as possible.

This suggests the following decision problem called MUTINY-FREE-ALLOCATION (or MFA for short). The input to MUTINY-FREE-ALLOCATION consists of:

a list of n non-negative integers v₁, . . . , v_n,
the number of pirates k, and
a lower bound l.

The problem is to decide if there is a partition of v₁, . . . , v_n into k subsets S₁, . . . , S_k such that each subset S_i sums to at least l.

Your task is to prove that -

(a) MUTINY-FREE-ALLOCATION is in NP,

(b) MUTINY-FREE-ALLOCATION is NP-hard using a Karp reduction. [Hint: Reduce from the Partition problem.]

Task 2 -

You are planning a road trip across Australia and need to decide which destinations you can reach from Sydney. The constraints are as follows: each road has a length and a toll cost; moreover, your car can travel K kilometers before it breaks down and you have D dollars. A destination is reachable if there exists a path from Sydney to the destination with total length at most K and total cost at most D.

This suggests the following decision problem called ROAD-TRIP-REACHABILITY (or RTR for short). The input consists of:

an undirected graph G = (V, E) where each edge e has a non-negative integer length l(e) and a non-negative integer cost c(e),
a source vertex s and a destination vertex t in V,
a non-negative integer length budget K and a non-negative integer cost budget D.

The problem is to decide if there exists a simple path P from s to t in G with total length ∑_e_∈p l(e) ≤ K and total cost ∑_e_∈P c(e) ≤ D.

Your task is to prove that -

(a) ROAD-TRIP-REACHABILITY is in NP,

(b) ROAD-TRIP-REACHABILITY is NP-hard using a Karp reduction. [Hint: Reduce from the Partition problems].

Attachment:- Assignment Files.rar

Reference no: EM132313104

Questions Cloud

Write a code to design a band-stop filter : Designing a band-stop FIR filter using Frequency sampling approach - Write a code to design a band-stop filter. Design a band-stop filter by having

Designing bandpass fir filter using windowed fourier series : Designing a low pass FIR filter using Windowed Fourier Series approach - Designing a bandpass FIR filter using Windowed Fourier Series approach

Implement and utilise a relational database : Implement and utilise a relational database using a database system - Model organisational information requirements using conceptual data modelling techniques

Data model development and implementation : Understand the fundamental principles of the networking and data requirements of a network - Identify organisational information requirements - Model

Prove that MUTINY-FREE-ALLOCATION is in NP : Your task is to prove that - MUTINY-FREE-ALLOCATION is in NP, and MUTINY-FREE-ALLOCATION is NP-hard using a Karp reduction

Performance evaluation of the design : Advanced Network Design Assignment - Network requirement analysis, plan and design - Evaluate performance metrics and dimensions according to specifications

Network requirement analysis - plan and design : Design must be the transformation of the existing design show in Figure 1 (i.e., IP addressing, number of departments etc., should remain intact in the new

Challenges faced by international student in english : Challenges faced by international student in English language in Australia - demonstrating their understanding of the business research paradigm, appropriate

Five different organizational mission statements : Using the mission statements, describe what types of corporate-level and business-level strategies each organization might use to fulfill that mission statement

User Account

All Pages