首页 >
> 详细

First Homework Set

Take home exam. Submit solutions via email, preferably in pdf format. Scanned images are OK.

Solutions are due by midnight of Sunday, March 22, 2020 (SHARP!)

Feel free to use an AMPL code when it is helpful!

Problem 1: Let a ∈ R

n

+ and b ∈ R+ be given parameters. Let us call a subset

S ⊆ E = {1, 2, ..., n} independent if a(S) = P

j∈S

aj ≤ b.

• Show that this defines an independence system F ⊆ 2

E.

• Consider n = 6, a = (1, 1, 1, 4, 4, 5), b = 8, E = {1, 2, 3, 4, 5, 6}, and

S = {1, 2, 3, 4, 5}. What are the values of r(S) and ρ(S)? How much is

q(E, F) for this example?

• For an arbitrary n find a ∈ Rn+ and b ∈ R+ such that q(E, F) ≤1n−1.

Problem 2: Consider the problem of processing a set E of n jobs on a single

machine. Each job j ∈ E needs one unit of (uninterrupted) time for processing,

has a due date dj , and brings a profit of pj , if it is finished before its due date.

Let us call a subset S ⊆ E of the jobs independent, if all the jobs in S can be

processed, in some order, such that all of them are finished on time (before their

respective due dates). Let F be the collection of all independent job subsets.

• Consider n = 7, and the following list of (dj , pj ) pairs: (3, 2), (2, 3), (4, 4),(1, 3), (4, 3), (4, 6), (6, 7). What is the ”Best-in-Greedy” solution?

• Prove that (E, F) is a matroid.

Problem 3: Let G be a graph on 5 vertices, V (G) = {1, 2, 3, 4, 5}, defined by

the set of edges E(G) = {(1, 2),(2, 3),(2, 5),(3, 4),(4, 5),(5, 1)}. Let F ⊆ 2V (G)

be the family of independent (stable) sets of G, that is vertex subsets that do

not contain an edge inside.

• Is (V (G), F) a matroid? Why?

• Recall that the associated independence polytope is defined as

Write down the defining inequalities for PV (G),F in this case, and eliminate

the redundant ones.

• How much is the maximum of 5x2 + 3x5 over PV (G),F ?

Problem 4: Consider the graph G on n = 7 vertices V = {1, 2, 3, 4, 5, 6, 7} with

edges E = {(1, 2),(1, 4),(2, 3),(2, 5),(2, 7),(3, 4),(3, 5),(4, 5),(4, 6),(4, 7),(5, 6),(6, 7)},

and with edge weights (in the previous order of edges) w1,2 = 9, w1,4 = 7,

w2,3 = 9, w2,5 = 10, w2,7 = 7, w3,4 = 8, w3,5 = 9, w4,5 = 9, w4,6 = 8, w4,7 = 8,

w5,6 = 7, w6,7 = 7.

1

• What is the weight of the maximum-weight spanning tree?

• Compute the sequence of edges chosen by Kruskal’s algorithm.

Problem 5: Let us consider a bipartite graph G = (A ∪ B, E) where set A

has 15 vertices of degree 3, 18 vertices of degree 5, and 12 vertices of degree 15

(that is |A| = 45 = 15 + 18 + 12.) Every vertex in set B is connected to exactly

1 vertex of degree 3, 2 vertices of degree 5, and 4 vertices of degree 15.

• How large is B?

• How large is a maximum cardinality matching in this graph? Why?

Problem 6: Consider the following cutting stock problem, with input length

L = 21. These 21-foot pieces are to be cut into smaller ones to fulfill the

following orders:

What is the optimal solution?

Problem 7: A company has 100M to invest in several possible projects. They

can either fund a project fully, or do not fund it at all. For each of the 12

possible projects we list in the table below the cost of the project and the net

profit the project is expected to generate (in millions of dollars.) Which projects

to fund so that the company maximizes its net profit?

P rojects

A B C D E F G H I J K L

P rof it 30 25 5 9 11 7 14 19 40 29 30 34

Cost 16 15 2 4 4 3 9 12 29 20 18 25

Solve the problem by the dynamic programming algorithm or by using an AMPL

model. Submit the optimal solution, and the corresponding AMPL .mod and

.dat files, if you worked with AMPL.

Problem 8: Consider a graph G = (V, E) (not necessarily bipartite), nonnegative

weights c : E → R+ on the edges, and the problem of finding a maximum

weight matching. How good (bad) is the greedy algorithm on this problem type?

Figure 1:

[Hint: What is the corresponding independence system F? How small q(E, F)

can be?]

Problem 9: Consider the instance of the Chinese Postman problem shown in

Figure 1. The edge traversing times are shown along the edges in minutes.

• Assume that the post office is in vertex 1. What is the optimal, time

minimizing tour of the postman? How much time does he need to deliver

all letters and get back to the post office?

• Assume that he starts at the post office and wants to finish in his house

in vertex 8. How much time does he need then to deliver all letters and

arrive home? What is his optimal tour in this case?

Problem 10: You are the manager of a consulting firm that has 5 co-workers

(A, B, C, D, and E) and 5 projects (P1, P2, P3, P4, and P5) to complete.

3

The table below shows the expected profit if a worker is assigned to a project.

For instance, if worker A is assigned to project P2, then the company earns $7K

as profit. What is the optimal, profit maximizing assignment of workers to

projects? Use the Hungarian algorithm to solve this, and document each step

of it.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Program课程作业代做、Python语言作业代写、Python编程作业调 2020-06-01
- 代做stats762作业、代写r编程设计作业、R课程设计作业代做、代写dat 2020-06-01
- Cosc 2666作业代写、C++程序设计作业调试、Programming作 2020-06-01
- Stats 731作业代写、代做c+,Java程序语言作业、代写python 2020-06-01
- Etf5952课程作业代写、Risk Analysis作业代做、Python 2020-06-01
- 41889留学生作业代做、代写ios Application作业、Java， 2020-06-01
- Sta2202作业代做、代写data课程作业、R程序语言作业调试、代写r课程 2020-06-01
- You Have Implemented A Simple Web Serv... 2020-05-31
- Stat 5511 Homework 4 2020-05-31
- Lab 7 2020-05-31
- 代写cosc 363作业、代做computer Graphics作业、代写c 2020-05-31
- Eie111课程作业代写、C++程序设计作业调试、代做c/C++语言作业、代 2020-05-31
- Math502作业代做、Mathematics课程作业代做、Java，Pyt 2020-05-31
- 代写sit114课程作业、代做data留学生作业、代写r编程设计作业、代做r 2020-05-31
- Envx3002作业代写、R程序语言作业调试、R课程设计作业代做、代写dat 2020-05-31
- Ee6435 Programming Homework 2020-05-30
- Computer Architecture Homework 3 2020-05-30
- Infs7450作业代做、Media Analytics作业代写、Pytho 2020-05-29
- 代写stats 782作业、代做r编程设计作业、代写data留学生作业、R课 2020-05-29
- 代写math223作业、R课程设计作业代做、代写data课程作业、R程序语言 2020-05-28