Aaron Archer's Research Page

My research interests include discrete optimization, algorithmic mechanism design, approximation algorithms, online algorithms, graph partitioning, facility location, network flows, and graph algorithms.

Look below for some of my publications.

I earned my Ph.D. in Operations Research from Cornell University in January, 2004. My thesis advisor was Éva Tardos, who is in the Computer Science department. During grad school, I spent the spring 2000 semester visiting the Computer Science department at UC Berkeley, and spent the summers of 2001 and 2002 working in the Computer Science Principles and Methodologies group at the IBM Almaden Research Center. Prior to these adventures, I earned a B.S. in mathematics from Harvey Mudd College.

I am now a member of the Algorithms and Optimization group at the AT&T Shannon Research Laboratory.

Algorithmic mechanism design

Aaron Archer, Mechanisms for Discrete Optimization with Rational Agents [ps]

Bibliographic info: Ph.D. thesis, Cornell University, January 2004.
Quick summary: My dissertation is primarily a synthesis of the next four papers listed below. The unifying theme is to highlight and rectify four shortcomings of the Vickrey-Clarke-Groves (VCG) mechanism, which is widely seen as the gold standard in the field of mechanism design. We approach algorithmic mechanism design as "discrete optimization with a blindfold." Whereas traditional optimization problems assume that you are given the data as a starting point, we assume that different economic agents each hold part of the input data and report it to the decision-maker, who then decides on some outcome. Since these agents are self-interested, we assume that they will lie if they think it is to their advantage to do so. The field of mechanism design seeks to create "truthful" protocols, which means it is always in the agents' best interest to report their data truthfully. These usually involve the use of side payments to help induce truthtelling.
The VCG framework is a general method for creating truthful mechanisms. We address the following four drawbacks: (1) VCG selects the outcome that maximizes the total social welfare, whereas often the decision-maker wants to maximize some other function. (2) In the case where the decision-maker is purchasing something, VCG must sometimes pay an unacceptably high premium to induce truthtelling. (3) Sometimes the decision-maker would like to use the VCG mechanism, but cannot because computing it is NP-hard. (4) VCG resists manipulation by single agents, but, in general, multiple agents could collude to cheat the mechanism.

Aaron Archer, Joan Feigenbaum, Arvind Krishnamurthy, Rahul Sami and Scott Shenker, "Approximation and collusion in multicast cost sharing" [ps]

Bibliographic info:

An abstract by the last four authors appears in Proceedings of the ACM Conference on Electronic Commerce (2001) 253-255.
Full version appears in Games and Economic Behavior 47 (2004) 36-71.

Quick summary: We investigate two strategyproof methods for sharing the cost of transmission among recipients in a multicast tree: the Shapley value mechanism and the marginal cost mechanism. We construct a method that approximates the Shapley value mechanism, greatly reducing its communication complexity while maintaining its key property of group strategyproofness. The marginal cost mechanism (an instance of the Vickrey-Clarke-Groves family) is known to resist manipulation by single agents, but not by groups. We characterize which coalitions of agents can successfully manipulate the mechanism, how, and under what circumstances.

Aaron Archer, Christos Papadimitriou, Kunal Talwar and Éva Tardos, "An approximate truthful mechanism for combinatorial auctions with single parameter agents" [ps]

Bibliographic info:

Conference version appears in Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003) 205-214.
Full version appears in Internet Math 1 (2004) 129-150.

Quick summary: For most combinatorial auctions, even the simplest ones, it is NP-hard to compute the allocation of goods that maximizes the overall social welfare. Sadly, replacing an exact optimization routine with an approximation usually destroys the desirable incentive compatibility properties of auction mechanisms such as the famed Vickrey-Clarke-Groves (VCG) mechanism. We show how to adapt the powerful technique of rounding a linear program to create mechanisms that approximate the VCG mechanism while simultaneously attaining truthfulness in expectation and truthfulness with high probability. We illustrate this technique in the context of combinatorial auctions for single-minded bidders.
Note: This paper was invited to appear in the inaugural issue of Internet Math., but an editorial mishap delayed it to the second issue.

Aaron Archer and Éva Tardos, "Frugal path mechanisms" [ps]

Bibliographic info:

Conference version appears in Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (2002) 991-999.
Full version will appear in J. Algorithms.

Quick summary: The Vickrey-Clarke-Groves (VCG) mechanism has been applied to the problem of buying the cheapest path in a graph, where the nodes or edges are owned by different economic agents. This mechanism induces truthful cost revelation as a dominant strategy for each agent, and selects the cheapest path in the graph, with respect to the actual costs incurred by the agents. However, since it must pay bonuses to each agent in order to induce truthtelling, it can sometimes be forced to overpay the actual cost by a factor of (k eps) (where k is the number of agents along the chosen path), even when there is tight competition in the market, in the form of a disjoint path costing only (1+eps) times the cost of the cheapest path. We prove that this drawback is intrinsic to the problem, in that every "reasonable" dominant strategy mechanism can be forced to overpay by just as much. The main part of our proof involves a characterization in terms of so-called min function mechanisms, which is of independent interest.
Note: This paper was invited to appear in a special issue of J. Algorithms devoted to the top papers from SODA '02.

