Hi Stefan,
How fast is the current weighted matroid intersection algorithm? It seems
to be the naive augmentation one.
Also, I'm thinking about solving the following problems in the proposal.
1. Connectivity: fast algorithms for k-connectivity.
- 3-connectivity algorithm by Bixby and Cunningham
- k-connectivity using matroid intersection.
- track down the faster 4-connectivity algorithm in Rajan's PhD thesis
and see if it's reasonable to implement. [Rajan 1987]
2. Matroid intersection:
- Implement the $O(n^{3/2}m)$ time algorithm for matroid intersection.
$m$ is the groundset size, $n$ is the size of maximum common independent
set. [Cunningham 1986]
- fast weighted matroid intersection. (this can be ignored if the
current one is already as fast) [Schrijver 2003, chapter 41]
- Some applications based on matroid intersection: matroid partition
algorithm, matroid union oracle.
I wonder if this is too little to do for the summer.
On Friday, March 13, 2015 at 1:09:05 PM UTC-5, Chao Xu wrote:
>
> Hi Stefan,
>
> Thanks for the reply. I know the definitions for many matroid concepts and
> its applications.
> For example, I have no problem reading the chapter on matroid in
> Schrijver's book.
> I don't have background with the deeper theories.
>
> On Monday, March 9, 2015 at 11:35:09 PM UTC-5, Stefan van Zwam wrote:
>>
>> Hi Chao,
>>
>> The state of the art in 3-connectivity algorithms is a 1979 book chapter
>> by Bixby and Cunningham, see
>> http://www.ams.org/mathscinet-getitem?mr=538038 (you'll have to dig it
>> up from a library, most likely). For matroid union and intersection,
>> Schrijver's 3-volume Combinatorial Optimization is a good reference.
>>
>> How much do you know about matroids?
>>
>> Cheers,
>>
>> Stefan van Zwam.
>>
>> On Tuesday, March 3, 2015 at 2:39:49 PM UTC-6, Chao Xu wrote:
>>>
>>> Hi all!
>>>
>>> I'm Chao Xu, a computer science PhD student at UIUC.
>>> - I had experience with Sage a few years ago during an REU, and I
>>> sometimes dub in python.
>>> - I have lot of experience implementing algorithms(although it's in
>>> Java).
>>> - I'm interested in combinatorial optimization, and believe implementing
>>> some algorithms for matroid seems to be a good introduction to this field.
>>>
>>> Any papers could bring me up to speed with the current state of art? So
>>> I might get a feeling of what is feasible.
>>>
>>> Best,
>>> Chao
>>>
>>
--
You received this message because you are subscribed to the Google Groups
"sage-gsoc" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-gsoc.
For more options, visit https://groups.google.com/d/optout.
