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: [email protected] 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: Connectivity: fast algorithms for k-connectivity. 3-connectivity algorithm by Bixby and Cunningham k-connectivity using matroid intersection. 4-connectivity algorithm by Rajan. 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 On Tue, Mar 17, 2015 at 11:29 AM, Stefan van Zwam <[email protected]> wrote: > 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 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 > [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. -- 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.