Aaron Archer and Éva Tardos, "Truthful mechanisms for one-parameter agents" [ps]

Bibliographic info:

Conference version appears in Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (2001) 482-491.
Full version in preparation.

Quick summary: We consider a range of classic discrete optimization problems in which the various components of the system under study are represented by distinct economic agents. In these problems, we are interested in optimizing some objective function other than the overall social welfare, so the Vickrey-Clarke-Groves mechanism is of no use to us. In the case where each agent's data can be naturally represented by a single real parameter, one can construct a truthful mechanism as long as the "load" allocated to each agent is monotone in her parameter. We apply this result to construct truthful polynomial-time mechanisms for a range of problems, including linear programming, facility location, max flow, and several basic scheduling problems. Some of these problems are NP-hard, in which case we derive truthful approximation algorithms. For one problem, we derive a lower bound on the approximation factor achievable by a truthful mechanism (without regard to its computational complexity).

Discrete optimization

Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar and Éva Tardos, "Approximate classification via earthmover metrics" [ps]

Bibliographic info: Appears in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (2004) 1072-1080.
Quick summary: The metric labeling problem and a special case, the 0-extension problem, ask us to label the nodes of a graph in such a way that neighboring nodes receive identical or similar labels (to the greatest extent possible). The so-called earthmover metric linear programming relaxation for the metric labeling problem is conjectured to have a small integrality gap, but attempts to use it to create approximation algorithms have so far met with limited success. We make progress in this direction by giving (1) an O(alpha)-approximation algorithm for the 0-extension problem in the case where the metric on labels is alpha-decomposable and (2) an O(log n)-approximation algorithm for the metric labeling problem, based on probabilistic tree embeddings and coordinated rounding along the tree.

Aaron Archer, Ranjithkumar Rajagopalan and David B. Shmoys, "Lagrangian relaxation for the k-median problem: new insights and continuity properties" [ps]

Bibliographic info: Appears in Proceedings of the 11th Annual European Symposium on Algorithms (2003) 31-42.
Quick summary: Good approximation algorithms for the k-median problem have been developed based on the fact that its Lagrangian relaxation is the much better-understood uncapacitated facility location problem. We make two contributions to this line of work. (1) We modify the Jain-Vazirani primal-dual algorithm for facility location in order to make it "continuous," meaning that the number of facilities opened by the algorithm never jumps by more than one as we vary the facility cost. This resolves an outstanding question posed by Jain and Vazirani, and establishes an upper bound of 3 on the integrality gap of the standard linear programming (LP) relaxation for k-median. (The previous best result was 4). This provides a rare example of an existential result proving an upper bound on an LP integrality gap without having an accompanying polynomial-time algorithm (since our algorithm involves finding a maximum independent set). (2) We give an LP-based analysis of a facility location algorithm by Mettu and Plaxton, which had previously been analyzed without any reference to an LP. One advantage of our analysis is that it leads immediately to a modification of Mettu-Plaxton that has the Lagrangian-preserving" property necessary for use in constructing an algorithm for k-median.

Aaron Archer, Asaf Levin and David P. Williamson, "A faster, better approximation algorithm for the minimum latency problem," [ps]

Bibliographic info:

Conference version by the first and third authors appears as "Faster approximation algorithms for the minimum latency problem," Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (2003) 88-96.
Improved version appears as Cornell ORIE Technical Report number 1362 (2003).
Journal version in preparation.

Quick summary: The minimum latency problem (MLP), sometimes called the deliveryman or traveling repairman problem, is a customer-oriented version of the traveling salesman problem. Instead of a tour that minimizes the total travel time, we desire a tour that minimizes the average time at which we arrive at our customer locations. Blum et al. gave a method for using a beta-approximation algorithm for the rooted k-minimum spanning tree (k-MST) problem as a black box to produce an (8 beta)-approximation for MLP. Goemans and Kleinberg improved this factor to (3.59 beta). We show how to use Lagrangian relaxation to produce a 7.18-approximation for MLP (the same result one would obtain using a 2-approximation algorithm for k-MST), even though there is no 2-approximation algorithm known for the rooted k-MST problem. Our algorithm improves previous results both in approximation guarantee and running time. The analysis is clever: it involves "bluffing," along with a proof that the Goemans-Kleinberg algorithm will never call our bluff.

Aaron F. Archer, "Two O(log*k)-approximation algorithms for the asymmetric k-center problem" [ps]

Bibliographic info: Appears in Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (2001) 1-14.
Quick summary: Suppose there are n buildings that require protection from the fire department, but we have enough money to build only k fire stations. Where should we locate the fire stations in order to minimize the worst-case travel time to a fire? This is known as the k-center problem. For the case where the travel times are symmetric (i.e., time from A to B = time from B to A), there is a clever but simple 2-approximation algorithm (Hochbaum and Shmoys). When the times are asymmetric (possibly due to one-way streets or asymmetric traffic patterns), the problem becomes much harder. Panigrahy and Vishwanathan gave an O(log*n)-approximation based on a recursive greedy set cover procedure. We improve this result to O(log*k), using two completely different algorithms. (The log* function is the number of times we must iterate the log to bring the result below 1.)

