Marek Karpinski - Selected publications#

[1] ALON, N., F. DE LA VEGA, W., KANNAN, R., AND KARPINSKI, M. Random Sampling and Approximation of
MAX-CSP Problems. J. Comput. and Syst. Sci. 67 (2003), 212–243.
[2] ARORA, S., KARGER, D., AND KARPINSKI, M. Polynomial Time Approximation Schemes for Dense Instances
of NP-hard Problems. J. Comput. and Syst. Sci. 58 (1999), 193–210.
[3] BERMAN, P., AND KARPINSKI, M. 8/7-Approximation Algorithm For (1, 2)-TSP. Proc. 17th ACM-SIAM SODA
(2006), 641–648.
[4] BORDEWICH, M., DYER, M., AND KARPINSKI, M. Path Coupling Using Stopping Times and Counting Independent
Sets and Colourings in Hypergraphs. Random Struct. Algorithms 32(3): 375-399 (2008)
[5] ENGEBRETSEN, L., AND KARPINSKI, M. TSP with Bounded Metrics. J. Comput. System Sci. 72 (2006).
[6] F. DE LA VEGA, W., KANNAN, R., KARPINSKI, M., AND VEMPALA, S. Tensor Decomposition and Approximation
Schemes for Constraint Satisfaction Problems. Proc. 37th ACM STOC (2005), 747–754.
[7] KARPINSKI, M. Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Problems.
Algorithmica 30 (2001), 386–397.
[8] KARPINSKI, M., AND MACINTYRE, A. Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian
Neural Networks. J. Comput. Syst. Sci. 54 (1997), 169–176.
[9] KARPINSKI, M., SCHUDY,W. Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems, Proc. 41st ACM STOC (2009), pp. 313-322.
[10] KARPINSKI, M., AND ZELIKOVSKY, A. New Approximation Algorithms for the Steiner Tree Problems. J. of Comb.
Optimization 1 (1997), 47–65.



Overall scientific metrics (Google Scholar): 5769 citations, i10-index: 123, h-index: 36