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...
Verfasserangaben: | Carsten Rössner, Jean-Pierre Seifert |
---|---|
URN: | urn:nbn:de:hebis:30-16712 |
URL: | http://citeseer.ifi.unizh.ch/25868.html |
Verlagsort: | Frankfurt am Main |
Dokumentart: | Bericht |
Sprache: | Englisch |
Datum der Veröffentlichung (online): | 28.09.2005 |
Jahr der Erstveröffentlichung: | 1996 |
Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
Datum der Freischaltung: | 28.09.2005 |
Seitenzahl: | 16 |
HeBIS-PPN: | 358603684 |
Institute: | Informatik und Mathematik / Mathematik |
Informatik und Mathematik / Informatik | |
DDC-Klassifikation: | 5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik |
Lizenz (Deutsch): | Deutsches Urheberrecht |