.png){kind=icon}
.png){kind=icon}
Return
Information-Assisted Dynamic Programming for a Class of Constrained Combinatorial Problems
.png){kind=icon}
PRE
AI
DOI：10.1109/ACCESS.2022.3198964.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The constrained discrete optimization (CDO) problems pose an immense challenge to solve with provable accuracy and computational efficiency. Dynamic programming (DP) is an elegant technique that is used to solve a class of such problems with linear constraints that follow a particular structure, namely Bellman's principle of optimality (BPO). Unfortunately, many of the CDO problems do not fall into this category. This work focuses on solving a class of CDO problems, which we call problem class H, that do not satisfy BPO if the constraint functions are considered. There are no conditions placed on the constraint functions of H. However, the objective function alone satisfies the BPO. Such problems are ubiquitous in wireless communication, signal processing, and machine learning. These problems are, in general, NP-Hard. This paper attempts to unify this class of problems to be solvable using the DP framework. Using the theory of multi-objective optimization and assisted by an information-theoretic measure, we establish provable near-optimality guarantees with reduced computational complexity. We describe two algorithms to solve H. We support our claims by solving the power-constrained analog-to-digital converter bit allocation (BA) problem in massive Multiple-Input Multiple-Output (MaMIMO) receivers. The optimal BA thus obtained ensures the maximum energy efficiency of the MaMIMO receiver.
Keywords:
Optimization
Dynamic programming
Receivers
Computational complexity
Viterbi algorithm
Resource management
Pareto optimization
Bellman's optimality principle
dynamic programming
information-to-go
Kullback-Leibler divergence
multi-objective optimization
Pareto optimal solution
Journal
IF:
3.6
Papers:
9.8W
Citations:
29.4W
