|
|
1970 | M.A. in Mathematics, Poznan University, Poland | 1971 | M.E.E. in Computer Science, Technical University Poznan, Poland | 1973 | PhD in Computer Science and Mathematics, Polish Academy of Sciences, Warsaw, Poland | 1976 | Habilitation in Computer Science and Mathematics, Polish Academy of Sciences, Warsaw, Poland | Since 1989 | Director, Department of Computer Science, University of Bonn | Since 1989 | Professor (C4), Department of Computer Science, University of Bonn | | He has been doing research and teaching at various universities and research institutes among others in Warsaw, Pittsburgh, Berkeley, Princeton, MIT, Yale, Oxford, Cambridge, Lund, and Paris. |
|
|
Main research interests are in computational complexity and design of efficient algorithms, especially randomized and approximate algorithms. Further topics in recent research include: Combinatorial and Geometric Optimization, VC Dimension and O-Minimality, Parallel and Distributed Systems, Internet Algorithms, Algorithmic Game Theory, Computational Molecular Biology.
|
|
ESPRIT BR Working Group – 7097 and 21726 on “Randomized Algorithms, RAND and RAND2”
Bonn, Edinburgh, Leeds, Lund, Oxford, Paris, Weizmann Institute, Rehovot
Principal Investigator, 1992 - 1995 and 1996 - 1999
Volkswagen-Stiftung Project (I/68055) on “Computational Complexity and Efficient Algorithms”
Principal Investigator, 1993 – 1998
NSF/ESPRIT BR Project EC-US 030 on “Randomness and Efficient Computation, RAND-REC” (with M. Luby, Berkeley)
Research Sites: Bonn, Berkeley, Edinburgh, Leeds, Lund, Oxford, and Paris
Principal Investigator, 1993 - 1997
IST BR Project 14036 (RAND-APX) on “Randomness and Approximate Computation”
Bonn, Edinburgh, Leeds, Lund, Oxford, and Paris
Principal Investigator, 1998 - 2004
Chair, Steering Committee on International Series of Conferences “Fundamentals of Computation Theory” (FCT)
Principal Investigator, since 1999
Project PROCOPE 333587 on “Design and Analysis of Randomized Approximation Algorithms for NP-Hard Optimization Problems”
Bonn, Paris
Principal Investigator, 2004 - 2007
FP6 Marie Curie Research Training Network in Model Theory (512234), MODNET
Principal Investigator, since 2004
B-IT Research School, University of Bonn and RWTH Aachen, Research Area “Algorithm Design and Formal Foundations”
Principal Investigator and Project leader, since 2008
|
|
[ 1] Marek Karpinski, Alexander Zelikovsky
New approximation algorithms for the Steiner tree problems J. Comb. Optim. , 1: (1): 47--65 1997 DOI: 10.1023/A:1009758919736[ 2] Sanjeev Arora, David Karger, Marek Karpinski
Polynomial time approximation schemes for dense instances of NP-hard problems J. Comput. System Sci. , 58: (1): 193--210 1999 DOI: 10.1006/jcss.1998.1605[ 3] Noga Alon, W. Fernandez de la Vega, Ravi Kannan, Marek Karpinski
Random sampling and approximation of MAX-CSPs Special issue on STOC2002 (Montreal, QC) J. Comput. System Sci. , 67: (2): 212--243 2003 DOI: 10.1016/S0022-0000(03)00008-4[ 4] Lars Engebretsen, Marek Karpinski
TSP with bounded metrics J. Comput. System Sci. , 72: (4): 509--546 2006 DOI: 10.1016/j.jcss.2005.12.001[ 5] M. Karpinski
Polynomial time approximation schemes for some dense instances of NP-hard optimization problems Approximation algorithms for combinatorial optimization problems Algorithmica , 30: (3): 386--397 2001 DOI: 10.1007/s00453-001-0012-z[ 6] M. Karpinski, W. Schudy
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems Proceedings of the 41st ACM Symposium on Theory of Computing (STOC) 2009[ 7] Gábor Ivanyos, Marek Karpinski, Nitin Saxena
Deterministic polynomial time algorithms for matrix completion problems SIAM J. Comput. , 39: (8): 3736--3751 2010 DOI: 10.1137/090781231[ 8] Marek Karpinski, Angus Macintyre
Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks 1st Annual Dagstuhl Seminar on Neural Computing (1994) J. Comput. System Sci. , 54: (1, part 2): 169--176 1997 DOI: 10.1006/jcss.1997.1477[ 9] Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
The mixing time of Glauber dynamics for coloring regular trees Random Structures Algorithms , 36: (4): 464--476 2010 DOI: 10.1002/rsa.20303[ 10] Piotr Berman, Marek Karpinski, Alexander Zelikovsky
A 3/2-approximation algorithm for generalized Steiner trees in complete graphs with edge lengths 1 and 2 Algorithms and computation. Part I of Lecture Notes in Comput. Sci. : 15--24 Publisher: Springer, Berlin 2010 DOI: 10.1007/978-3-642-17517-6_4[ 11] Bhaskar Das Gupta, Marek Karpinski, Nasim Mobasheri, Farzane Yahyanejad
Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications Algorithmica , 80: (2): 772--800 2018 DOI: 10.1007/s00453-017-0291-7
|
|
|
|
• Electronic Colloquium on Computational Complexity (since 1983)
• Fundamenta Informaticae (1994 - 2010)
• Journal of Combinatorial Optimization (since 1995)
• Compendium of NP Optimization Problems (since 1999)
• Chair, Imternational Steering Committee of the Series of FCT-conferences (since 2011)
• SN Computer Science, Springer (since 2019)
• Journal of Networking and Telecommunications (since 2019)
• Journal Algorithms (since 2020)
|
|
1974 | Prize of the Polish Mathematical Society | 1975 | Venia Legendi Annual Research Prize | 1976 | Award of the Polish Academy of Sciences | 1980 | Special IBM T.J. Watson Research Grant | 1982 | Humboldt Research Award | 1988 | Senior Visiting Research Fellow, Merton College, Oxford University, England, UK | 1995 | Max Planck Research Award | 2004 | IHES European Fellowship | 2013 | Member of the Academia Europaea |
|
|
Download Profile  |