ACO Seminar: Veit Elser (Cornell University)

Speaker: Veit Elser, Cornell University A greedy method for solving even hard problems Abstract: Greed is a great instinct for solving problems. Its geometrical analog is a projection. Say your problem has many variables. It’s always possible to let them live in a continuous space, and define solutions to your problem as some subset in that space. A projection is the greedy operation of moving an arbitrary point to the set as efficiently as possible — by the least Euclidean distance. For many kinds of sets, even discrete and other highly non-convex ones, the projection computations are easy. Of course we know that cannot be the case when the task at hand is truly hard. Fortunately, even hard problems can be formulated as finding a point in the intersection of two sets, where projecting to each set individually is easy. This talk describes a general method that uses two easy projections, iteratively, to solve hard problems. After some history I will go over several examples, including sudoku, square packing, and data clustering. Problem requests will be considered if received (at ve10@cornell.edu) at least one week before the talk.