Detail page

Knowledge Web

Person

Marek Karpiński (1948-)

Mathematiker

Name	Marek Karpiński
Time	1948- (Date of birth and death)
Place	Polen Deutschland
Profession	Mathematiker (characteristic profession) Informatiker
Variant	M. Karpinski
Related	Rheinische Friedrich-Wilhelms-Universität Bonn. Institut für Informatik
Source	Wikipedia: https://de.wikipedia.org/w/index.php?title=Marek_Karpi%C5%84ski&oldid=207831150 (Stand: 19.10.2021)
Record type	Person
GND-Identifier	115476032
Record ID	115476032
Involved in show all Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields A QPTAS for the base of the number of crossing-free structures of a planar point set Inapproximability of dominating set on power law graphs On the approximability of independent set problem on power law graphs On the complexity of nondeterministically testable hypergraph parameters Polynomial interpolation and identity testing from high powers over finite fields Towards better inapproximability bounds for TSP : a challenge of global dependencies A QPTAS for the base of the number of triangulations of a planar point set Complexity of nondeterministic graph parameter testing Generalized Wong sequences and their applications to Edmonds' problems Limits of CSP problems and efficient parameter testing A compendium on Steiner Tree Problems Algorithmic perspectives of network transitive reduction problems and their applications to synthesis and analysis of biological networks Approximation hardness of graphic TSP on cubic graphs Improved inapproximability results for the shortest superstring and the bounded metric TSP Inapproximability of dominating set in power law graphs New inapproximability bounds for TSP Approximate counting of matchings in sparse hypergraphs Approximate counting of matchings in sparse uniform hypergraphs Improved approximation lower bounds for vertex cover on power law graphs and some generalizations Improved inapproximability results for the shortest superstring and related problems On approximation lower bounds for TSP with bounded metrics Optimal cuts and bisections on the real line polynomial time Optimal cuts and partitions in tree metrics in polynomial time Approximation schemes for the Betweenness problem in tournaments and related ranking problems Improved lower bounds for the shortest superstring and related problems Tight approximation bounds for vertex cover on dense k-partite hypergraphs Computational complexity of the perfect matching problem in hypergraphs with subcritical density Exact and approximation algorithms for geometric and capacitatived set cover problems Faster algorithms for feedback arc set tournament, Kemeny Rank aggrgation and betweenness tournament Range reporting for moving points on a grid Approximating transitive reductions for directed networks Exact and approximation algorithms for geometric and capacitated set cover problems with applications 1.25 approximation algorithm for the Steiner tree problem with distances one and two Approximating transitivity in directed networks Linear time approximation schemes for the Gale Berlekamp game and related minimization problems Schemes for deterministic polynomial factoring Searching for frequent colors in rectangles Space-efficient multi-dimensional range reporting The mixing rate of Glauber dynamics for Smpling colourings of regular trees with few colours A fast algorithm for adaptive prefix coding Complexity of computing functions by quantum branching programs Predecessor queries in constant time? Trading tensors for cloning : constant time approximation schemes for metric MAX-CSP 8/7-approximation algorithm for (1,2)-TSP Approximation complexity of nondense instances of MAX-CUT Approximation of global MAX CSP problems On the sample complexity of MAX-CUT Stopping times, metric and approximate counting Trading tensors for cloning : constant time approximation schemes for metric MAX-CSP 8/7-approximation algorithm for (1,2)-TSP Algorithms for construction of optimal and almost optimal length restricted codes Dynamic planar orthogonal range reporting Fast data structures for orthogonal range reporting Metric construction, stopping times and path coupling On the complexity of global constraint satisfaction Path coupling using stopping times and counting independent sets and colouring in hypergraphs Predecessor queries in constant time? TSP with bounded metrics: approximation hardness for the (1,2) case TSP with bounded metrics: stronger approximation hardness

Please note

The beta version does not yet contain all functions and information of the DNB portal catalogue. If you are missing information or want to order a medium, please visit the page in the DNB portal catalogue via the following link:

Katalog der Deutschen Nationalbibliothek

Marek Karpiński (1948-)

Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields

A QPTAS for the base of the number of crossing-free structures of a planar point set

Inapproximability of dominating set on power law graphs

On the approximability of independent set problem on power law graphs

On the complexity of nondeterministically testable hypergraph parameters

Polynomial interpolation and identity testing from high powers over finite fields

Towards better inapproximability bounds for TSP : a challenge of global dependencies

A QPTAS for the base of the number of triangulations of a planar point set

Complexity of nondeterministic graph parameter testing

Generalized Wong sequences and their applications to Edmonds' problems

Limits of CSP problems and efficient parameter testing

A compendium on Steiner Tree Problems

Algorithmic perspectives of network transitive reduction problems and their applications to synthesis and analysis of biological networks

Approximation hardness of graphic TSP on cubic graphs

Improved inapproximability results for the shortest superstring and the bounded metric TSP

Inapproximability of dominating set in power law graphs

New inapproximability bounds for TSP

Approximate counting of matchings in sparse hypergraphs

Approximate counting of matchings in sparse uniform hypergraphs

Improved approximation lower bounds for vertex cover on power law graphs and some generalizations

Improved inapproximability results for the shortest superstring and related problems

On approximation lower bounds for TSP with bounded metrics

Optimal cuts and bisections on the real line polynomial time

Optimal cuts and partitions in tree metrics in polynomial time

Approximation schemes for the Betweenness problem in tournaments and related ranking problems

Improved lower bounds for the shortest superstring and related problems

Tight approximation bounds for vertex cover on dense k-partite hypergraphs

Computational complexity of the perfect matching problem in hypergraphs with subcritical density

Exact and approximation algorithms for geometric and capacitatived set cover problems

Faster algorithms for feedback arc set tournament, Kemeny Rank aggrgation and betweenness tournament

Range reporting for moving points on a grid

Approximating transitive reductions for directed networks

Exact and approximation algorithms for geometric and capacitated set cover problems with applications

1.25 approximation algorithm for the Steiner tree problem with distances one and two

Approximating transitivity in directed networks

Linear time approximation schemes for the Gale Berlekamp game and related minimization problems

Schemes for deterministic polynomial factoring

Searching for frequent colors in rectangles

Space-efficient multi-dimensional range reporting

The mixing rate of Glauber dynamics for Smpling colourings of regular trees with few colours

A fast algorithm for adaptive prefix coding

Complexity of computing functions by quantum branching programs

Predecessor queries in constant time?

Trading tensors for cloning : constant time approximation schemes for metric MAX-CSP

8/7-approximation algorithm for (1,2)-TSP

Approximation complexity of nondense instances of MAX-CUT

Approximation of global MAX CSP problems

On the sample complexity of MAX-CUT

Stopping times, metric and approximate counting

Trading tensors for cloning : constant time approximation schemes for metric MAX-CSP

8/7-approximation algorithm for (1,2)-TSP

Algorithms for construction of optimal and almost optimal length restricted codes

Dynamic planar orthogonal range reporting

Fast data structures for orthogonal range reporting

Metric construction, stopping times and path coupling

On the complexity of global constraint satisfaction

Path coupling using stopping times and counting independent sets and colouring in hypergraphs

Predecessor queries in constant time?

TSP with bounded metrics: approximation hardness for the (1,2) case

TSP with bounded metrics: stronger approximation hardness