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
Loading...
Thumbnail Image
Name

2404.03747

Type

Main Document

Version

Submitted version (Preprint)

Access type

openaccess

License Condition

CC BY

Size

301.17 KB

Format

Unknown

Checksum (MD5)

56dd3726cc5f8302db2588d54948a097

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