On a class of branching problems in broadcasting and distribution

Edward C. Rosenthal, Sohail S. Chaudhry, In Chan Choi, Jinbong Jang

    Research output: Contribution to journalArticlepeer-review

    1 Citation (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)1793-1799
    Number of pages7
    JournalComputers and Operations Research
    Volume39
    Issue number8
    DOIs
    Publication statusPublished - 2012 Aug

    Keywords

    • Distribution
    • Graph theory
    • Logistics
    • Network flows

    ASJC Scopus subject areas

    • General Computer Science
    • Modelling and Simulation
    • Management Science and Operations Research

    Fingerprint

    Dive into the research topics of 'On a class of branching problems in broadcasting and distribution'. Together they form a unique fingerprint.

    Cite this