Algebraic Algorithms for Matching and Matroid Problems
We present new algebraic approaches for two well-known combinatorial problems: nonbipartite matching and matroid intersection. Our work yields new randomized algorithms that exceed or match the efficiency of existing algorithms. For nonbipartite matching, we obtain a simple, purely algebraic algorit...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2010
|
| Online Access: | http://hdl.handle.net/1721.1/52443 |
| _version_ | 1826215648285425664 |
|---|---|
| author | Harvey, Nicholas J. A. |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Harvey, Nicholas J. A. |
| author_sort | Harvey, Nicholas J. A. |
| collection | MIT |
| description | We present new algebraic approaches for two well-known combinatorial problems: nonbipartite matching and matroid intersection. Our work yields new randomized algorithms that exceed or match the efficiency of existing algorithms. For nonbipartite matching, we obtain a simple, purely algebraic algorithm with running time $O(n^\omega)$ where $n$ is the number of vertices and $\omega$ is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (2004). For matroid intersection, our algorithm has running time $O(nr^{\omega-1})$ for matroids with $n$ elements and rank $r$ that satisfy some natural conditions. |
| first_indexed | 2024-09-23T16:37:15Z |
| format | Article |
| id | mit-1721.1/52443 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:37:15Z |
| publishDate | 2010 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/524432022-10-02T08:27:46Z Algebraic Algorithms for Matching and Matroid Problems Harvey, Nicholas J. A. Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Harvey, Nicholas J. A. Harvey, Nicholas J. A. We present new algebraic approaches for two well-known combinatorial problems: nonbipartite matching and matroid intersection. Our work yields new randomized algorithms that exceed or match the efficiency of existing algorithms. For nonbipartite matching, we obtain a simple, purely algebraic algorithm with running time $O(n^\omega)$ where $n$ is the number of vertices and $\omega$ is the matrix multiplication exponent. This resolves the central open problem of Mucha and Sankowski (2004). For matroid intersection, our algorithm has running time $O(nr^{\omega-1})$ for matroids with $n$ elements and rank $r$ that satisfy some natural conditions. United States Office of Naval Research (grant N00014-05-1-0148) National Science Foundation (contract CCF-0515221) Natural Sciences and Engineering Research Council of Canada PGS Scholarship 2010-03-09T20:43:46Z 2010-03-09T20:43:46Z 2009-07 2008-10 Article http://purl.org/eprint/type/JournalArticle 1095-7111 0097-5397 http://hdl.handle.net/1721.1/52443 Harvey, Nicholas J. A. “Algebraic Algorithms for Matching and Matroid Problems.” SIAM Journal on Computing 39.2 (2009): 679-702. © 2009 Society for Industrial and Applied Mathematics en_US http://dx.doi.org/10.1137/070684008 SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial and Applied Mathematics SIAM |
| spellingShingle | Harvey, Nicholas J. A. Algebraic Algorithms for Matching and Matroid Problems |
| title | Algebraic Algorithms for Matching and Matroid Problems |
| title_full | Algebraic Algorithms for Matching and Matroid Problems |
| title_fullStr | Algebraic Algorithms for Matching and Matroid Problems |
| title_full_unstemmed | Algebraic Algorithms for Matching and Matroid Problems |
| title_short | Algebraic Algorithms for Matching and Matroid Problems |
| title_sort | algebraic algorithms for matching and matroid problems |
| url | http://hdl.handle.net/1721.1/52443 |
| work_keys_str_mv | AT harveynicholasja algebraicalgorithmsformatchingandmatroidproblems |