Discrepancy One among Homogeneous Arithmetic Progressions |
| |
Authors: | Robert Hochberg Paul Phillips |
| |
Institution: | 1.Department of Mathematics,University of Dallas,Irving,USA |
| |
Abstract: | We investigate a restriction of Paul Erd?s’ well-known problem from 1936 on the discrepancy of homogeneous arithmetic progressions. We restrict our attention to a finite set S of homogeneous arithmetic progressions, and ask when the discrepancy with respect to this set is exactly 1. We answer this question when S has size four or less, and prove that the problem for general S is NP-hard, even for discrepancy 1. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|