Uni Logo

FORSCHUNGSBERICHT 1999-2001

INDEX
Prev.:Institut für Informatik Abteilung für Informatik IV
Next:Institut für Informatik Abteilung für Informatik VI
Up:Forschungsbericht
Up:Mathematisch-Naturwissenschaftliche Fakultät

Institut für Informatik Abt.für Informatik V

Allgemeine Angaben:
Römerstraße 164, 53117 Bonn
Telefon: 0228 / 73-4327
Fax: 0228 / 73-4440
eMail: marikar@cs.uni-bonn.de

Hauptamtliche Professoren:
Prof. Dr. Norbert Blum
Prof. Dr. Marek Karpinski

Wissenschaftliches Personal:
Universitätsstellen
Priv.-Doz. Elias Dahlhaus
Dipl.-Math. Mathias Hauptmann
Dipl.-Inform. Martin Löhnertz
Dr. Yakov Nekritch
Dr. Maria Nikolaidou
Dr. Claus Rick
Dipl.-Inform. Peter Wegner

Drittmittelstellen
Prof. Dr. Piotr Berman (DFG)

Forschungsschwerpunkte:
Optimierungsprobleme der Bioinformatik
(Blum)

Graphentheorie
(Blum, Löhnertz)

Algorithmische Geometrie und VC Dimension
(Dahlhaus, Hauptmann, Karpinski, Nekritch, Wegner)

Approximationsalgorithmen für NP-harte kombinatorische Optimierungsprobleme und Anwendungen
(Dahlhaus, Hauptmann, Karpinski, Nekritch, Wegner)

Berechnungskomplexität, Boolesche Schaltkreise, Branching Programme und VLSI-Entwurf
(Dahlhaus, Hauptmann, Karpinski, Nekritch, Wegner)

Parallele und verteilte Systeme, On-Line Algorithmen
(Dahlhaus, Hauptmann, Karpinski, Nekritch, Wegner)

Schnelle parallele und randomisierte Algorithmen
(Dahlhaus, Hauptmann, Karpinski, Nekritch, Wegner)

Kodierungs- und Dekodierungsalgorithmen für fehlerresistente ATM Systeme
(Dahlhaus, Karpinski, Nekritch, Wegner)

Compilerbau
(Löhnertz)

Stringalgorithmen
(Nikolaidou, Rick)

Besondere Forschungsförderung:
DFG
(Karpinski, Deutsche Forschungsgemeinschaft, Bonn)

ESPRIT BR RAND2
(Karpinski, European Commission - Bruxelles)

IST-1999-14036; RAND-APX
(Karpinski, European Commission - Bruxelles)

PROCOPE
(Karpinski, DAAD - Deutscher Akademischer Austauschdienst)

Veröffentlichungen:

Ablayev F, Gainutdinova A, Karpinski M
On Computational Power of Quantum Branching Programs
Proc. of the 13th Symposium on Fundamentals of Computation Theory,LNCS 2138(2001), pp. 59-70

Ambainis A, Bonner R, Freivalds R, Golovkins M, Karpinski M
Quantum finite multitape automata
SOFSEM'99: theory and practice of informatics (Milovy), 340--348, Lecture Notes in Comput. Sci., 1725

Arora S, Karger D, Karpinski M
Polynomial Time Approximation Schemes for Dense Instances of NP-hard Problems
J. Comput. System Sci. 58 (1999), pp. 193-210

Berman P, Charikar M, Karpinski M
On-line Load Balancing for Related Machines
J. of Algorithms 35 (2000), pp. 108-121

Berman P, Karpinski M
On Some Tighter Inapproximability Results
Preliminary version appeared in ECCC TR98-065; Also in Proc. 26th ICALP (1999), pp. 200-209

Blum N
Speeding up Dynamic Programming without Omitting any Optimal Solution and some Applications in Molecular Biology,
Journal of Algorithms 35

Blum N
On Parsing LL-Languages
TCS 267

Blum N , Koch R
Greibach Normal Form Transformation, Revisited
Information and Computation 150

Engebretsen L, Karpinski M
Approximation Hardness of TSP with Bounded Metrics,
ECCC TR00-089 (2000), to appear in Proc. 28th ICALP (2001)

Evdokimov S, Karpinski M, Ponomarenko I
On a new High-dimensional Weisfeiler-Lehman Algorithm
J. Algebraic Combin. 10 (1999)

Feige U, Karpinski M, Langberg M
Improved Approximation of MAX-CUT on Graphs of Bounded
ECCC TR00-021 (2000), to appear in J. of Algorithms 2002

Fernandez de la Vega W, Karpinski M
On the Approximation Hardness of Dense TSP and other Path Problems
Information Processing Letters 70 (1999), pp. 53-55

Fernandez de la Vega W, Karpinski M
Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT
Random Structures and Algorithms 8 (2000), pp. 314-332

Freivalds R, Karpinski M, Smith C H, Wiehagen R
Learning by the Process of Elimination
Information and Computation, 171 (2001)

Jansen K, Karpinski M, Lingas A, Seidel E
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
Proc. STACS '01, LNCS

Karpinski M
Randomized Complexity of Linear Arrangements and Polyhedra
Proc. 12th FCT (1999), pp. 1-12

Karpinski M
Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Problems
Algorithmica 30 (2001), pp. 386-397

Karpinski M
Approximating Bounded Degree Instances of NP-Hard Problems
Proc. 13th Symp. on Fundamentals of Computation Theory, FCT'01, LNCS 2138 (2001), pp.24-34.

Karpinski M, Macintyre A
A Generalization of Wilkie's Theorem of the Complement, and an Application to Pfaffian Closure
Selecta Mathematica 5 (1999), pp. 1-10

Karpinski M, Macintyre A
Approximating Volumes and Integrals in o-minimal and p-minimal Theories
Quaderni Mathematica, 6(2000), pp. 149-177

Karpinski M, Mubarakzjanov R
A Note on Las Vegas OBDDs
ECCC TR99-009

Karpinski M, Shparlinski I
On the Computational Hardness of Testing Square-Freeness of Sparse Polynomials
Proc. AAECC (1999), pp. 492-497

Karpinski M, van der Poorten A, Shparlinski I
Zero Testing of p-adic and Modular Polynomials
Theoretical Computer Science, 233 (2000), pp. 309-317

Nekritch Y
Decoding of Canonical Huffman Codes with Look-Up Tables
Data Compression Conference 2000, 28-30 March

Nekritch Y
Byte-oriented Decoding of Canonical Huffman Codes
IEEE International Symposium on Information Theory

Nekritch Y
Image Compression by Local Choice of Compression Method
Signal and Image Processing Conference

Rick C
Efficient Computation of All Longest Common Subsequences
Lecture Notes in Computer Science, Vol. 1851

Rick C
Simple and Fast Linear Space Computation of Longest Common Subsequences,
Information Processing Letters, Vol. 75/6


eMail: Transfer und Öffentlichkeitsarbeit