These things have a way of filling up your time, so I don't think it's too
little. You could include some minor work (improving the catalog, e.g. by
adding options for the type of representation of the matroids in it, or
forging more links between the coding theory, graph theory, and matroid
theory parts of Sage, computing the automorphism group of a matroids, ...)
Will you be able to work the desired amount of time this summer? Is your
PhD supervisor on board with you doing this?
Cheers,
Stefan.
On Sunday, March 15, 2015 at 7:37:47 PM UTC-5, Chao Xu wrote:
>
> 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.
