Concept
Vertex cover
Publications associées (121)
ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS
We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...
Ottawa2023Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
IEEE COMPUTER SOC2022Algebra and geometry of link homology Lecture notes from the IHES 2021 Summer School
These notes cover the lectures of the first named author at 2021 IHES Summer School on "Enumerative Geometry, Physics and Representation Theory" with additional details and references. They cover the definition of Khovanov-Rozansky triply graded homology, ...
WILEY2022Chance-Constrained Trajectory Planning With Multimodal Environmental Uncertainty
We tackle safe trajectory planning under Gaussian mixture model (GMM) uncertainty. Specifically, we use a GMM to model the multimodal behaviors of obstacles' uncertain states. Then, we develop a mixed-integer conic approximation to the chance-constrained t ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022How to Match in Modern Computational Settings
Buddhima Ruwanmini Gamlath Gamlath Ralalage
This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models called query-commit and price-of-information where the algori ...
EPFL2021Adaptive majority problems for restricted query graphs and for weighted sets
Abhishek Methuku, Balázs Keszegh
Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...
ELSEVIER2021Wasserstein Adversarial Regularization for learning with label noise
Devis Tuia, Sylvain Lobry, Nicolas Courty
Noisy labels often occur in vision datasets, especially when they are obtained from crowdsourcing or Web scraping. We propose a new regularization method, which enables learning robust classifiers in presence of noisy data. To achieve this goal, we propose ...
2021