|
|
|
| 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
|
|
Research Area G
New probabilistic method has been developed to approximate the class of dense minimization pronlems solving some open problems of the area. | Research Area KL
Strongest up to now inapproximablity bounds have been proven for the Traveling Salesman Problem and somr related optimization problems. |
|
|
[ 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)
|
|
| 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  |
