The Complexity of Approximate Optima for Greatest Common Divisor Computations
We study the approximability of the following NP-complete (in their feasibility recognition forms) number theoretic optimization problems: 1. Given n numbers a1 ; : : : ; an 2 Z, find a minimum gcd set for a1 ; : : : ; an , i.e., a subset S fa1 ; : : : ; ang with minimum cardinality satisfying gcd(S) = gcd(a1 ; : : : ; an ). 2. Given n numbers a1 ; : : : ; an 2 Z, find a 1-minimum gcd multiplier for a1 ; : : : ; an , i.e., a vector x 2 Z n with minimum max 1in jx i j satisfying P n...
Download full text files
Export metadata
Additional Services
| Author: | Carsten Rössner, Jean-Pierre Seifert |
|---|---|
| URN: | urn:nbn:de:hebis:30-16712 |
| URL: | http://citeseer.ifi.unizh.ch/25868.html |
| Document Type: | Article |
| Language: | English |
| Date of Publication (online): | 28.09.2005 |
| Year of first Publication: | 1996 |
| Publishing Institution: | Univ.-Bibliothek Frankfurt am Main |
| Institutes: | Mathematik |
| Informatik | |
| Dewey Decimal Classification: | 510 Mathematik |
| Sammlungen: | Universitätspublikationen |
| Licence (German): |  Veröffentlichungsvertrag für Publikationen ohne Print on Demand |