Aaron Archer, "Inapproximability of the asymmetric facility location and k-median problems" [ps]

Bibliographic info: unpublished manuscript (2000).
Quick summary: This paper gives lower bounds on the approximability of the facility location and k-median problems when the distance function is not symmetric, which essentially match the upper bounds given for these two problems by Hochbaum and by Lin and Vitter, respectively. We attain the bounds via a simple reduction from the set cover problem.

Other

Aaron F. Archer, "On the upper chromatic numbers of the reals" [ps] [pdf available from the publisher ]

Bibliographic info: Discrete Math., 214 (2000) 65-75.
Quick summary: The chromatic number of a metric space (X,d) is the minimum number of colors necessary to color every point in such a way that no two points at distance 1 get the same color. Now suppose we restrict different distances for each color, e.g., points at distance 2 cannot both be colored red, while points at distance 3 cannot both be colored blue. The upper chromatic number of X is the minimum number m of colors such that, no matter what list of m distances are restricted for the m colors, there is a legal coloring. The k^th upper chromatic number is the same, except that there are k distances restricted for each color. Our main results are: (1) For each k, the k^th upper chromatic number of the reals is at most the ceiling of 4ek, which improves the previous best upper bound of 32^k k! (2) For each k, the k^th upper chromatic number of the real numbers matches that of the integers, which is pretty astounding, since there are so many more reals to color. We generalize this to higher dimensions under the L₁ and L_infinity norms, and prove that these upper chromatic numbers are all finite. We also introduce a related quantity, the chromatic capacity of a graph, and prove some elementary results about it.
Addendum: I stated Theorem 14 without proof, since the proof is so similar to that of a similar theorem already in the literature. Since publication, some people have asked me for it, so here is the full proof.
Note: This paper came out of research I did at Joe Gallian's math REU at U. Minnesota, Duluth. Thanks for a fun summer and a fine introduction to research, Joe!

Aaron F. Archer. "A modern treatment of the 15 puzzle" [ps][summary]

Bibliographic info: Amer. Math. Monthly, 106 (1999) 793-799.
Quick summary: The infamous puzzle maker Sam Loyd introduced his popular 15-puzzle in the 1870's, driving many people crazy by offering a prize of $1000 for the first person who could perform a feat that Loyd knew to be mathematically impossible. The puzzle consists of a tray that can hold a 4 by 4 grid of square pieces, which is filled by 15 squares with one square left blank. One can change the configuration by moving an adjacent square into the blank spot. The object is to obtain certain configurations of the pieces. It is easy to show that no odd permutations of the pieces are attainable, if the blank is to end up back where it started. This paper gives a particularly slick proof that all even permutations *are* attainable. It also includes many amusing historical notes about the puzzle.
Note: I figured out the main result while trying to avoid writing a paper for my film studies class in college. Ironically, more people have talked to me about this paper than about any of my serious research papers. I guess people really read the Monthly.

Aaron F. Archer, Andrew D. Hutchings, and Brian Johnson, "A case for stricter grading" [ps]

Bibliographic info: UMAP J. 19.3 (1998) 299-313.
Quick summary: As a remedy for the epidemic of grade inflation, this paper proposes and investigates one scheme for adjusting students' GPAs according to the difficulty of the courses they have taken and the harshness or leniency of their professors in assigning grades for the course.
Note: This paper -- dreamed up and written in 89 hours -- won the SIAM award at the 1998 Mathematical Contest in Modeling. Adjacent articles in the journal explain the contest, and present the other two winning papers.

Aaron Archer, Rick Cleary, Robin Lock and John Trono, "March Mathness: an analysis of a nonstandard basketball pool" [pdf]

Bibliographic info: Math Horizons (Feb. 2001) 17-21.
Quick summary: Office pools for the annual NCAA men's basketball tournament (nicknamed "March Madness") are a popular national diversion every March in the United States. In 2004, ESPN's online bracket challenge received about 2.4 million entries. Despite this popularity, many people are intimidated by the prospect of picking the winners in 63 games, many of them between colleges they may not have heard of, and whose basketball teams they certainly know nothing about. We suggest a different type of pool. Each team is assigned a price based on their seed -- the top seeds cost 25 cents apiece, while the bottom seeds cost only 1 cent apiece. To enter, you pay one dollar, and buy one dollar's worth of teams. Each player counts up the total number of games won by her teams, and the player with the highest total wins the jackpot. This leads to a lot of interesting mathematical questions, some of which we examine in this article.
Note: Co-author Rick Cleary was interviewed about this topic for the NPR show Science Friday on March 19, 2004 during the NCAA basketball tournament. Click here for the audio archive of the interview.

Back to Aaron's main page