The traveling salesman problem, or TSP for short, is easy to state: given a number of cities along with the cost of travel between each pair of them, find the cheapest way to visit them all and return to your starting point. Simple to state, but remarkably difficult to solve! Despite decades of research by top applied mathematicians around the world, in general it is not known how to significantly improve upon simple brute-force checking. It is a real possibility that there may never exist an efficient method that is guaranteed to solve every instance of the problem. This is a deep mathematical question:
Is there an efficient solution method or not? The topic goes to the core of complexity theory concerning the limits of feasible computation. For the stout-hearted who would like to tackle the general version of the TSP, the Clay Mathematics Institute will hand over a $1,000,000 prize to anyone who can either produce an efficient general method or prove an impossibility result.
The complexity question that is the subject of the Clay Prize is the Holy Grail of traveling-salesman-problem research and we may be far from seeing its resolution. This is not to say that mathematicians have thus far come away empty-handed. Within the theoretical community the problem has led to a large number of results and conjectures that are both beautiful and deep. In the arena of exact computation, an 85,900-city challenge problem was solved in 2006, when the optimal tour was pulled out of a mind-boggling number of candidates in a computation that took the equivalent of 136 years on top-of-the-line computer workstations.
In the Internet’s early years, some observers believed that the new technology would reduce social inequality in at least two ways. First, by reducing the price of information, it would make information more available, and therefore level the playing field. Second, because young people appeared to have the inside track in mastering and using the new technologies (and because youth is negatively associated with wealth and uncorrelated with other indicators of socioeconomic status), some felt that the advantage of the young would likewise reduce certain kinds of inequality in access to and use of information. By contrast, other more jaded observers predicted that the well to do and well educated would use their resources to extract more benefit from the Web than for their less prosperous and well schooled neighbors, reproducing or even exacerbating inequality rather than moderating it.
In his Lunch ‘n Learn seminar on December 2, Paul DiMaggio addressed three issues. First, what is the status of the digital divide? Which divides (i.e. inequality in access to the Internet between which groups) have persisted and which have moderated over time, and why? Second, once people go on-line, how does social inequality shape their experience, how they use the Internet and what they get out of it? Third, what difference does it make? What evidence addresses the question of whether access to and use of the internet does (or does not) improve people’s life chances and ability to participate in their communities?
For the past three decades, the Princeton University Art Museum and the Office of Information Technology have collaborated on many innovative projects. During the 1980s. the Piero Project produced a real time three-dimensional tour of the Basilica of San Francesco in Arezzo, Tuscani. During the 1990s, OIT led the development of Almagest, a media management, presentation, and authoring tool.
Today, OIT and the Princeton University Art Museum are collaborating on the delivery of the museum’s collection through Roxen, the University’s web Content Management System. Customarily, museums are able to display only a small fraction of their holdings, but all museums recognize that one of their most important objectives is to make available scholarly content. Today, with the availability of powerful new development tools and special components to cost-effectively connect to the museum’s SQL Collection Information Management System, the Art Museum will be able to promote existing collections and to provide online access to local and even international researchers to a much larger portion of its holdings and events.
Why has the use of Facebook and other social networking sites exploded? Perhaps, suggest John Jameson and Shani Hilton of Princeton’s Office of Communications, because it is now possible to interact socially with very large numbers of people in ways that are no more difficult than sending out a simple e-mail.
Most users need not worry about the coding or the construction of their pages. They can simply concern themselves with what they should share, and not share.
The technologies are changing rapidly (MySpace, for example, has lost 20% of their users in just two months), bringing enormous opportunities, challenges, and some significant policy headaches.
The current recession has persuaded institutions of higher education to look in new places for significant savings. And so, rather than flying cross country for a conference, imagine being able to take part in sessions, or even delivering a paper, right from your office or from a specialized videoconferencing facility on campus.
Professor John Nash and Professor Robert Socolow, for example, have given several keynote addresses via videoconferencing. Says Professor Socolow: “The Princeton Environmental Institute (PEI) and the Center for Human Values sponsored a video conference lecture last spring for the popular Ethics and Climate Change Lecture Series. Robyn Eckersley of the University of Australia at Melbourne presented a virtual lecture entitled: “The Ethics of Carbon Trading” to an audience which was very receptive to the videoconference.”
The lecture and more information about the series are available at the ECC website.