Formulate the problem of finding the minimum cost connection

Assignment Help Basic Computer Science

Reference no: EM131122642

We have m communication terminals, each to be connected to one out of a given collection of concentrators. Suppose that there is a cost aij for connecting terminal i to concentrator j, and that each concentrator j has an upper bound bj on the number of terminals it can be connected to. Also, each terminal i can be connected to only a given subset of concentrators.

(a) Formulate the problem of finding the minimum cost connection of terminals to concentrators as a minimum cost flow problem. Hint: You may use the fact that there exists an integer optimal solution to a minimum cost flow problem with integer supplies and arc flow bounds. (This will be shown in Chapter 5.)

(b) Suppose that a concentrator j can operate in an overload condition with a number of connected terminals greater than bj , up to a number bj > bj . In this case, however, the cost per terminal connected becomes aij > aij . Repeat part (a).

(c) Suppose that when no terminals are connected to concentrator j there is a given cost savings cj > 0. Can you still formulate the problem as a minimum cost flow problem?

Reference no: EM131122642

Questions Cloud

From the headlines-cleantricity briefly describe the small : From the Headlines-CLEANtricity: Briefly describe the small wind turbine market and how CLEANtricity's SHAPEshifter addresses that market. Give some examples of how CLEANtricity might approach raising the $2 million in capital that it seeks

Describe company when the platform was initially discussed : Describe the company, the industry and when the platform was initially discussed. Which factors or drivers, using the textbook as a source, are in the firm's sustainability platform?

Check whether these scores are feasible : Show that this is equivalent to checking feasibility of some transportation problem.

Development of organizational health care policies : Analyze the role of accreditation and regulatory agencies in the health care industry. Evaluate what impact legal and regulatory requirements have on the development of organizational health care policies

Formulate the problem of finding the minimum cost connection : Suppose that when no terminals are connected to concentrator j there is a given cost savings cj > 0. Can you still formulate the problem as a minimum cost flow problem?

Describe the life cycle approach for teaching entrepreneure : Describe the life cycle approach for teaching entrepreneurial finance.

An entrepreneur or a marketing strategist : Scenario: Students are to either undertake the role of an entrepreneur or a marketing strategist. In your chosen role identify a product/service that you are interested in creating/developing or a new existing product/service you think would be p..

Create competitive advantage when other organizations fail : Write a paper of 1,600-1,750 words in which you discuss why Blue Ocean organizations successfully create sustainable competitive advantage when other organizations fail.

Identify the major sources as well as the players associated : Identify the major sources, as well as the players, associated with each type of financing for each life cycle stage.

User Account

All Pages