Карпинский, Марек

Марек Карпинский

польск. Marek Karpinski

Файл:Marek Karpinski 2.jpg

Дата рождения

25 марта 1948 года

Род деятельности

информатик, математик

Марек Карпинский (^{[Нет даты!]}) — польский информатик и математик. Известен исследованиями в области теории алгоритмов и их приложений, комбинаторной оптимизации, вычислительной сложности и математических основ информатики. Лауреат премии Макса Планка (1994).

Биография

Работал в области исследований и преподавания в различных европейских и американских университетах, в том числе в Беркли, Принстоне и Бонне. Внёс вклад в развитие аппроксимационных алгоритмов для NP-трудных задач оптимизации, теории VC-размерности (теорема Карпинского — Макинтайра), а также других вычислительных методов нижних оценок для различных вычислительных моделей. Получил несколько исследовательских премий в упомянутых областях. Является соучредителем международной серии конференций по теоретической информатике FCT, а также специализированных боннских семинаров по теории вычислений. Был одним из основателей и главным исследователем международных исследовательских групп по основам рандомизированных и приближённых вычислений.

Сейчас является профессором информатики и математики, руководителем группы алгоритмов и вычислительной сложности в Боннском университете и алгоритмической секции Bonn-Aachen Research School. Также является одним из членов-основателей Bonn International Graduate School in Mathematics и Hausdorff Center for Mathematics.

В 1994 году был удостоен премии Макса Планка. В 2013 году был избран в Европейскую академию.

Литература

• N. Alon, W. F. de la Vega, R. Kannan, and M. Karpinski, Random Sampling and Approximation of MAX-CSP Problems, J. Comput. and Syst. Sci. 67 (2003), 212–243..
• S. Arora, D. Karger, and M. Karpinski, Polynomial Time Approximation Schemes for Dense Instances of NP-hard Problems, J. Comput. and Syst. Sci. 58 (1999), 193–210..
• M. Bordewich, M. Dyer, and M. Karpinski, Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs ,Random Struct. Algorithms 32 (2008), 375–399..
• L. Engebretsen and M. Karpinski, TSP with Bounded Metrics, J. Comput. System Sci. 72 (2006), 509–546..
• W. F. de la Vega, R. Kannan, M. Karpinski, and S. Vempala, Tensor Decomposition and Approximation Schemes for Constraint Satisfaction Problems, Proc. 37th ACM STOC (2005), 747–754..
• G. Ivanyos, M. Karpinski, and N. Saxena, Deterministic Polynomial Time Algorithms for Matrix Completion Problems, SIAM J. Comput. 39 (2010), 3736-3751..
• M. Karpinski, Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Problems, Algorithmica 30 (2001), 386–397..
• M. Karpinski and A. Macintyre, Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks, J. Comput. Syst. Sci. 54 (1997), 169–176..
• M. Karpinski and W. Schudy, Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems, Proc. 41st ACM STOC (2009), pp. 313-322..
• M. Karpinski and A. Zelikovsky, New Approximation Algorithms for the Steiner Tree Problems, J. of Comb. Optimization1 (1997), 47–65..

Ссылки

• Site personnelангл..
• Marek Karpinski at DBLPангл.. Архивировано из первоисточника 3 октября 2012. Проверено 17 ноября 2014.
• Marek Karpinski at Scholar Wikiангл.. Архивировано из первоисточника 3 ноября 2014. Проверено 17 ноября 2014.
• Число Эрдёша
• Publications at ACM Digital Libraryангл..
• The Best Nurturers in Computer Science Researchангл.. Архивировано из первоисточника 26 сентября 2015. Проверено 18 ноября 2014.

Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Карпинский, Марек», расположенная по адресу: — https://ru.ruwiki.ru/wiki/Карпинский,_Марек Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?».