Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
 
conference paper

Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems

Eisenbrand, Friedrich  
•
Rohwedder, Lars  
•
Węgrzycki, Karol
October 27, 2024
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
65th Annual Symposium on Foundations of Computer Science

We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from ${-\Delta,\ldots,\Delta}$ or more generally $m$-dimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by $\Delta$ and $m$ for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in ${0,1}$, or arbitrary $\Delta$ and $m=1$. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1109/focs61266.2024.00100
ArXiv ID

2404.03747v2

Author(s)
Eisenbrand, Friedrich  

EPFL

Rohwedder, Lars  
Węgrzycki, Karol

Saarland University

Date Issued

2024-10-27

Publisher

IEEE

Published in
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
DOI of the book
10.1109/FOCS61266.2024
ISBN of the book

979-8-3315-1674-1

Start page

1610

End page

1620

Subjects

Computer Science - Data Structures and Algorithms

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent acronymEvent placeEvent date
65th Annual Symposium on Foundations of Computer Science

FOCS

Chicago, United States

2024-10-27 - 2024-10-30

FunderFunding(s)Grant NumberGrant URL

European Research Council

850979

Available on Infoscience
March 5, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/247459
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés