Dyadic linear programming and extensions
成果类型：
Article
署名作者：
Abdi, Ahmad; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
署名单位：
University of London; London School Economics & Political Science; Carnegie Mellon University; University of Waterloo
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-024-02146-4
发表日期：
2025
页码：
473-516
关键词：
摘要：
A rational number is dyadic if it has a finite binary representation p/2k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p/2<^>k$$\end{document}, where p is an integer and k is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-point arithmetic on a computer. A vector is dyadic if all its entries are dyadic rationals. We study the problem of finding a dyadic optimal solution to a linear program, if one exists. We show how to solve dyadic linear programs in polynomial time. We give bounds on the size of the support of a solution as well as on the size of the denominators. We identify properties that make the solution of dyadic linear programs possible: closure under addition and negation, and density, and we extend the algorithmic framework beyond the dyadic case.
来源URL：