Loading...
Please wait, while we are loading the content...
Similar Documents
Query Lower Bounds for Matroid Intersection (Combinatorial Optimization and Discrete Algorithms)
| Content Provider | Semantic Scholar |
|---|---|
| Author | Harvey, Nicholas J. A. |
| Copyright Year | 2010 |
| Abstract | We consider the number of queries needed to solve the matroid intersection problem, \mathrm{a} question raised by Welsh (1976). Given two matroids of rank r on n elements, it is known that O(nr^{1.5}) independence queries suffice. Unfortunately, very little is known about lower bounds for this problem. This paper describes three lower bounds which, to our knowledge, are the best known: 2n-2 queries are needed for rank 1 matroids, n queries are needed for rank n-1 matroids, and (log23) n-o(n) queries are needed for matroids of rank n/2 . The first two results are elementary, and the last uses methods from communication complexity and group representation theory. |
| Starting Page | 81 |
| Ending Page | 105 |
| Page Count | 25 |
| File Format | PDF HTM / HTML |
| Volume Number | 23 |
| Alternate Webpage(s) | http://www.kurims.kyoto-u.ac.jp/~kenkyubu/bessatsu/open/B23/pdf/B23_005.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
