Marek Karpinski

From ScholarWiki
Jump to: navigation, search

Contents

DESCRIPTION

(please update this section)

Marek Karpinski frequently used research question: steiner tree problem; steiner tree; methodology(algorithm): quality of service;

LIST OF PAPERS about "steiner tree problem"

1. 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY - ECCC, 2008, Piotr Berman Marek Karpinski Alexander Zelikovsky

2. Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem WORKSHOP ON ALGORITHMS AND DATA STRUCTURES - WADS, 2003, Marek Karpinski Ion I. Mandoiu Alexander Olshevsky Alexander Zelikovsky

3. Improved Approximation Algorithms for the Quality of Service Steiner Tree Problem , 0, Marek Karpinski I. Mandoiu Alexander Olshevsky

4. New Approximation Algorithms for the Steiner Tree Problems ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY - ECCC, 1995, Marek Karpinski Alexander Zelikovsky

LIST OF PAPERS about "steiner tree"

1. A Factor 3/2 Approximation for Generalized Steiner Tree Problem with Distances One and Two COMPUTING RESEARCH REPOSITORY - CORR, 2008, Piotr Berman Marek Karpinski Alexander Zelikovsky

LIST OF PAPERS about "sorting by reversals"

1. On Some Tighter Inapproximability Results ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY - ECCC, 0, Piotr Berman Marek Karpinski

2. On Some Tighter Inapproximability Results ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY - ECCC, 1998, Piotr Berman Marek Karpinski

LIST OF PAPERS about "polynomial time"

1. 8/7-Approximation Algorithm for (1,2)-TSP ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY - ECCC, 2005, Piotr Berman Marek Karpinski

LIST OF PAPERS about "binary search"

1. Randomized splay trees: Theoretical and experimental results INFORMATION PROCESSING LETTERS - IPL, 2002, Susanne Albers Marek Karpinski

LIST OF PAPERS about "triangle inequality"

1. Approximation Hardness of TSP with Bounded Metrics ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY - ECCC, 0, Lars Engebretsen Marek Karpinski

LIST OF PAPERS about "semidefinite relaxation"

1. Improved Approximation of MAX-CUT on Graphs of Bounded Degree ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY - ECCC, 0, Uriel Feige Marek Karpinski Michael Langberg

LIST OF PAPERS about "minimum degree"

1. Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems JOURNAL OF COMPUTER AND SYSTEM SCIENCES - JCSS, 1999, Sanjeev Arora David R. Karger Marek Karpinski

LIST OF PAPERS about "competitive ratio"

1. On-line Load Balancing for Related Machines WORKSHOP ON ALGORITHMS AND DATA STRUCTURES - WADS, 1997, Piotr Berman Moses Charikar Marek Karpinski

LIST OF PAPERS about "pattern matching"

1. An Efficient Pattern-Matching Algorithm for Strings with Short Descriptions NORDIC JOURNAL OF COMPUTING - NJC, 1997, Marek Karpinski Wojciech Rytter Ayumi Shinohara

LIST OF PAPERS about "hamiltonian cycle"

1. On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs JOURNAL OF ALGORITHMS - JAL, 1993, Elias Dahlhaus Péter Hajnal Marek Karpinski

LIST OF PAPERS about "circuit complexity"

1. Simulating threshold circuits by majority circuits ACM SYMPOSIUM ON THEORY OF COMPUTING - STOC, 1993, Mikael Goldmann Marek Karpinski

LIST OF PAPERS about "maximal independent set"

1. An Efficient Parallel Algorithm for Computing a Maximal Independent Set in a Hypergraph of Dimension 3 INFORMATION PROCESSING LETTERS - IPL, -313, Elias Dahlhaus Marek Karpinski Pierre Kelsen

LIST OF PAPERS about "finite field"

1. Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields SIAM JOURNAL ON COMPUTING - SIAMCOMP, 1990, Dima Grigoriev Marek Karpinski Michael F. Singer

LIST OF PAPERS (other)

Subtree Isomorphism is NC Reducible to Bipartite Perfect Matching INFORMATION PROCESSING LETTERS - IPL, 1989, Andrzej Lingas Marek Karpinski

Simulating threshold circuits by majority circuits ACM SYMPOSIUM ON THEORY OF COMPUTING - STOC, -560, Mikael Goldmann Marek Karpinski

Approximation Hardness of Short Symmetric Instances of MAX-3SAT ELECTRONIC COLLOQUIUM ON COMPUTATIONAL COMPLEXITY - ECCC, 2003, Piotr Berman Marek Karpinski Alex D. Scott

Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE - STACS, 2001, Klaus Jansen Marek Karpinski Andrzej Lingas Eike Seidel

An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph THEORETICAL COMPUTER SCIENCE - TCS, 1994, Elias Dahlhaus Marek Karpinski

On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields THEORETICAL COMPUTER SCIENCE - TCS, 1991, Michael Clausen Johannes Grabmeier Marek Karpinski

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract) IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE - FOCS, 1987, Dima Grigoriev Marek Karpinski

A note on approximating Max-Bisection on regular graphs INFORMATION PROCESSING LETTERS - IPL, 2001, Uriel Feige Marek Karpinski Michael Langberg

On the Monte Carlo Space Constructible Functions and Seperation Results for Probabilistic Complexity Classes INFORMATION AND COMPUTATION/INFORMATION AND CONTROL - IANDC, 1987, Marek Karpinski Rutger Verbeek

On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts COMBINATORIAL PATTERN MATCHING - CPM, 1997, Piotr Berman Marek Karpinski Lawrence L. Larmore Wojciech Plandowski Wojciech Rytter

Pattern-Matching for Strings with Short Descriptions COMBINATORIAL PATTERN MATCHING - CPM, 1995, Marek Karpinski Wojciech Rytter Ayumi Shinohara

Computational Complexity of Sparse Rational Interpolation SIAM JOURNAL ON COMPUTING - SIAMCOMP, 1994, Dima Grigoriev Marek Karpinski Michael F. Singer

On Some Approximation Problems Concerning Sparse Polynomials over Finite Fields THEORETICAL COMPUTER SCIENCE - TCS, 1996, Marek Karpinski Igor Shparlinski

Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks JOURNAL OF COMPUTER AND SYSTEM SCIENCES - JCSS, 1997, Marek Karpinski Angus Macintyre

New Approximation Algorithms for the Steiner Tree Problems JOURNAL OF COMBINATORIAL OPTIMIZATION - JCO, 1997, Marek Karpinski Alexander Zelikovsky

On the Approximation Hardness of Dense TSP and Other Path Problems INFORMATION PROCESSING LETTERS - IPL, 1999, Wenceslas Fernandez De La Vega Marek Karpinski

Personal tools
Namespaces
Variants
Actions
Navigation
Toolbox