TY  - RPRT
A1  - Rössner, Carsten
A1  - Seifert, Jean-Pierre
T1  - The complexity of approximate optima for greatest common divisor computations
N2  - 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...
Y1  - 2005
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/3820
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-16712
UR  - http://citeseer.ifi.unizh.ch/25868.html
CY  - Frankfurt am Main
ER  -