A maximum feasible subset algorithm with application to radiation therapy

Payman Sadegh

doi:10.1109/ACC.1999.782859

A maximum feasible subset algorithm with application to radiation therapy

Payman Sadegh

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

403 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Proceedings of American Control Conference
Volume	1
Publication date	1999
Pages	405-408
ISBN (Print)	0-7803-4990-3
DOIs	https://doi.org/10.1109/ACC.1999.782859
Publication status	Published - 1999
Event	American Control Conference 1999 - San Diego, CA, United States Duration: 2 Jun 1999 → 4 Jun 1999

Conference

Conference	American Control Conference 1999
Country/Territory	United States
City	San Diego, CA
Period	02/06/1999 → 04/06/1999

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

Access to Document

10.1109/ACC.1999.782859

SadeghFinal published version, 419 KB

OpenUrl availability

Full text

Cite this

@inproceedings{37a03741931b4725bf696e0748cfa2cd,

title = "A maximum feasible subset algorithm with application to radiation therapy",

abstract = "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.",

author = "Payman Sadegh",

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; American Control Conference 1999, ACC 1999 ; Conference date: 02-06-1999 Through 04-06-1999",

year = "1999",

doi = "10.1109/ACC.1999.782859",

language = "English",

isbn = "0-7803-4990-3",

volume = "1",

pages = "405--408",

booktitle = "Proceedings of American Control Conference",

}

TY - GEN

T1 - A maximum feasible subset algorithm with application to radiation therapy

AU - Sadegh, Payman

N1 - 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

PY - 1999

Y1 - 1999

N2 - 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.

AB - 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.

U2 - 10.1109/ACC.1999.782859

DO - 10.1109/ACC.1999.782859

M3 - Article in proceedings

SN - 0-7803-4990-3

VL - 1

SP - 405

EP - 408

BT - Proceedings of American Control Conference

T2 - American Control Conference 1999

Y2 - 2 June 1999 through 4 June 1999

ER -

A maximum feasible subset algorithm with application to radiation therapy

Abstract

Conference

Bibliographical note

Access to Document

OpenUrl availability

Fingerprint

Cite this