A maximum feasible subset algorithm with application to radiation therapy

Payman Sadegh

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    359 Downloads (Pure)


    Consider a set of linear one sided or two sided inequality constraints on a real vector X. The problem of interest is selection of X so as to maximize the number of constraints that are simultaneously satisfied, or equivalently, combinatorial selection of a maximum cardinality subset of feasible inequalities. Special classes of this problem are of interest in a variety of areas such as pattern recognition, machine learning, operations research, and medical treatment planning. This problem is generally solvable in exponential time. A heuristic polynomial time algorithm is presented in this paper. The algorithm relies on an iterative constraint removal procedure where constraints are eliminated from a set proposed by solutions to minmax linear programs. The method is illustrated by a simulated example of a linear system with double sided bounds and a case from the area of radiation therapy.
    Original languageEnglish
    Title of host publicationProceedings of American Control Conference
    Publication date1999
    ISBN (Print)0-7803-4990-3
    Publication statusPublished - 1999
    EventAmerican Control Conference 1999 - San Diego, CA, United States
    Duration: 2 Jun 19994 Jun 1999


    ConferenceAmerican Control Conference 1999
    Country/TerritoryUnited States
    CitySan Diego, CA

    Bibliographical note

    Copyright: 2000 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE


    Dive into the research topics of 'A maximum feasible subset algorithm with application to radiation therapy'. Together they form a unique fingerprint.

    Cite this