Demo Data from SIGIR 2026 / reviewers in the wild / expert
Miroslav Chlebík
dblp:55/5774
· DBLP profile ↗
18ranked-venue papers
18as first author
0since 2021 · last 2019
0000-0001-8137-479XORCID · verified
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 18 · 18 first-author
Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.
| Theoretical computer science
2 papers |
Computational complexity · 42% Computational geometry · 33% Graph algorithms and graph theory · 25% |
Topics — the 4 heaviest of 4, each with the papers that count most for it
| Topic | Weight | Papers | Last | Evidence papers |
|---|---|---|---|---|
Computational complexity
hardness of approximation |
0.1 | 2 | 2008 | Approximation hardness of dominating set problems in bounded degree graphs · Inf. Comput. 2008 Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes · SODA 2005 |
Graph algorithms and graph theory
dominating set |
0.1 | 1 | 2008 | Approximation hardness of dominating set problems in bounded degree graphs · Inf. Comput. 2008 |
Computational geometry
intersection graphs |
0.1 | 1 | 2005 | Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes · SODA 2005 |
Computational geometry › intersection graphs
rectangle intersection graphs |
0.1 | 1 | 2005 | Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes · SODA 2005 |
Methods — techniques the papers use, named apart from their topics
reduction · 0.1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2019 | Approximation Hardness of Travelling Salesman via Weighted Amplifiers
Miroslav Chlebík, Janka Chlebíková |
COCOON | 1 |
| 2014 | Connection between conjunctive capacity and structural properties of graphs
Miroslav Chlebík, Janka Chlebíková |
Theor. Comput. Sci. | 1 |
| 2013 | On the Conjunctive Capacity of Graphs
Miroslav Chlebík, Janka Chlebíková |
COCOON | 1 |
| 2008 | Crown reductions for the Minimum Weighted Vertex Cover problem
Miroslav Chlebík, Janka Chlebíková |
Discret. Appl. Math. | 1 |
| 2008 | Approximation hardness of dominating set problems in bounded degree graphs
Miroslav Chlebík, Janka Chlebíková |
Inf. Comput. | 1 |
| 2008 | The Steiner tree problem on graphs: Inapproximability results
Miroslav Chlebík, Janka Chlebíková |
Theor. Comput. Sci. | 1 |
| 2007 | Minimum 2SAT-DELETION: Inapproximability results and relations to Minimum Vertex Cover
Miroslav Chlebík, Janka Chlebíková |
Discret. Appl. Math. | 1 |
| 2007 | The Complexity of Combinatorial Optimization Problems on d-Dimensional BoxesabstractThe MAXIMUM INDEPENDENT SET problem in d‐box graphs, i.e., in intersection graphs of axis‐parallel rectangles in $\mathbb{R}^d$, is known to be NP‐hard for any fixed $d\geq 2$. A challenging open problem is that of how closely the solution can be approximated by a polynomial time algorithm. For the restricted case of d‐boxes with bounded aspect ratio a PTAS exists [T. Erlebach, K. Jansen, and E. Seidel, SIAM J. Comput., 34 (2005), pp. 1302–1323]. In the general case no polynomial time algorithm with approximation ratio $o(\log^{d-1} n)$ for a set of n d‐boxes is known. In this paper we prove APX‐hardness of the MAXIMUM INDEPENDENT SET problem in d‐box graphs for any fixed $d\geq 3$. We give an explicit lower bound $\frac{245}{244}$ on efficient approximability for this problem unless $\PP=\text{\rm NP}$. Additionally, we provide a generic method how to prove APX‐hardness for other graph optimization problems in d‐box graphs for any fixed $d\geq 3$. Miroslav Chlebík, Janka Chlebíková |
SIAM J. Discret. Math. | 1 |
| 2006 | Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
Miroslav Chlebík, Janka Chlebíková |
CIAC | 1 |
| 2006 | Hard coloring problems in low degree planar bipartite graphs
Miroslav Chlebík, Janka Chlebíková |
Discret. Appl. Math. | 1 |
| 2006 | Complexity of approximating bounded variants of optimization problems
Miroslav Chlebík, Janka Chlebíková |
Theor. Comput. Sci. | 1 |
| 2005 | Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes
Miroslav Chlebík, Janka Chlebíková |
SODA | 1 |
| 2004 | Approximation Hardness of Dominating Set Problems
Miroslav Chlebík, Janka Chlebíková |
ESA | 1 |
| 2004 | On Approximation Hardness of the Minimum 2SAT-DELETION Problem
Miroslav Chlebík, Janka Chlebíková |
MFCS | 1 |
| 2004 | On Approximability of the Independent Set Problem for Low Degree Graphs
Miroslav Chlebík, Janka Chlebíková |
SIROCCO | 1 |
| 2003 | Approximation Hardness for Small Occurrence Instances of NP-Hard Problems
Miroslav Chlebík, Janka Chlebíková |
CIAC | 1 |
| 2003 | Inapproximability Results for Bounded Variants of Optimization Problems
Miroslav Chlebík, Janka Chlebíková |
FCT | 1 |
| 2003 | Approximation Hardness of Minimum Edge Dominating Set and Minimum Maximal Matching
Miroslav Chlebík, Janka Chlebíková |
ISAAC | 1 |