Interested in working on connectivity algorithms for matroids

[Chao Xu]

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

[Stefan van Zwam]

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.

[Chao Xu]

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.

[Chao Xu]

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. 

[Stefan van Zwam]

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.

[Chao Xu]

I won't be around my campus in the summer, so I'm able to work the desired amount of time.  My advisor grants me freedom to work on anything of my interest during the summer. 

Here is my draft proposal, do you have any suggestions? 

Personal

Name: Chao Xu 
Contact: cha...@illinois.edu 
Location/Timezone: Urbana, PST 
University: University of Illinois at Urbana–Champaign 
Background:

What are your technical skills, education, experience, etc. Especially make sure to explain with what level of mathematics you are comfortable with and on what level you would like to program.

I’m a PhD student of computer science at UIUC. I specialize in algorithms. My adviser is Jeff Erickson.

Mathematically, my experience lies in combinatorics and theoretical CS. I have somewhat decent knowledge on matroid because I encounter them when I work on submodular functions.

Although I mainly program in Java and Haskell, but I do have C++ and python experience. I frequently help students with their python code (albeit simple). In my undergrad years I worked on a site with Django, which requires me to write python.

Who are you? What makes you the best person to work on this particular project? Special motivation?

I have an interest in combinatorial optimization. Matroid comes up often in the field. It will be useful for me to learn the related matroid connectivity and actually implement some optimization algorithms on matroids.

I’m used to coding algorithms. Some more recent code samples (in haskell) include local affine alignment, Sardinas Patterson algorithm and Aho Corasick automaton. I have also implemented a simulation for X-ray crystallography in C++ while working at Brookhaven National Lab, and wrote algorithms for manipulating curves on surfaces for Moria Chas.

What platform and operating-system are you using on your computer? (Sage development is done best on Linux and OSX) 
I use OSX.

Are you or have you been engaged in other open-source projects? 
I had contributed a few open source codes and documentation for Drupal when I was in high school.

Do you code on your own pet projects? 
I have a few pet programs written in Haskell. 
The largest should be the program that generates my website, using Hakyll and a format that I call MathDoc.

Are you a Sage user, how long do you know Sage? 
I had 2 months of SAGE experience during an REU in 2012, where I use it in order to experiment on a game of graph nim.

Project

Title: Connectivity and optimization problems on matroids 
Synopsis: 
This project implements a few fast optimization algorithms on matroids. This includes fast algorithms for matroid intersection(weighted/unweighted) and 3-connectivity algorithm by Bixby and Cunningham (1979), 4-connectivity by Rajan (1987) and higher level connectivity algorithms using matroid intersection. The project will also provide useful examples of matroid intersection.

What is your personal involvement or relationship with your proposed project? 
I will implement algorithms listed.

Details:

1. Connectivity: fast algorithms for k-connectivity. 
   

1. • 3-connectivity algorithm by Bixby and Cunningham

1. • k-connectivity using matroid intersection.
   • 4-connectivity algorithm by Rajan.
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 the maximum common independent set. (Cunningham 1986) This is important for faster k-connectivity algorithm.
   • faster weighted intersection. (it might be faster than the current augmenting path implementation) (Schrijver 2003, chapter 41)
   • Build a collection of matroid intersection examples: 
     
     • matroid partitioning algorithm. This will establish a connection to the graph theory package, as it can be used directly to find the arboricity of a graph.
     • matroid union rank oracle.
     • minimum cost arborescence.

Schedule:

Now - 25th May: Background research: Learning about various algorithms and how the matroid packages work.

25th May – 10th June: Implement 3-connectivity algorithm and 4-connectivity algorithm.

10th June - 15th June: k-connectivity algorithm.

16th June - 26th June: Work on faster algorithms for matroid intersection.

27 June – 5 July: Midterm evaluation period, finish up left overs.

6 July - 17 July: faster weighted matroid intersection algorithm.

20 July - 11 August: Building useful examples of the matroid intersection. Matroid partition algorithm, matroid union rank oracle, min cost arborescence.

11 August - 18 August: Finishing up, provide documentation and a nice wiki page for everything implemented in the summer.

Risk Management: The algorithm implementation of connectivity algorithms might take longer than expected. Rajan’s algorithm is described for representable matroids, and I would need to figure out if it is still fast if it only have access to independence oracle. There is a large amount of time allocated for useful examples of matroid intersections. I can always save some time on those and focus on connectivity.

Best,
Chao Xu

--
You received this message because you are subscribed to a topic in the Google Groups "sage-gsoc" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-gsoc/f4zUkolcX8A/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-gsoc+...@googlegroups.com.
To post to this group, send email to sage...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-gsoc.
For more options, visit https://groups.google.com/d/optout.

[Stefan van Zwam]

It is a good start. I think the weakest aspect is your lack of experience coding in Python/Cython. You need to set aside time for familiarizing yourself with the Sage development process, preferably during the orientation period. Your goal should be to fix one of the open tickets (not necessarily a matroid one, just pick an easy one), and to review one other ticket.

What matroid intersection algorithm do you have in mind? Can you put in some references? I'm curious about Rajan's algorithm in particular.

--Stefan.

[Chao Xu]

"You need to set aside time for familiarizing yourself with the Sage development process, preferably during the orientation period"

When is the orientation period? I'm would be much free than now after April 22, since I have a conference deadline. 

"What matroid intersection algorithm do you have in mind? Can you put in some references? I'm curious about Rajan's algorithm in particular."

The 4-connectivity algorithm is described in section 2 of Arvind Rajan's PhD thesis. 

@phdthesis{Rajan:1987,

 author = {Rajan, Arvind},

 title = {Algorithmic Applications of Connectivity and Related Topics in Matroid Theory},

 year = {1987},

 note = {AAI8710378},

 publisher = {Northwestern University},

 address = {Evanston, IL, USA}}

The matroid intersection algorithm

W.H. Cunningham, Improved bounds for matroid partition and intersection algorithms, SIAM Journal on Computing 15 (1986) 948–957. 

There is a O(n^{3/2}mQ)-time algorithm, n is the maximum size of common independent set, m is the number of elements and Q is the time for independence oracle. 

 

The weighted matroid intersection algorithm is the Corollary 41.10a in Schrijver's 3-volume Combinatorial Optimization.

 

Best,
Chao Xu

[rudi.pe...@gmail.com]

Hi Chao,

I implemented the 3-connectivity algorithm based on matroid intersection last week. I did not implement Bixby-Cunningham and I did not essentially change the implementation of matroid intersection, so there will be no need to change any of your gsoc plans. But my new code is clearly in your path this summer, so I thought I'd let you know. Perhaps the best way to reduce any interference with the work you will be doing is to review my patch now, so that it is part of sage by the time you start adding code.

While I was writing the code I noticed that the matroid intersection method did not return an optimal dual solution, that is, a U so that max{ |X| : X common independent set} = min { r_1(U) +r_2(E\U) }. I'm hoping you will also add this functionality when you rewrite the cardinality matroid intersection algorithm. I only partially did this now, to get minimal matroid separations. 

Best wishes,

Rudi