Cette recherche s'applique uniquement aux ressources en bibliothèque.
206 résultats
Trier par:
Ajouter à la liste:
Étendre à toutes les références (sans texte intégral)
    • Article
    Sélectionner

    Removing Degeneracy in LP-Type Problems Revisited

    Matoušek, Jiří
    Discrete & Computational Geometry. - 2009/42/4/517-526
    Disponible
    Plus…
    Titre: Removing Degeneracy in LP-Type Problems Revisited
    Auteur: Matoušek, Jiří
    Description: LP-type problems is a successful axiomatic framework for optimization problems capturing, e.g., linear programming and the smallest enclosing ball of a point set. In Matoušek and Škovroň (Theory Comput. 3:159-177, 2007), it is proved that in order to remove degeneracies of an LP-type problem, we sometimes have to increase its combinatorial dimension by a multiplicative factor of at least 1+ε with a certain small positive constant ε. The proof goes by checking the unsolvability of a system of linear inequalities, with several pages of calculations. Here by a short topological argument we prove that the dimension sometimes has to increase at least twice. We also construct 2-dimensional LP-type problems with −∞ for which removing degeneracies forces arbitrarily large dimension increase
    Publication en relation: Discrete & Computational Geometry. - 2009/42/4/517-526
    Document hôte: Discrete & Computational Geometry
    Identifiant: 10.1007/s00454-008-9085-7 (DOI)

    • Article
    Sélectionner

    A Combinatorial Proof of Kneser'sConjecture*

    Matoušek, Jiří
    Combinatorica. - 2004/24/1/163-170
    Disponible
    Plus…
    Titre: A Combinatorial Proof of Kneser'sConjecture*
    Auteur: Matoušek, Jiří
    Description: Kneser's conjecture, first proved by Lovász in 1978, states that the graph with all k-element subsets of {1, 2, . . . , n} as vertices and with edges connecting disjoint sets has chromatic number n−2k+2. We derive this result from Tucker's combinatorial lemma on labeling the vertices of special triangulations of the octahedral ball. By specializing a proof of Tucker's lemma, we obtain self-contained purely combinatorial proof of Kneser's conjecture
    Publication en relation: Combinatorica. - 2004/24/1/163-170
    Document hôte: Combinatorica
    Identifiant: 10.1007/s00493-004-0011-1 (DOI)

    • Article
    Sélectionner

    Blocking Visibility for Points in General Position

    Matoušek, Jiří
    Discrete & Computational Geometry. - 2009/42/2/219-223
    Disponible
    Plus…
    Titre: Blocking Visibility for Points in General Position
    Auteur: Matoušek, Jiří
    Sujet: Visibility - Visibility-blocking set - Behrend's construction
    Description: For a finite set P in the plane, let b(P) be the smallest possible size of a set Q, Q∩P=∅, such that every segment with both endpoints in P contains at least one point of Q. We raise the problem of estimating b(n), the minimum of b(P) over all n-point sets P with no three points collinear. We review results providing bounds on b(n) and mention some additional observations
    Publication en relation: Discrete & Computational Geometry. - 2009/42/2/219-223
    Document hôte: Discrete & Computational Geometry
    Identifiant: 10.1007/s00454-009-9185-z (DOI)

    • Article
    Sélectionner

    Near-Optimal Separators in String Graphs

    MATOUŠEK, JIŘÍ
    Combinatorics, Probability and Computing. - 2014/23/1/135-139
    Disponible
    Plus…
    Titre: Near-Optimal Separators in String Graphs
    Auteur: MATOUŠEK, JIŘÍ
    Sujet: Primary 05C62 - Secondary 05C10
    Description: Let G be a string graph (an intersection graph of continuous arcs in the plane) with m edges. Fox and Pach proved that G has a separator consisting of $O(m^{3/4}\sqrt{\log m})$ vertices, and they conjectured that the bound of $O(\sqrt m)$ actually holds. We obtain separators with $O(\sqrt m \,\log m)$ vertices
    Publication en relation: Combinatorics, Probability and Computing. - 2014/23/1/135-139
    Document hôte: Combinatorics, Probability and Computing
    Identifiant: 10.1017/S0963548313000400 (DOI)

    • Article
    Sélectionner

    New Constructions of Weak ε-Nets

    Matousek, Jirí
    Wagner, Uli
    Discrete & Computational Geometry. - 2004/32/2/195-206
    Disponible
    Plus…
    Titre: New Constructions of Weak ε-Nets
    Auteur: Matousek, Jirí
    Contributeur: Wagner, Uli
    Description: A finite set $N \subset \R^d$ is a {\em weak $\eps$-net} for an $n$-point set $X\subset \R^d$ (with respect to convex sets) if $N$ intersects every convex set $K$ with $|K\,\cap\,X|\geq \eps n$. We give an alternative, and arguably simpler, proof of the fact, first shown by Chazelle et al., that every point set $X$ in $\R^d$ admits a weak $\eps$-net of cardinality $O(\eps^{-d}\polylog(1/\eps))$. Moreover, for a number of special point sets (e.g., for points on the moment curve), our method gives substantially better bounds. The construction yields an algorithm to construct such weak $\eps$-nets in time $O(n\ln(1/\eps))$
    Publication en relation: Discrete & Computational Geometry. - 2004/32/2/195-206
    Document hôte: Discrete & Computational Geometry
    Identifiant: 10.1007/s00454-004-1116-4 (DOI)

    • Article
    Sélectionner

    A highly non-smooth norm on Hilbert space

    Matoušek, Jiří
    Matoušková, Eva
    Israel Journal of Mathematics. - 1999/112/1/1-27
    Disponible
    Plus…
    Titre: A highly non-smooth norm on Hilbert space
    Auteur: Matoušek, Jiří
    Contributeur: Matoušková, Eva
    Description: We show that there exists a familyF of unit balls in the Hilbert spacel 2 such that ∪F is dense inl 2 but the complement of ∪F is large in the sense of measure. In an appendix, we present a considerable simplification of the proof due to Preiss. As a corollary, we prove that there is an equivalent normp onl 2 such that the set of points wherep is Fréchet differentiable is Aronszajn null. This disproves a conjecture of Borwein and Noll in a very strong sense
    Publication en relation: Israel Journal of Mathematics. - 1999/112/1/1-27
    Document hôte: Israel Journal of Mathematics
    Identifiant: 10.1007/BF02773476 (DOI)

    • Plusieurs versions

    The number of unit distances is almost linear for most norms

    Matoušek, Jiří
    Advances in Mathematics, 2011, Vol.226(3), pp.2618-2628 [Revue évaluée par les pairs]

    • Article
    Sélectionner

    String graphs and separators

    Matoušek, Jiří
    arXiv.org, Apr 25, 2014
    © ProQuest LLC All rights reserved, Engineering Database, Publicly Available Content Database, ProQuest Engineering Collection, ProQuest Technology Collection, ProQuest SciTech Collection, Materials Science & Engineering Database, ProQuest Central (new), ProQuest Central Korea, SciTech Premium Collection, Technology Collection, ProQuest Central Essentials, ProQuest One Academic, Engineering Collection (ProQuest)
    Disponible
    Plus…
    Titre: String graphs and separators
    Auteur: Matoušek, Jiří
    Contributeur: Matoušek, Jiří (pacrepositoryorg)
    Sujet: Separators ; Graphs ; Graphical Representations ; Combinatorics ; Computational Geometry
    Description: String graphs, that is, intersection graphs of curves in the plane, have been studied since the 1960s. We provide an expository presentation of several results, including very recent ones: some string graphs require an exponential number of crossings in every string representation; exponential number is always sufficient; string graphs have small separators; and the current best bound on the crossing number of a graph in terms of the pair-crossing number. For the existence of small separators, unwrapping the complete proof include generally useful results on approximate flow-cut dualities.
    Fait partie de: arXiv.org, Apr 25, 2014
    Identifiant: 2331-8422 (E-ISSN)

    • Article
    Sélectionner

    String graphs and separators

    Matoušek, Jiří
    Cornell University
    Disponible
    Plus…
    Titre: String graphs and separators
    Auteur: Matoušek, Jiří
    Sujet: Mathematics - Combinatorics ; Computer Science - Computational Geometry ; 05c62
    Description: String graphs, that is, intersection graphs of curves in the plane, have been studied since the 1960s. We provide an expository presentation of several results, including very recent ones: some string graphs require an exponential number of crossings in every string representation; exponential number is always sufficient; string graphs have small separators; and the current best bound on the crossing number of a graph in terms of the pair-crossing number. For the existence of small separators, unwrapping the complete proof include generally useful results on approximate flow-cut dualities. Comment: Expository paper based on course notes
    Identifiant: 1311.5048 (ARXIV ID)

    • Article
    Sélectionner

    A Geometric Proof of the Colored Tverberg Theorem

    Matoušek, Jiří
    Tancer, Martin, Wagner, Uli
    Discrete & Computational Geometry. - 2012/47/2/245-265
    Disponible
    Plus…
    Titre: A Geometric Proof of the Colored Tverberg Theorem
    Auteur: Matoušek, Jiří
    Contributeur: Tancer, Martin; Wagner, Uli
    Sujet: Convexity - Tverberg's theorem - Colored Tverberg theorem - Continuous motion
    Description: The colored Tverberg theorem asserts that for every d and r there exists t=t(d,r) such that for every set C⊂ℝ d of cardinality (d+1)t, partitioned into t-point subsets C 1,C 2, ,C d+1 (which we think of as color classes; e.g., the points of C 1 are red, the points of C 2 blue, etc.), there exist r disjoint sets R 1,R 2, ,R r ⊆C that are rainbow, meaning that |R i ∩C j |≤1 for every i,j, and whose convex hulls all have a common point. All known proofs of this theorem are topological. We present a geometric version of a recent beautiful proof by Blagojević, Matschke, and Ziegler, avoiding a direct use of topological methods. The purpose of this de-topologization is to make the proof more concrete and intuitive, and accessible to a wider audience
    Publication en relation: Discrete & Computational Geometry. - 2012/47/2/245-265
    Document hôte: Discrete & Computational Geometry
    Identifiant: 10.1007/s00454-011-9368-2 (DOI)