Publications associées à The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ_1

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

Charles Babbage Res Ctr2016

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Ola Nils Anders Svensson, Abbas Bazzi

The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regevproved that the problem is NP-hard to approximate within a factor2 - ∈, assuming the Unique Games Conjecture (UGC). This is tig ...

IEEE Computer Society2015

Remarks on Schur's conjecture

János Pach, Filip Moric

Let P be a set of n > d points in for d >= 2. It was conjectured by Zvi Schur that the maximum number of (d-1)-dimensional regular simplices of edge length diam(P), whose every vertex belongs to P, is n. We prove this statement under the condition that any ...

Elsevier Science Bv2015

Cross-Intersecting Families of Vectors

János Pach, Gábor Tardos

Given a sequence of positive integers , let denote the family of all sequences of positive integers such that for all . Two families of sequences (or vectors), , are said to be -cross-intersecting if no matter how we select and , there are at least distinc ...

Springer Japan Kk2015

Approximating ATSP by Relaxing Connectivity

Ola Nils Anders Svensson

The standard LP relaxation of the asymmetric traveling salesman problem has been conjectured to have a constant integrality gap in the metric case. We prove this conjecture when restricted to shortest path metrics of node-weighted digraphs. Our arguments a ...

IEEE Computer Society2015

Codimension one stability of the catenoid under the vanishing mean curvature flow in Minkowski space

Joachim Krieger, Roland Donninger, Willie Wai Yeung Wong

We study time-like hypersurfaces with vanishing mean curvature in the (3+1) dimensional Minkowski space, which are the hyperbolic counterparts to minimal embeddings of Riemannian manifolds. The catenoid is a stationary solution of the associated Cauchy pro ...

Duke Univ Press2015

Affine congruences and rational points on a certain cubic surface

Pierre Francis André Le Boudec

We establish estimates for the number of solutions of certain affine congruences. These estimates are then used to prove Manin's conjecture for a cubic surface split over Q whose singularity type is D-4. This improves on a result of Browning and answers a ...

Mathematical Science Publ2014

Overview of the Geometries of Shape Spaces and Diffeomorphism Groups

Martins Bruveris, Martin Bauer

This article provides an overview of various notions of shape spaces, including the space of parametrized and unparametrized curves, the space of immersions, the diffeomorphism group and the space of Riemannian metrics. We discuss the Riemannian metrics th ...

Springer Verlag2014

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ_1

Graph Chatbot

Chattez avec Graph Search

Strengths and Limitations of Linear Programming Relaxations

Independence number of generalized Petersen graphs

Bi-Jacobi Fields And Riemannian Cubics For Left-Invariant SO(3)

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Remarks on Schur's conjecture

Cross-Intersecting Families of Vectors

Approximating ATSP by Relaxing Connectivity

Codimension one stability of the catenoid under the vanishing mean curvature flow in Minkowski space

Affine congruences and rational points on a certain cubic surface

Overview of the Geometries of Shape Spaces and Diffeomorphism Groups

Affine congruences and rational points on a certain cubic surface

Overview of the Geometries of Shape Spaces and Diffeomorphism Groups

Cross-Intersecting Families of Vectors

Bi-Jacobi Fields And Riemannian Cubics For Left-Invariant SO(3)

Independence number of generalized Petersen graphs

Strengths and Limitations of Linear Programming Relaxations

No Small Linear Program Approximates Vertex Cover within a Factor 2 - e

Remarks on Schur's conjecture

Approximating ATSP by Relaxing Connectivity

Codimension one stability of the catenoid under the vanishing mean curvature flow in Minkowski space