On a class of branching problems in broadcasting and distribution
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Rosenthal, Edward C. | - |
dc.contributor.author | Chaudhry, Sohail S. | - |
dc.contributor.author | Choi, In-Chan | - |
dc.contributor.author | Jang, Jinbong | - |
dc.date.accessioned | 2021-09-06T17:20:09Z | - |
dc.date.available | 2021-09-06T17:20:09Z | - |
dc.date.created | 2021-06-18 | - |
dc.date.issued | 2012-08 | - |
dc.identifier.issn | 0305-0548 | - |
dc.identifier.uri | https://scholar.korea.ac.kr/handle/2021.sw.korea/107838 | - |
dc.description.abstract | We introduce the following network optimization problem: given a directed graph with a cost function on the arcs, demands at the nodes, and a single source s, find the minimum cost connected subgraph from s such that its total demand is no less than lower bound D. We describe applications of this problem to disaster relief and media broadcasting, and show that it generalizes several well-known models including the knapsack problem, the partially ordered knapsack problem, the minimum branching problem, and certain scheduling problems. We prove that our problem is strongly NP-complete and give an integer programming formulation. We also provide five heuristic approaches, illustrate them with a numerical example, and provide a computational study on both small and large sized, randomly generated problems. The heuristics run efficiently on the tested problems and provide solutions that, on average, are fairly close to optimal. (C) 2011 Elsevier Ltd. All rights reserved. | - |
dc.language | English | - |
dc.language.iso | en | - |
dc.publisher | PERGAMON-ELSEVIER SCIENCE LTD | - |
dc.subject | ALGORITHMS | - |
dc.title | On a class of branching problems in broadcasting and distribution | - |
dc.type | Article | - |
dc.contributor.affiliatedAuthor | Choi, In-Chan | - |
dc.identifier.doi | 10.1016/j.cor.2011.06.001 | - |
dc.identifier.scopusid | 2-s2.0-84855207626 | - |
dc.identifier.wosid | 000300745900002 | - |
dc.identifier.bibliographicCitation | COMPUTERS & OPERATIONS RESEARCH, v.39, no.8, pp.1793 - 1799 | - |
dc.relation.isPartOf | COMPUTERS & OPERATIONS RESEARCH | - |
dc.citation.title | COMPUTERS & OPERATIONS RESEARCH | - |
dc.citation.volume | 39 | - |
dc.citation.number | 8 | - |
dc.citation.startPage | 1793 | - |
dc.citation.endPage | 1799 | - |
dc.type.rims | ART | - |
dc.type.docType | Article | - |
dc.description.journalClass | 1 | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.relation.journalResearchArea | Computer Science | - |
dc.relation.journalResearchArea | Engineering | - |
dc.relation.journalResearchArea | Operations Research & Management Science | - |
dc.relation.journalWebOfScienceCategory | Computer Science, Interdisciplinary Applications | - |
dc.relation.journalWebOfScienceCategory | Engineering, Industrial | - |
dc.relation.journalWebOfScienceCategory | Operations Research & Management Science | - |
dc.subject.keywordPlus | ALGORITHMS | - |
dc.subject.keywordAuthor | Distribution | - |
dc.subject.keywordAuthor | Logistics | - |
dc.subject.keywordAuthor | Network flows | - |
dc.subject.keywordAuthor | Graph theory | - |
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
145 Anam-ro, Seongbuk-gu, Seoul, 02841, Korea+82-2-3290-2963
COPYRIGHT © 2021 Korea University. All Rights Reserved.
Certain data included herein are derived from the © Web of Science of Clarivate Analytics. All rights reserved.
You may not copy or re-distribute this material in whole or in part without the prior written consent of Clarivate Analytics.