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

DOI10.1016/J.DAM.2019.08.012MaRDI QIDQ2192058zbMATH OpenOpenAlexFDO

Authors Noam Goldberg, Gábor Rudolf

Publication date 29 June 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.07406

zbMATH Keywords

computational complexityapproximation schemespseudo-Boolean optimization

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Stochastic programming (90C15)

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.

Recommendations

• The minimum expectation selection problem
• Maximizing nonmonotone submodular functions under matroid or knapsack constraints
• Maximum probabilistic all-or-nothing paths
• Maximizing expected utility over a knapsack constraint
• Maximizing a monotone submodular function subject to a matroid constraint

Cites work

• scientific article; zbMATH DE number 3694944 (Why is no real title available?)
• A fully polynomial time approximation scheme for minimum cost-reliability ratio problems
• A parametric characterization and an \(\epsilon\)-approximation scheme for the minimization of a quasiconcave program
• A polynomial algorithm for a class of 0-1 fractional programming problems involving composite functions, with an application to additive clustering
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Approximation algorithms for sequential batch-testing of series systems
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Maximizing the Product of Two Linear Functions In 0-1 Variables
• Minimization of half-products
• Non‐zero‐sum nonlinear network path interdiction with an application to inspection in terror networks
• Polynomial testing of the query Is \(a^ b\geq c^ d?\) with application to finding a minimal cost reliability ratio spanning tree
• Pseudo-Boolean optimization
• \(NP\)-hardness of linear multiplicative programming and related problems

Cited in

(4)

• The minimum expectation selection problem
• Linearized formulations for failure aware barter exchange
• Maximum probabilistic all-or-nothing paths
• Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions

This page was built for publication: On the complexity and approximation of the maximum expected value all-or-nothing subset

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192058)