Publication:
On the complexity and approximation of the maximum expected value all-or-nothing subset

Thumbnail Image

Organizational Units

Program

KU-Authors

KU Authors

Co-Authors

Goldberg, Noam

Advisor

Publication Date

2018

Language

English

Type

Journal Article

Journal Title

Journal ISSN

Volume Title

Abstract

An unconstrained nonlinear binary optimization problem of selecting a maximum expected value subset of items is considered. Each item is associated with a profit and probability. Each of the items succeeds or fails independently with the given probabilities, and the profit is obtained in the event that all selected items succeed. The objective is to select a subset that maximizes the total value times the product of probabilities of the chosen items. The problem is proven NP-hard by a nontrivial reduction from subset sum. Then we develop a fully polynomial time approximation scheme (FPTAS) for this problem.

Description

Source:

Discrete Applied Mathematics

Publisher:

Keywords:

Subject

Computer Science

Citation

Endorsement

Review

Supplemented By

Referenced By

Copy Rights Note

0

Views

1

Downloads

View PlumX Details