| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Marek Karpinski, Richard Schmied |
On Approximation Lower Bounds for TSP with Bounded Metrics.  |
Electronic Colloquium on Computational Complexity (ECCC)  |
2012 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
Approximate Counting of Matchings in Sparse Hypergraphs |
CoRR |
2012 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
Approximate Counting of Matchings in Sparse Uniform Hypergraphs |
CoRR |
2012 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Richard Schmied |
On Approximation Lower Bounds for TSP with Bounded Metrics |
CoRR |
2012 |
DBLP BibTeX RDF |
|
| 1 | Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena |
Trading GRH for algebra: Algorithms for factoring polynomials and related structures. |
Math. Comput. |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann |
Approximating vertex cover in dense hypergraphs. |
J. Discrete Algorithms |
2012 |
DBLP DOI BibTeX RDF |
|
| 1 | Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann |
Approximating Subdense Instances of Covering Problems. |
Electronic Notes in Discrete Mathematics |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Richard Schmied, Claus Viehmann |
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Richard Schmied |
Improved Lower Bounds for the Shortest Superstring and Related Problems. |
Electronic Colloquium on Computational Complexity (ECCC) |
2011 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Richard Schmied |
Improved Lower Bounds for the Shortest Superstring and Related Problems |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Richard Schmied, Claus Viehmann |
Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Bhaskar DasGupta, Lakshmi Kaligounder, Marek Karpinski |
On Systemic Stability of Banking Networks |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski |
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). |
Dagstuhl Reports |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Top-K Color Queries for Document Retrieval. |
SODA |
2011 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Warren Schudy |
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems. |
APPROX-RANDOM |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
Computational Complexity of the Perfect Matching Problem in Hypergraphs with Subcritical Density. |
Int. J. Found. Comput. Sci. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski |
The mixing time of Glauber dynamics for coloring regular trees. |
Random Struct. Algorithms |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Warren Schudy |
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann |
Approximating Vertex Cover in Dense Hypergraphs |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Top-K Color Queries for Document Retrieval |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Jean Cardinal, Marek Karpinski, Richard Schmied, Claus Viehmann |
Approximating Subdense Instances of Covering Problems |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, J. Ian Munro, Yakov Nekrich |
Range Reporting for Moving Points on a Grid |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | A. Abouelaoualim, Kinkar Chandra Das, Wenceslas Fernandez de la Vega, Marek Karpinski, Yannis Manoussakis, Carlos A. J. Martinhon, Rachid Saad |
Cycles and paths in edge-colored graphs with given degrees. |
Journal of Graph Theory |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Gábor Ivanyos, Marek Karpinski, Nitin Saxena |
Deterministic Polynomial Time Algorithms for Matrix Completion Problems. |
SIAM J. Comput. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs. |
LATIN |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Andrzej Lingas |
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems. |
COCOON |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alexander Zelikovsky |
A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2. |
ISAAC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Warren Schudy |
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament. |
ISAAC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Gábor Ivanyos, Marek Karpinski, Nitin Saxena |
Deterministic Polynomial Time Algorithms for Matrix Completion Problems. |
Electronic Colloquium on Computational Complexity (ECCC) |
2009 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
A Fast Algorithm for Adaptive Prefix Coding. |
Algorithmica |
2009 |
DBLP DOI BibTeX RDF |
Prefix-free codes, Data compression, Adaptive coding |
| 1 | Piotr Berman, Marek Karpinski, Andrzej Lingas |
Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems with Applications |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Gábor Ivanyos, Marek Karpinski, Nitin Saxena |
Deterministic Polynomial Time Algorithms for Matrix Completion Problems |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Warren Schudy |
Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Bhaskar DasGupta, Marek Karpinski |
Approximating Transitive Reductions for Directed Networks. |
WADS |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alexander Zelikovsky |
1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2. |
WADS |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Space Efficient Multi-dimensional Range Reporting. |
COCOON |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Andrzej Rucinski, Edyta Szymanska |
The Complexity of Perfect Matching Problems on Dense Hypergraphs. |
ISAAC |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Gábor Ivanyos, Marek Karpinski, Nitin Saxena |
Schemes for deterministic polynomial factoring. |
ISSAC |
2009 |
DBLP DOI BibTeX RDF |
grh, schemes, polynomial factoring, representation theory |
| 1 | Travis Gagie, Marek Karpinski, Yakov Nekrich |
Low-Memory Adaptive Prefix Coding. |
DCC |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Warren Schudy |
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. |
STOC |
2009 |
DBLP DOI BibTeX RDF |
Gale-Berlekamp game, correlation and hierarchical clustering, dense instances, linear time approximation schemes, minimum constraint satisfaction, nearest codeword problem, approximation algorithms |
| 1 | Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena |
Trading GRH for algebra: algorithms for factoring polynomials and related structures. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alexander Zelikovsky |
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Warren Schudy |
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Gábor Ivanyos, Marek Karpinski, Nitin Saxena |
Schemes for Deterministic Polynomial Factoring. |
Electronic Colloquium on Computational Complexity (ECCC) |
2008 |
DBLP BibTeX RDF |
|
| 1 | Magnus Bordewich, Martin E. Dyer, Marek Karpinski |
Path coupling using stopping times and counting independent sets and colorings in hypergraphs. |
Random Struct. Algorithms |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Warren Schudy |
Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alexander Zelikovsky |
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Gábor Ivanyos, Marek Karpinski, Nitin Saxena |
Schemes for Deterministic Polynomial Factoring |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Travis Gagie, Marek Karpinski, Yakov Nekrich |
Low-Memory Adaptive Prefix Coding |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Searching for Frequent Colors in Rectangles |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Space-Efficient Multi-Dimensional Range Reporting |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena |
Trading GRH for algebra: algorithms for factoring polynomials and related structures |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski |
The Mixing Time of Glauber Dynamics for Colouring Regular Trees |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Bhaskar DasGupta, Marek Karpinski |
Approximating Transitivity in Directed Networks |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alexander Zelikovsky |
A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two |
CoRR |
2008 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Searching for Frequent Colors in Rectangles. |
CCCG |
2008 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Bhaskar DasGupta, Marek Karpinski |
Approximating Transitive Reductions for Directed Networks. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Yakov Nekrich |
Optimal trade-off for Merkle tree traversal. |
Theor. Comput. Sci. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Marek Karpinski |
1.0957-Approximation Algorithm for Random MAX-3SAT. |
RAIRO - Operations Research |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alexander D. Scott |
Computational complexity of some restricted instances of 3-SAT. |
Discrete Applied Mathematics |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Yakov Nekrich |
Approximating Huffman codes in parallel. |
J. Discrete Algorithms |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Marek Karpinski, Christian Knauer, Andrzej Lingas |
Embedding Point Sets into Plane Graphs of Small Dilation. |
Int. J. Comput. Geometry Appl. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski |
Approximation of Global MAX-CSP Problems. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Marek Karpinski |
Approximation Complexity of Nondense Instances of MAX-CUT. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Marek Karpinski |
Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Marek Karpinski |
On the Sample Complexity of MAX-CUT. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Algorithms for Construction of Optimal and Almost-optimal Length-restricted Codes. |
Parallel Processing Letters |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Lars Engebretsen, Marek Karpinski |
TSP with bounded metrics. |
J. Comput. Syst. Sci. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski |
8/7-approximation algorithm for (1, 2)-TSP. |
SODA |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Magnus Bordewich, Martin E. Dyer, Marek Karpinski |
Stopping Times, Metrics and Approximate Counting. |
ICALP |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski |
8/7-Approximation Algorithm for (1,2)-TSP |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Magnus Bordewich, Martin E. Dyer, Marek Karpinski |
Metric Construction, Stopping Times and Path Coupling. |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Magnus Bordewich, Martin E. Dyer, Marek Karpinski |
Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky |
Improved Approximation Algorithms for the Quality of Service Multicast Tree Problem. |
Algorithmica |
2005 |
DBLP DOI BibTeX RDF |
Quality of service, Approximation algorithm, Multicast, Interconnection network, Steiner tree |
| 1 | Farid M. Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Chris Pollett |
On the computational power of probabilistic and quantum branching program. |
Inf. Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel |
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. |
SIAM J. Comput. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Predecessor Queries in Constant Time?. |
ESA |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Optimal trade-off for merkle tree traversal. |
ICETE |
2005 |
DBLP BibTeX RDF |
|
| 1 | Magnus Bordewich, Martin E. Dyer, Marek Karpinski |
Path Coupling Using Stopping Times. |
FCT |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Annette Ebbers-Baumann, Ansgar Grüne, Marek Karpinski, Rolf Klein, Christian Knauer, Andrzej Lingas |
Embedding Point Sets into Plane Graphs of Small Dilation. |
ISAAC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Cristina Bazgan, Marek Karpinski |
On the Complexity of Global Constraint Satisfaction. |
ISAAC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Yakov Nekrich |
Algorithms for Construction of Optimal and Almost-Optimal Length-Restricted Codes. (PDF / PS) |
DCC |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala |
Tensor decomposition and approximation schemes for constraint satisfaction problems. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
approximation scheme, tensor decomposition |
| 1 | Marek Karpinski, Yakov Nekrich |
A Note on Traversing Skew Merkle Trees |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Yakov Nekrich |
Optimal Trade-Off for Merkle Tree Traversal |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alexander D. Scott |
Computational Complexity of Some Restricted Instances of 3SAT |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Marek Karpinski, Lawrence L. Larmore, Yakov Nekrich |
Work-Efficient Algorithms For The Construction Of Length-Limited Huffman Codes. |
Parallel Processing Letters |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas |
Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs. |
Fundam. Inform. |
2004 |
DBLP BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon |
Approximation schemes for Metric Bisection and partitioning. |
SODA |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski |
Improved Approximation Lower Bounds on Small Occurrence Optimization |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alex D. Scott |
Approximation Hardness of Short Symmetric Instances of MAX-3SAT |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski |
Approximability of Hypergraph Minimum Bisection |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Piotr Berman, Marek Karpinski, Alex D. Scott |
Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT |
Electronic Colloquium on Computational Complexity (ECCC) |
2003 |
DBLP BibTeX RDF |
|
| 1 | Farid M. Ablayev, Marek Karpinski |
A lower bound for integer multiplication on randomized ordered read-once branching programs. |
Inf. Comput. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski |
Polynomial time approximation schemes for dense instances of minimum constraint satisfaction. |
Random Struct. Algorithms |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski |
Random sampling and approximation of MAX-CSPs. |
J. Comput. Syst. Sci. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Marek Karpinski, Ion I. Mandoiu, Alexander Olshevsky, Alexander Zelikovsky |
Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem. |
WADS |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani |
Approximation schemes for clustering problems. |
STOC |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Susanne Albers, Marek Karpinski |
Randomized splay trees: Theoretical and experimental results. |
Inf. Process. Lett. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Wenceslas Fernandez de la Vega, Marek Karpinski |
A Polynomial Time Approximation Scheme for Subdense MAX-CUT |
Electronic Colloquium on Computational Complexity (ECCC) |
2002 |
DBLP BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")