Posts tagged sample
Posts tagged sample
So what is the use of being able to mathematically determine if a huge graph is bipartite or not?
"Bipartite" is the same thing as "2-colorable". Finding that your graph is bipartite is the same as finding that its vertices can be colored red and blue, with edges connecting only vertices of different colors.
Therefore, if the vertices represent some objects you are interested in, and the edges represent certain constraints that can be viewed as “being incompatible”, finding that the graph has low chromatic number can be seen as an efficient way of allocating the objects into a small number of internally-compatible classes. If the graph is bipartite, this is as good as you could have hoped for - two classes suffice.
A standard concrete example is the assignment of teachers to classes: suppose you need people to teach various introductory calculus courses, the timetables have already been drawn, and various courses overlap so they cannot be taught by the same person. You’re trying to determine how many profs would be needed to cover calculus. You draw the graph (vertices = classes, edges = overlaps), and if it’s bipartite, woohoo, you can make do with just two teachers. If the graph is 3-colorable, you’ll need three, and so on.
So, whenever you see an application of graph coloring (and, really, there are tons of these), “bipartite” is just the special case “two colors suffice”. It’s sort of a special special case, since determining 2-colorability is algorithmically way easier than determining 3-colorability or 4-colorability and so on, but that is a different story.
It helps adapting algorithms dealing with graphs and matrices to run in parallel.
When solving large linear systems on parallel processors, you can represent the matrix by a graph. If the graph is bipartite (two-colorable), then some of the well-known algorithms (Successive over-relaxation or SOR) are easily adaptable to run in parallel threads — vertices of each color form an independent set and can be processed in parallel. Look for “red-black SOR”, which is particularly effective on a grid (when solving linear systems arising from partial differential equations in mathematical physics). The amount of parallelism is determined by the size of the smaller set.
The bipartite graph structure can be used to capture a relationship between two types of objects where the distinction between the types of objects is important.
A student-applied-to-college relationship can (for example) be stored in the bipartite graph depicted above. Blue dots could be students (e.g. Mary, Jane, Joe) and Red dots could be colleges they applied to (e.g. Princeton, Cornell, MIT)
Bipartite graphsare a specific kind of graphs nodes can be decomposed into two disjoints sets such that two nodes in a same set are not connected, therefore those graphs are usually written B=(L,R,E), where L,R (left/right) are the disjoint sets of nodes and E the edges. In this context, a complete bipartite graph is a bipartite graph where every node in one set are connected to every node in the other set
But an easy way to understand and reason about bipartite graphs is to think of two groups of people being paired in some activity. For example, boys and girls dating. Assuming only heterosexual couples, even without monogamy, you get a bipartite graph where the vertices are people, edges represent relationships between them, and the two sets are the set of boys and the set of girls.
E.g. tree is always bipartite (it doesn’t contain cycles and esp’ not odd length cycles),
In order to split some tree’s vertices into two sets you can run the BFS algorithm and mark all the vertices that you found on any odd step as V1 and all the other vertices as V2
The descriptions above outline the properties, but not the utility or reason you should care.
What is it? I think of it as a search criteria over graph data, where I am looking for a very useful special case. I am looking for a data structure called an Adjacency Matrix, aka: a 2-mode matrix.
A two mode matrix maps together instances of entities of two types. That means for example your row headers are schools, and your column headers are students. In databases these are resolver tables that enable many-to-many relations. Prathyush Kashyap’s answer illustrates this nicely.
Bipartite Graphs are those which have two sets of vertices which are mutually disjoint . The Relation or edges in these graphs exists only between two vertices which are not from the same set of vertices.
Famous example :
Assigning n jobs to m persons can be modelled using a Bipartite Graph..
The edge exists if a job i can be allotted to a person p.
Obviously this requires a Bipartite model of graph, Since an edge here can not exist between a job to another job or a person to another person.
Outside of modelling problems as matchings in a bipartite graph which is very common, I would say the best known everyday use of bipartite graphs is the stable marriage problem (http://en.wikipedia.org/wiki/Sta…).
Think of two groups - guys and girls where each guy has an ordered list of all girls and vice versa. The Gale-Shapely algorithm always outputs a stable matching - one in which there never exist two couples such that they would be happier if they swapped partners. I think its really well described in the following slides:
But for a more standard reference, the Wikipedia page is here:
Answer by Robert Love to In computer security, what is a sandbox?
I worked at Carl’s Jr. as a teenager here in Tucson, AZ. Tucson is in the hot southwest American desert and we do not get much rain except for a short period around late July to early September when we get huge summer monsoons almost daily. The reason I explain this will become obvious soon.
The big fish story…
After working at Carl’s Jr. for two years, one summer I was cooking up some Carl’s Catch Fish sandwiches and we ran out of the preblanched patties. This was a bit of a pain because fish took longer to cook than anything else on the menu. To reduce the time it took to cook the fish we would pre-blanch the fish patties we intended to use for the day and then store them in the refrigerator instead of the freezer. Then when someone orders fish you cooked it freshly for an additional 2 mins 20secs . If you did not have preblanched fish it would take 6+ minutes to cook. This was not good as it meant fish took twice as long to cook and get out the door as everything else and would slow us down.
… about the one that got away…
On my lunch hour I went to the computer and tried to pull up the history of fish orders because it seemed like we were never having enough fish lately. We must not be blanching enough fish compared to our average sales. I looked at the average for fish orders and it turned out to be roughly what we prepared each day. So why was it that we were running out of fish lately? There weren’t any sales or advertisements to explain it.. So I seemed to be wrong. We were preparing the correct average amount of fish sold per day on a yearly average. I spent my whole lunch hour looking at the average sales for fish and found we had the right guess on how much to prepare.
The thing was we seemed to be wasting a lot of fish on some days and having way too little on others. A fish that was blanched and unsold had to be thrown away daily and fish that had to be cooked fresh slowed our order times. I couldn’t understand why fish sales would fluctuate widely enough compared to other menu items to explain this. There had to be a different explanation. So my initial experiment of looking at average sales and trying to adjust for it was a total failure.
… and the ugly truth…
So I was looking out the window watching the rain with the last minutes of my lunch ticking away and I had the weirdest thought… There was no way it could be right.
I thought, “What if people are buying more fish on rainy days?”.
So I wasn’t too confident on this thought given my failure going through the average sales before but sure enough by comparing weather data to sales data on rainy days we sold 2-3 times as much fish! Consistently, 2-3 times as much fish!
This was huge! The huge fish sales during rainy days during a 2 month period was throwing off the average for the whole year. This meant my average number I was preparing every day was way too much on dry days (most of the year) and way too little on rainy ones.
… until finally, the big catch!
By reducing the number of fish we blanch on dry days we cut our wasted fish by almost half and by blanching more fish on rainy monsoon days we cut order times by several minutes and had happier customers all around. Win, win, win! On a yearly basis this saved enough money they could easily afford the promotion and raise they gave me and still increase profits!
On rainy days we even found we could increase fish sales by suggesting it after greeting the customer. This never worked on dry days. This was good as they were more expensive than the Carl’s Jr. Famous Stars which at the time only cost 99c apiece! The proactive sales pitch increased the sales even more.
This experience taught me that the psychology of consumer sales is a very weird thing. You can’t base social buying behaviors on averages alone. Something as random and unpredictable as a rainstorm could change what customers order.
What are the potential reasons for this preference?
update, now a question of its own : Rain: Why might people prefer fish sandwiches on rainy days?
I have a theory. The type of customers they got was different on rainy days. In dry places, where people are not accustomed to rain, it really inconveniences them, so much as to change their usual eating place. Instead of going back home or to a better restaurant, people would be more eager to go to the nearest fast food place. Now, the sort of people who do not usually eat fast food, would be more likely to order fish, as it may be considered a lighter and healthier meal.
Operations Research is what it’s called. How to make Operations more efficient. You can approach it from the business side (money side) or from the systems side. Creating systems that help organizations work more efficiently and make more money. Systems can be computer systems, but more broadly it is collecting the right data and changing the work-flow, including computers and data when and where they will make a difference.