Summary

Computers and algorithms have come to play a central role in modern society. Large networks and massive decentralized systems in engineering, biology and the social sciences, pose unprecedented modeling and algorithmic challenges, arising from the huge amounts of data to be handled, the fact that relevant information is often distributed and noisy, and the presence of multiple agents that interact in a selfish manner. These situations —frequently encountered in large data retrieval systems, telecommunication networks, economic markets, and urban transportation— raise the issue of algorithmic efficiency to a new level of importance.

This proposal —at the interface of computer science, economics and mathematics— has a multidisciplinary nature spanning the fields of Algorithms, Combinatorics, Game theory, and Optimization (ACGO). Our goal is to create and consolidate a research Center with both a national and regional leadership role in the development, application and dissemination of the ACGO themes. To this end, we have put together a team that comprises 9 principal researchers from the Departments of Computer Science, Industrial Engineering and Mathematical Engineering at Universidad de Chile, together with 14 associate researchers from these Departments and 5 other Chilean institutions.

In the past, each of us has successfully carried forth his own research agenda. We have also collaborated among us in basic and applied research, and we have established a strong network of international collaborators. Our activity has qualitatively and quantitatively consolidated in the last decade, attaining nowadays a critical mass and substantial volume that provides a solid ground to build and carry forth this proposal. We stress that 14 out of the 23 participating researchers have been recruited in the past 5 years, in part due to the success of various previous grants that allowed this group to grow and mature. This proposal will substantially contribute to increase the associative impact of our activity.

In perspective, this proposal can be viewed as a second generation FONDAP, with a multidisciplinary character but at the same time with a more focused scope. The proposed research deals with the design and analysis of algorithms in the context of combinatorics, game theory and optimization. The specific subjects are all concerned, in one way or another, with decision problems where control and information are decentralized, and which are characterized by the lack of information and/or lack of coordination. Many of these questions arise from the study of large networks such as the Internet, where multiple agents make decisions in a decentralized manner, with limited information about the system’s characteristics. We are interested in the mathematical structure of such systems, though the ultimate goal is to deepen our algorithmic understanding of these complex structures. Of course, our immediate research goals are more restricted in scope and technical in nature. We have grouped them into three major themes:

Algorithms and Complexity

focuses on designing and analyzing efficient procedures for discrete-structured problems. Topics to be addressed include data structures and compression for large information retrieval problems, the study of adaptive complexity analysis of algorithms, smoothed analysis of discrete problems such as pattern matching, sampling techniques to gather information about the structure of complex networks, and distributed routing in large unstructured networks.

Algorithmic Game Theory

groups problems where the lack of coordination is a prominent characteristic. These include learning and adaptation of agents in traffic networks, design of decentralized protocols for routing and congestion control in telecommunications, mechanism design and market games, and the study of combinatorial games in graphs such as selfish scheduling and dynamic flow equilibrium.

Mathematical Programming

deals with the analysis and algorithmic solution of optimization problems. We will investigate techniques to deal with uncertainty such as sampling methods for stochastic programming, robust optimization for combinatorial problems, and sensitivity analysis for second order cone programming. Also, in the area of integer programming, we plan to investigate new cutting plane techniques as well as aggregation and local search heuristics for branch-and-bound methods. Finally, warm starts and complexity issues for interior point methods in linear and quadratic programming will be addressed.

Our proposal has also a strong commitment towards educational and training activities at the graduate and undergraduate levels. We believe that the highest impact of universities in society and industry is attained through the advanced training of scientists and engineers. In this respect, it is worth mentioning that our group has a substantial experience in developing applied projects jointly with industrial partners, including the development of industrially-oriented thesis. We expect these activities to continue in the future with their positive impacts in training. On the other hand, we highly value the concept of multidisciplinary training, which we take as one of our strategic axis for future development. With this in mind we recently created an ACGO Minor at the School of Engineering of the University of Chile, a multidisciplinary program that encompasses undergraduate educational activities. At the graduate level, we plan to articulate our efforts around the ACGO cluster and build bridges between the existing Ph.D. programs in Applied Mathematics, Engineering Systems, and Computer Science. Advising undergraduate and graduate students will thus be a fundamental part of our training efforts. We will supplement these efforts with other activities such as a Graduate Summer Schools in ACGO themes, a Winter Camp experience for undergraduates, and a research internship program to allow thesis students to do part of their work at international centers.

As it can be observed from the researchers’ curricula, the group has a substantial publication record in first-rate academic venues. Although short-term impact citation factors are not very meaningful in our disciplines (which are characterized by long publication half-lives), it is worth noting that the journals on which we publish are among the top 20% according to their 5-year impact factors. Still more relevant is the fact that our observed citations are 20% above those journal averages. The international recognition of our work can also be observed in the significant number of invitations to join program committees of reputed conferences¹ , invitations to deliver plenary talks and to serve in the editorial boards of leading scientific journals² . Furthermore, members of our group have been distinguished with 4 best paper awards³ and 3 best thesis awards⁴ , as well as several distinctions for excellence in teaching at the University of Chile.

We also have a substantial experience in training undergraduate and graduate students and carrying out research projects, both individually and collectively. Moreover, several of the participants in this research proposal have a proven track record in academic leadership, measured in terms of senior roles in succesfully completed projects, academic management, and national and international scientific committee work. In order to assist us in the effort of setting up a center of a true international stature, we have set up an International Advisory Board composed by Bill Cook (GaTech), Michel Goemans (MIT), Alexander Shapiro (GaTech), Sylvain Sorin (U. Paris 6), and Shang-Hua Teng (USC). The board will meet once a year in Santiago to discuss and provide scientific advice on the research and activities carried out by the Center.

We would like to end this Summary by pointing out that Chile, as a small country, cannot expect to develop cutting edge research in all areas of knowledge. This young and competent group of researchers has attained the required critical mass to set up a research center that would be unique in Latinamerica. Taking into account the increasing relevance of algorithms in solving real-world problems, we are convinced that this is an extremely valuable step in the development of Chile.

Research Proposal

1 Introduction and Overview

The advent of the computer in the 50’s brought a fresh view on the algorithmic aspects of mathematics. A host of new questions emerged, as computers and algorithms began to play a central role in society. Operations research, for instance, was born from the need to address industrial problems by putting them in a mathematical form solvable by algorithms. Optimization under constraints became the basic paradigm of quantitative methods for decision-making, and Computer Science arose as a new discipline dealing with a range of questions related to discrete structures. Furthermore, basic questions in graph theory, logic, computational models, number theory, and even topology, were reformulated in algorithmic terms.

The mathematics used by computer scientists and operations researchers overlap and the boundaries have become blurred. Important theories, including polyhedral combinatorics, graph theory, network optimization, approximation and on-line algorithms, are nowadays jointly developed by computer scientists, operations researchers, and applied mathematicians. Naturally, these communities are converging in instances such as conferences, seminars, and graduate programs structured around the Algorithms-Combinatorics-Optimization trilogy. Examples of such ACO initiatives are found at Carnegie Mellon, CWI, Georgia Tech, Warwick, and Waterloo. In the last decade or so, with the emergence of decentralized markets and massive decentralized networks such as the Internet, Game Theory and its algorithmic counterpart, mechanism design, have started to join the picture. The pertinent models for these huge and widely distributed systems seem to be found in the context of game theory, but the issues differ significantly from the classical economic questions and the tools needed to address them are found in the ACO toolkit.

In August 2008, a group of researchers from the departments of Computer Science, Industrial Engineering, and Mathematical Engineering at Universidad de Chile, established a group-of-interest spanning the fields of Algorithms, Combinatorics, Games, and Optimization (ACGO). This initiative arose as an attempt to structure the existing collaborations in order to increase their impact in research and education. In the past, each of us has successfully carried forth his own research program: we lead individual projects, collaborate with researchers from abroad, train undergraduate and graduate students. We have also been successful in collaborating among us in basic and applied research, as well as with colleagues from other areas such as transportation, computational biology, and economics. Although fruitful, this scenario is far from exploiting the full potential of the ACGO initiative. In particular, despite a significant record of collaborations across departments, the undergraduate and graduate programs remained largely unrelated. The ongoing challenge is to reinforce the communication across these areas. In order to achieve our goals, we are convinced that what is needed is to focus on two main axes: research and education. Below we explain the rationale supporting our conviction, the steps we have been taking in both areas, and how a FONDAP grant would greatly speed-up the achievement of our objectives and multiply their impact.

Research.

Education.

Our mid-term objective is to consolidate a research Center with a national and regional leadership role in the development, application and dissemination of the ACGO themes. The next sections describe a number of specific goals that we have set for this 5-year proposal. The requested funding will be used to support the research goals as well as the wider activities of the ACGO initiative, including post-doctoral positions, PhD scholarships, and conference organization. This will decidedly contribute to deepen and broaden our group capabilities, allow us to attract, train and retain more students and young researchers, and poise ourselves for faster advancement and higher research impact.

2 Research Themes

The ACGO seminar allowed us to identify many open questions in the areas of algorithms and complexity, discrete and continuous optimization, network equilibrium, game theory and mechanism design. While putting together this proposal, we made the strategic choice of focusing on a subset of the research subjects that would benefit from a multidisciplinary approach and hold the potential for collaboration. The research subjects that we selected are all concerned, in one way or another, with decision problems where the decisions and information are decentralized, and which are characterized by the lack of information and/or lack of coordination. Many of these questions arise from the study of large networks such as the Internet and urban transportation systems, where a multitude of agents make decisions in a decentralized manner, with limited information on the network characteristics or even its topology. Another common characteristic of the problems is their focus on algorithmic issues: we are interested in the mathematical structure of the objects and models, with the ultimate goal of designing algorithms for computing solutions. Due to space limitations we cannot provide a detailed description of each, so we refer to http://www.agco.uchile.cl for a more thorough discussion. The research topics were grouped into three major themes: Algorithms & Complexity; Algorithmic Game Theory; and Mathematical Programming.

2.1 Algorithms and Complexity

In little more than a decade we have seen a convergence of social and technological networks, with networks such as the Web characterized by the interplay between rich information content, the millions of individuals and organizations who create it, and the technology that supports it. Information retrieval from large data sets and distributed networks pose algorithmic challenges where efficiency and sensitivity to underlying assumptions rise to a new level of importance, while distributed procedures performed by uncoordinated agents lacking full information about the system gain relevance. This has driven a major shift of research in computer science to issues concerning efficient access, fast processing, classification, data mining of huge volumes of information, and mechanism design.

The heterogeneity of sources and media, and the lack of a centralized control over the contents, requires novel and more flexible tools for querying, navigating, and manipulating data. In content-based searching, data can be searched without need of tagging or interpreting it. The combinatorial approach reduces the problem to matching discrete multidimensional symbol streams for complex patterns, providing an effective alternative for text, audio, image, and multimedia searches. The gigantic amounts of data to be processed and the relative slowness of the interconnection network, make an ideal case to study compressed data representations that can be transmitted at reduced cost and, ideally, processed without decompressing.

The emergence of large dynamic networks also raises novel issues coming from the fact that knowledge of the exact link structure and edge presence is not guaranteed. New theoretical foundations and mathematical techniques are required to understand which properties are robust under small changes of the network structure, and providing meaningful results on large objects for which complete information is lacking. In this context, areas such as random graphs, phase transition, spectral analysis, probabilistic sampling, etc., have gained enormous relevance [116, 172, 164, 41, 74]. Besides the mathematical aspects, there is also a pervasive need for algorithmic developments associated to large networks. Just to illustrate, major shifts in Internet routing standards can be viewed as debates over the deficiencies of one protocol relative to another.

Considering our background expertise and the relatively small number of local researchers in the area, we aim to focus on three main topics: (i) new approaches to fundamental information retrieval problems for large volumes of data, (ii) sampling techniques to increase the efficiency of algorithmic procedures for data processing and for ascertaining relevant properties or identifying local structures in large objects such as networks, and (iii) distributed routing and information gathering in large unstructured networks.

• Adaptive Analysis: Traditionally, the analysis of algorithms measures the complexity of a problem or algorithm in terms of the worst-case behavior over all inputs of a given size. On large instances, this information might not be very useful as all reasonable algorithms behave similarly badly in the worst case. Adaptive analysis seeks to identify instances that are easier than others and to design algorithms that take advantage to escape the worst case behavior, bridging the gap between theory and practice. For example, Demaine et al. [67] showed how to compute the union of k sorted arrays (or k B-trees) in sub-linear time on easy instances, by measuring the difficulty of an instance as the cost of encoding a description of the union. The approach was extended to the intersection and difference of sorted arrays, applied to solve conjunctive queries in search engines such as Google [68]. Barbay and Kenyon [27] gave two other adaptive analysis for the intersection problem, along with applications to multi-join operators in relational databases and to pattern matching queries in semi-structured data (file systems, XML). Barbay and Chen [26] generalized this to the merging of planar convex hulls, using as a measure of difficulty the complexity of the certificate for the merging of the convex hulls. The analyses in [67] and [27] are not comparable and to this date no algorithm is known to be optimal for both simultaneously. We aim to develop a finer analysis combining the main features of both, along with an optimal intersection algorithm, and the derived algorithms to compute adaptively the merging of convex hulls in 2D and 3D.

  Many algorithms to find the convex hull of n points in the plane with worst case complexity (nlog n) have been known since the 1970s. Kirkpatrick and Seidel [120] described a better algorithm with complexity (nlog h), where h is the number of vertices of the convex hull. Since h is at most n the latter algorithm is never worse and often better than one which only optimizes for the worst case (improvements of [120] can be found in in [50, 184, 49, 168]). Afshani et al. [3] further refined this analysis up to any random permutation of a particular instance (“input order oblivious instance optimality”), and gave extensions to dimension three. We aim to further extend such results to higher dimensions, useful for multidimensional mechanism design and for the computation of correlated equilibria, and to relate the quantity of certificates available for a given instance structure and the easiness of finding one (e.g. maximal vectors, computation of meshes, prefix free codes).

• Data Structures and Compression: Combinatorial pattern matching (CPM) encompasses exact and approximate search of sequences for simple and complex patterns, including regular expressions and parameterized pattern matching [62, 147, 104]. It has a long list of applications, the most prominent being probably information retrieval in computational biology. CPM has been traditionally dealt with in sequential form, without resorting to any indexing data structure on the searched sequence. However, in order to handle the huge amount of data that arise in applications, index structures must be built on the text [14, 104]. Unfortunately, classical indexes have a high space usage, which renders them impractical precisely in the applications where they are most needed, namely, those handling huge collections of sequences.

  The last decade has witnessed important progress in the enhancement of compression mechanisms for sequences, giving rise to compressed self-indexed representations. These require space close to the entropy of the sequence, allow extracting any subsequence of it, and provide indexed searching in time sublinear in the sequence length [146]. Self-indexing can be generalized to searching non-linear structures such as trees [142, 80] and graphs [55]. For example, compact tree representations are useful for semistructured text databases (e.g., XML and HTML) in little space [80], while compact graph representations allow to solve large problems involving networks, such as computing Google’s PageRank or detecting Web communities, within main memory. This is relevant given that most graph algorithms are not disk-friendly. In particular, Claude and Navarro [55] showed that Web graphs can be compressed 10-fold while retaining fast access. Similarly, the study of combinatorial properties of images, grids, sets, permutations, mappings, partial sums, and other basic data structures, allows for compressed representations of those structures while retaining direct access and navigation operations. Applications include complex searches in computational biology, multimedia databases, and structured text retrieval. We intend to further contribute on self-indexed representations, including how they connect compressibility and adaptivity, and explore new application domains. Barbay and Navarro in [28] have already advanced in this promising line of research.

• Smoothed Analysis and Pattern Matching: An extension of the formalism of adaptive algorithms defines the difficulty of an instance as a function of the stability of the output under small random perturbations of the input (smooth complexity). The concept has been independently reinvented to study Machine Learning problems, and to express the quality of the solution produced by an algorithm as a function of the difficulty of the instance (as opposed to the traditional approach that uses the quality of the optimal solution to this instance). We aim to formalize the link between these two approaches, and explore alternative combinations of analysis.

  Smooth analysis was pioneered by Spielman and Teng [173] as a framework to explain the practical success of heuristics that do not admit traditional worst-case analysis. It is a hybrid of worst-case and average-case analysis that inherits advantages of both, by measuring the expected performance of algorithms under slight random perturbations of worst-case inputs. If the smoothed complexity of an algorithm is low, then it is unlikely that the algorithm will take long time to solve practical instances whose data are subject to slight noises and imprecisions. For instance the Simplex algorithm runs in exponential-time in the worst-case and yet in practice it is a very efficient algorithm. This was one of the main motivations for developing smoothed analysis and the celebrated proof that the Simplex algorithm has polynomial time smoothed complexity [173].

  Researchers have investigated the smoothed complexity of several problems, mostly numerical ones (e.g. [20, 46, 47, 19]) and some discrete problems (e.g. [25, 134, 174]). However, there are very few instances where smoothed analysis has been used to tackle problems concerning sequences. A notable exception is the work by Andoni and Krauthgamer [13] who initiated the study of the smoothed complexity of sequence alignment. In pattern matching one often finds problems where there is a significant gap between worst-case and average-case algorithmic complexity while practice suggests the latter is most relevant (e.g., in sequential searching both in the exact and the approximate case [63]). Smoothed analysis seems especially well suited to help explain such state of affairs. We intend to explore these issues, for the case of exact and also approximate string matching algorithms. More general variants might also be considered, such as multi-pattern matching, regular expression matching, and tree pattern matching.

• Testing, Sub-linear Time Algorithms, and Local Sampling: Testing and property testing, also referred to as the art of uninformed decisions [81], are rather new areas of computational theory that deal with the information that can be deduced from the input given that the number of allowable queries (reads from the input) is significantly smaller than its size. There is by now a large body of literature (see e.g. the surveys of Goldreich [97, 98, 99], Fischer [81], Kiwi et al [121], Ron [163, 164] and Rubinfeld [166]). One of the aims is to devise sub-linear time algorithms by avoiding having to read all of the input of a problem instance. The algorithms return a result without processing the whole input, thus lacking full information about the instance they are running on. Usually these algorithms use randomization and provide answers that are approximate, or wrong with some probability.

  Kiwi, Navarro and Telha [122] considered the approximate string-matching problem (in its on-line version where the text is not pre-processed) under a relaxed scenario that is still useful for most applications. Specifically, they relax the goal of listing all substrings of the text T at (edit) distance at most k from pattern P to that of listing each such position with probability at least 1 − ϵ. Using sampling techniques motivated by the testing paradigm they show how to beat the optimal expected time approximate string-matching algorithm of Chang and Marr [51]. We intend to further develop this approach and apply it to pattern matching algorithms and information retrieval procedures. A celebrated recent result due to Alon et al. [7] (see also [8, 44]) completely characterizes which properties of dense graphs are testable in terms of Szemerédy regularity partitions [40, IV.5]. To the best of our knowledge, no similar result is known for properties concerning ordered structures such as sequences and permutations. Given our interest in testing and pattern matching, we intend to address this anomaly in the development of the theory of property testers.

  The emergence of huge computer networks has enabled the study of very large and complex social interactions. Knowing the precise structure of such networks is algorithmically impractical and often impossible. This turns out to be an ideal application scenario for the testing paradigm, yet a better understanding is needed on how to handle and extract information from such objects. One approach consists in using randomized sampling techniques to drive a local exploration of a large structure (e.g. a network) in order to extract a smaller profile from which to identify a desired substructure (e.g. a cluster). For example, identifying dense subgraphs is an increasingly important task in the study of large networks. A local algorithm for finding dense subgraphs was given in [11, 12], which however requires complete knowledge of the link structure in the neighborhood where a dense subgraph is being sought. Since access to the graph’s link structure usually carries a cost, we aim to design local sampling algorithms that find dense subgraphs by accessing only a sub-linear number of its links.

• Network Routing: Network routing is the process of selecting paths in a network to send traffic, such as in telephone, electronic data, and transportation networks. In computer networks, routing is concerned with the flow of data and the design and analysis of the protocols that support it, a broad and active research area. Here we focus on locality of information and how it affects data flows.

  Routing strategies for navigating synthetic or real-world networks specify rules to move in a graph from a given vertex towards a target vertex along paths close to optimal. Although full-tables allow to route optimally, their use in large networks is limited since they require to store locally O(nlog k) bits (in a network of size n and maximum degree k). Practical routing strategies are forced to make assumptions on the structure of the network in order to guarantee delivery of the message or to route using suboptimal paths. Dragan and Matamala [72] proposed a new routing strategy where distances in a spanning tree are used as global information while routing decisions are taken locally. In this approach the local memory requirement is reduced to O(k log(n)) bits plus the information for computing distances in the spanning tree O(log ²(n)). Even though message delivery is guaranteed, delays can be larger than the length of the shorter paths. One specific aim on this proposal is to enrich our knowledge about classes of networks where we can guarantee that our strategy is optimal, a fact already established for some well-structured networks.

  In rapidly changing dynamic networks memory efficient routing strategies such as the one discussed in the previous paragraph are impractical, mainly because of the difficulty of efficiently refreshing the information stored at the nodes. A prime example of this are unstructured Peer-to-Peer networks formed dynamically by ad-hoc additions of nodes and where no algorithm is provided for organizing or optimizing network connections. When a peer wants to find a desired piece of data, the query has to be flooded through the network looking for peers that have the sought resource. We intend to formally derive some of the results announced in [103]. Specifically, we would like to explain how does the optimal routing topology change as a function of the network load, and design protocols that would drive the network towards near optimal interconnection patterns. We would also like to explore related topics including information gathering in distributed systems [130, 157], and the design of efficient message routing algorithms with anonymity guarantees weaker than those of the fully anonymous channel model [52].

2.2 Algorithmic Game Theory

Game theory provides a natural framework to model situations where decisions are decentralized and the actions of each agent influence the well being of others. While this is a prominent feature in many real-world situations, the intrinsic complexity of computing equilibria has biased the analysis towards centralized decision making, emphasizing combinatorial optimization and operations research methods. For instance, the movement of people and cars within a city, or the flow of packets in communication systems have been addressed as optimal transportation problems, the assignment of jobs in a factory as a scheduling problem, and the relation between producers and consumers as a problem of logistics of a distribution system. In recent years, a renewed interest has come from the need to deal with conflicting situations such as the acute congestion phenomena observed in modern urban transportation and communication networks that occur when decisions are decentralized and multiple agents compete for the scarce available resources. The focus is thus shifted from a centralized perspective to models that naturally fit the framework of game theory: the transportation problem becomes one of network equilibrium, the scheduling problem turns into a mechanism design issue in which agents submit tasks which are processed according to certain rules, the logistic problem one of competition among strategic producers and consumers.

Although game theory is a mature discipline, there are few tools for the actual computation of equilibria, its complexity analysis, and the characterization of properties such as efficiency and fairness. On the other hand, player rationality, perfect information about histories, and complete information about other players payoffs are questionable assumptions in situations with a large number of agents or strategies. In such contexts, dynamic models for the adaptive behavior of agents can be more adequate to describe the evolution of a system towards equilibrium. These dynamics may provide in turn inspiration for new algorithms to compute equilibria. The recent books [154], [171] and [190] reflect the vitality of the area and the variety of questions that are currently investigated.

In this proposal we focus on some specific algorithmic and modeling questions related to the dynamics of network flows, the optimality of scheduling coordination mechanisms, the effects of market power in producer-consumer interactions, and the assessment of the approximate efficiency and fairness of equilibria. These questions naturally relate game theoretical issues with algorithms, combinatorics and optimization, and thus showcase the need for interdisciplinary work. Specific questions that we plan to address include:

• Learning and Adaptation in Network Games: Learning and adaptation are fundamental issues in repeated games (see [92, 190]). Most adaptive procedures, such as fictitious play and its variants [45,  92, 112, 159], no-regret [106, 108], exponential weight [87], and calibration [91], although flexible and robust, assume an underlying rationality of the agents that is too demanding for games with a large number of strategies and poorly informed players. A simpler adaptive rule that relies only on the sequence of realized moves and payoffs is reinforcement [18, 43, 77]. Its convergence has been established for zero-sum 2-player games and for some games with unique equilibria [30, 127]. An alternative approach, using a simple mechanism based on a minimal piece of information, was recently proposed in [57] as a model for network flow equilibrium. It turns out that in the long run this dynamic stabilizes on a steady state that can be characterized as a Nash equilibrium for a particular limit game.

  One relevant research direction is to develop dynamic models for the adaptive behavior of drivers in a congested transportation network, assuming bounded rationality and limited information. Can coordination be attained using a decentralized mechanism? Are the steady states and/or limit cycles connected to Nash or Wardrop equilibrium? How do these dynamics capture the statistical variability of flows? How does this extend to potential games? How does market power affect the dynamics and equilibria? Can we exploit the dynamics of urban traffic to design decentralized protocols for routing and congestion control of Internet flows?

• Equilibrium Flows in Dynamic Networks: Ford and Fulkerson [86] introduced the notion of dynamic flow in a network. In this context, the capacity of an arc bounds the amount of flow that can traverse the link in a time period. Thus, a natural question is to determine the maximum amount of flow that can be shipped through the network on a given horizon. This problem has been widely studied from a centralized perspective  [29, 84, 85, 94, 113, 139, 185]. Our interest is to study equilibrium flows in this dynamic setting as a model for evacuation problems, city traffic, and Internet routing, where players compete to ship as much flow as possible between given sources and sinks over a fixed time window, with queuing delays arising from the maximum flow allowed to enter each arc per time unit. Among the questions we would like to address are: Which is the most pertinent model? How do we compute equilibria? How do we measure their efficiency and fairness?
• Selfish Scheduling: Machine scheduling problems have their origin in the optimization of production systems. Their formal mathematical treatment goes back to the 1950’s. In this setting, a family of n tasks have to be processed in m machines, with task i requiring a time p_ij if processed on machine j. In addition, tasks may have a weight, a release date, a deadline, and other characteristics that impose additional constraints, including time windows, precedence constraints when certain tasks must be processed before others, or processing delays when switching a task from one machine to another. Moreover, there is a variety of possible machine environments such as machines that work in parallel at different speeds, or sequentially in what is called the job-shop environment. The classical problem is to find a schedule to process tasks as to minimize an objective function such as the makespan or the weighted average completion time of all tasks. Recently, distributed environments have emerged as the main architecture for parallel computing. Thus, a central question is to understand machine scheduling problems where each task is managed by a selfish agent, who is only interested in its own completion time. In particular, it is important to understand the existence, uniqueness and characteristics of equilibrium for different processing policies. In the last decade significant effort has been put in studying these type of competitive scheduling problems [22, 54, 73, 109, 114, 125]. We aim to investigate the existence, uniqueness and characteristics of equilibrium, both in the case of complete and incomplete information, under different social objectives. Which are the best processing policies? Which ones minimize the price of anarchy? Is this price of anarchy constant for some social costs?
• Market Games: Traditional Cournot and Bertrand market-competition models consider that producers of different goods decide the quantity they are going to produce or the price at which they are going to sell [137]. Strategic consumers eventually learn these decisions and decide whether or not to buy and from whom. These models are simplified representation of the operations of a firm. Two important extensions are to consider more general pricing functions that map production quantities to prices (supply function equilibria [124]) and the study of localization decisions (pioneered by Hotelling). In modeling price as a function of quantity one can study the revenue management decisions used in the airline industry. Basically firms postpone their pricing decisions and adapt to the best demand forecast available. Localization is also a critical decision of firms, which in fact influences future prices and production quantities. We would like to study market games in which firms and consumers compete through different channels such as localization and price functions. Are there equilibria? Which are their structural properties? How hard is to compute them? How is efficiency affected by increased competition? Can these models help to understand airline revenue management and electricity markets?
• Mechanism Design: In situations where information is dispersed and/or the control over actions is decentralized, a designer is faced with the problem of choosing appropriate rules of the game which perform well for different instances of the problem. Good performance requires, in general, truthful information transmission and/or coordination of activities between the different agents. Examples abound: mechanisms for the adequate provision of public goods [148], revenue maximizing mechanisms for the sale of an object [117, 143], and scheduling systems with a low price of anarchy [54]. Mechanism design is well understood as long as the problem is static, private information is single dimensional, and agents utilities are quasilinear in money. However, many interesting real world problems which fall under the category of mechanism design do not satisfy these assumptions. For example if multiple goods are sold, private information is multidimensional [117, 160]. Also, if the designer lacks commitment power the revelation principle does not hold, and if players face budget constraints their utility is not separable. In some cases, money may not even be available to compensate agents, such as in matching procedures for kidney donations. Our main interest is to characterize good mechanisms according to some metric, and to find efficient algorithms to compute them. Furthermore, can optimal mechanisms be approximated using integer programming tools at least in particular cases? Are such problems computationally tractable? How far from the optimal solution is a mechanism with message-space dimension below that of private information?
• Games, Bilevel Problems and Robustness: Bilevel problems are optimization problems where some variables are restricted to be optimal solutions or Nash equilibria of a second level problem. Such models are general enough to encompass mechanism design as well as optimization problems with multiple agents. Recent work on robust Nash equilibrium [4] and network games, suggests that similar models could be developed for bilevel programs. We plan to address robust bilevel problems, including defining alternative models for robustness and exploring the price of robustness. Other research directions that we plan to address are: obtaining approximate bounds for problems with approximate complementarity constraints, using homotopy methods to work on the sensitivity with penalized complementarity constraints, and exploiting the sensitivity analysis from convex relaxations of the bilevel program and extend to the case of bilevel problems behavioral measures used for convex conic problems [158, 88]. In some cases, bilevel programming can be formulated as mixed integer programs (MIP), where the integer variables are used to represent the complementarity constraints. We believe that the sensitivity analysis on the linear or disjunctive programming relaxations of this MIP can provide meaningful information on how the original problem changes.

2.3 Mathematical Programming

What we know today as Mathematical Programming was probably born in 1947, when G. B. Dantzig [65] invented the Simplex method for solving Linear Programs (LP). Three key ingredients related to this event were (1) the discovery that many relevant problems related to optimally allocating scarce resources could be modeled as linear programs [118, 119, 181, 183], (2) the theory of linear programming which provided solid foundations for designing algorithms [93, 182], and (3) the first computational method able to solve practical-sized problems. Nowadays, the field is relevant to industries and research disciplines ranging from Airlines and Mining to Economics and Biology. The Institute for Operations Research and Management Science has put up a website (http://www.scienceofbetter.org) which showcases success stories of mathematical programming applications in business and the management sciences. This success has been fed by the interplay of convex analysis, optimization, algorithms, data structures and complexity.

The last twenty years have seen key advancements in the field. On the modeling side, new approaches for tackling uncertainty have focused on the robustness of the solution [6, 31, 32, 33, 151], while new developments on Stochastic Optimization [38, 149, 156, 169] have facilitated solving larger problems and addressing new applications [4, 32, 36, 48, 96, 170]. On the algorithmic side, the development of Interior Point Methods (IPM) has produced new and faster algorithms for LP, and has led to efficient methods for broader classes of convex optimization problems including Second Order Cone Programming (SOCP) [6] and Semi-Definite Programming (SDP) [180]. Improvements in algorithms, polyhedral theory and data structures  [39] have led to a spectacular increase in our ability to solve general Mixed Integer Programming problems (MIP) [15, 16, 17, 39, 144]. These elements, together with the constant hardware improvements, suggest that it is possible to achieve a qualitative leap in the type and size of optimization problems that will be solved in the future. Being able to achieve this qualitative leap and address the open questions, requires, more than ever, a coordinated effort to exploit the interplay of the main areas of this research project: Algorithms, Combinatorics, Game-Theory and Optimization. We describe below our research agenda on mathematical programming. This research touches on different types of problems —nonlinear programs, stochastic programs, mixed integer programs— addressing questions about size, uncertainty, sensitivity, robustness and complexity; and looking for better solution algorithms.

• Sensitivity and Robustness: Input parameters of optimization problems are typically given in the form of numerical data that may be subject to variability or measurement errors. Furthermore, the practical implementation of an optimal solution might be subject to errors.

  Sensitivity analysis addresses the question of how stable is the solution of a problem to changes in the data. Informally, a problem that is relatively stable represents a robust model, while solutions which are immune to changes in the data within a certain range are said to be robust. In Nonlinear Programming, regularity properties that have proven to be useful for sensitivity analysis are the Aubin property and strong regularity [71]. However, known abstract results are not always easy to apply in practice as they fail to exploit the particular structure of specific problems. By focusing on Nonlinear Conic Programming (NLCP), we expect to develop tools to assess the sensitivity of a particular instance. Strong regularity has been recently characterized, in terms of second-order optimality conditions, for nonlinear SOCP [42] and SDP [178], and we plan to investigate it for general NLCP. Motivated by tools developed for the SOCP case in [155], we also expect to obtain a similar characterization of Aubin’s property for nonlinear SOCP, which could be extended even for general NLCP. Another approach to assess how sensitive is an optimization problem with respect to data perturbations is to use geometric characteristics of the instance, measured by means of included and containing ellipsoids relative to the feasible set. These constructions are common in convex optimization [75, 102] and have been used to evaluate the complexity of algorithms for convex optimization [89, 90]. We propose to investigate, theoretically and computationally, the explanatory power of these geometric measures regarding stability, and their connection to other stability measures.

  Robust optimization aims to compute solutions to mathematical programming problems which are stable under changes in the input data. Although this is a difficult task, recent methods have been successful in computing robust solutions for several problem instances. For example, robust versions of standard LPs are equivalent to SOCPs which are still highly structured convex problems [31, 131], and can be solved using IPMs [177]. Nevertheless, for an unstable problem, robust solutions might come at the price of a severe deterioration in the objective function value. Surprisingly, it has been observed in practice that the extra cost of a robust solution is small [32, 36, 96], although there is scant theoretical understanding of the price-of-robustness [31], that is, the increase in cost between a robust solution and an optimal solution. We plan to address important types of optimization problems such as MIPs, for which robust optimization theory and algorithms have yet to be developed.

• Stochastic Uncertainty: Stochastic Programming, which combines Math Programming and Probability, provides tools for optimization problems in which uncertainty arises from random variables whose distribution is (at least partially) known. Among the variety of models in this class we find the Chance-Constrained Programming (CCP) in which deterministic constraints are replaced with probabilistic ones requiring that the random variable lies in the feasible set with high probability [38,  169]. Applications of CCP include financial models, classification of randomly generated data, reliable telecommunication network design and mine planning. Such problems are usually intractable, so sampling methods have been proposed and successfully employed to obtain good candidate solutions [149, 133, 156, 48]. We will investigate theoretical properties of CCP in order to develop better sampling algorithms for the above mentioned applications.

  On the other hand, it is often the case that only partial information about the probability distribution is available. As an example, consider regression models where, instead of an exact pattern, one only has some random data sets generated according to an unknown probability distribution. If the first and second moments are known, it is possible to derive a SOCP formulation for a CCP-type linear regression model for the worst case in the class of all distributions with given mean and covariance [170, 145]. This may be solved using generic IPMs, but for large data sets it would be very useful to specialize them to obtain more efficient algorithms. We plan to extend this approach to nonlinear regression and data classification models, and to explore tractable formulations based on other types of incomplete information on the actual distribution.

  Finally, the introduction of uncertainty in combinatorial problems through extended scenario formulations leads to huge models for which most of the known valid inequalities have proven to be weak [133]. However, these models are often structured as they come in the form of several problems tied together by common capacity (or in this case probability) constraints, which include integer or semi-continuous variables. In many situations, such as open-pit mining, production planning, central power generating planning, and time-expanded production scheduling, the original deterministic problem naturally has a network-like structure that interacts with global side-constraints. We plan to develop algorithms for these MIPs and study their polyhedral structure from a theoretical and computational viewpoints.

• Integer Programming: As mentioned above, many real-world problems naturally lead to very large scale, non-convex, discrete optimization problems. This constantly pushes the need for better algorithms for large MIPs. An important aspect in MIP-solving today is cut-generation. It is known that Gomory cuts are numerically unstable and prone to rounding errors that lead to invalid cuts [135]. To work around this problem, Dash et al. [58] have shown that by controlling rounding modes it is possible to add numerically safe Gomory cuts in a much more aggressive manner. We are interested in further studying the Gomory mixed integer rounding cut, and enhancing its computational performance. Another important recent development is the interest in cuts derived from multiple constraints [59, 10, 128, 60, 100, 101, 61,  69, 78]. Unlike Gomory cuts, the separation problem does not have an analytical solution forcing the use of separation techniques such as in [15]. We plan to further investigate approximations to the separation problem of these inequalities, trying to find theoretical approximation factors and evaluate them in practice; focusing on multiple row cases, and in practical implementations for general MIPs.

  A common problem in many hard MIPs is that branch and bound algorithms terminate too early or the improvement over time tends to zero as the branch and bound tree grows [16, 105, 129]. One possible way around is to summarize the information of a partial branch and bound tree in a more succinct way [2, 1, 70]. However, at least in theory [102], it is possible to transform a partial branch and bound technique into a set of cuts to the original problem. Our aim will be on practical implementations of these techniques for general MIPs, including extensive evaluation on standard testing sets.

  The other key element for solving large-scale MILP problems is to generate feasible solutions quickly. In order to find such solutions, many different heuristics have been proposed for general MILP models [23, 24, 64, 82, 83, 107, 110, 132, 167]. We focus on two heuristics: aggregation and local-search. While aggregation has been extensively studied in LP [175, 176, 191, 138, 162], for MIPs the experience is limited to special-structured problems [126, 152, 79]. Concerning local-search heuristics for general MILP, to our knowledge all of them require solving the original linear programming relaxation and branching, which may be prohibitive for large problems. In this project, we want to develop practical implementations of these branch and bound, aggregation, and local search techniques for general MIP problems, and further study them from a theoretical viewpoint. We also expect to understand which integer programming formulation structures are better fitted for a local-search heuristic, and thus suitable for a parallel computing environment where different processors can explore diverse neighborhoods of an incumbent solution.

• Nonlinear Programming: Algorithms for linear and nonlinear programming cross-fertilize each other. While the Simplex method strongly influenced the first methods for nonlinear programming, the IPMs conceived originally for nonlinear problems led to polynomial time algorithms for LP and other structured convex programs [165, 186, 150, 95]. Tools that proved useful in both contexts include penalty and Lagrangean approaches, as well as the Bundle and Proximal methods [111, 136]. On the other hand, decomposition techniques designed for linear optimization such as column generation and Benders decomposition, are now used extensively together with Lagrangean methods to solve large-scale nonlinear models [66, 34, 5, 35, 37]. Interestingly, efficient decomposition methods for nonlinear programming still pose challenges as they require fast non-linear optimization algorithms, warm starts from prior solutions to related problems, and exploiting the problem structure, perhaps through geometric measures.

  Decomposition methods have an important impact on the performance of Proximal Point Algorithms (PPA) [76], which have proved useful for solving convex optimization and monotone variational inequalities [136, 140, 141, 9, 56, 115, 123]. Moreover, for problems on a product space, PPA can be efficient when combined with the augmented Lagrangean approach [53, 161, 187], especially under separability assumptions that occur frequently in applications [21]. We intend to investigate this type of methods combining penalization, projection-extrapolation steps, relaxation, and augmented Lagrangian techniques. We will address theoretical questions and the implementation of these algorithms, including implicit-explicit versions and bundle methods for nonsmooth problems [153].

  When IPMs are used within a Branch and Bound tree or in a decomposition method, the problem of warm starting from an available solution is critical. While the Simplex method does very efficiently, when the problem includes QP or SOCP elements and thus IPMs are a good alternative, the situation changes dramatically. The main challenge, is to develop effective warm start procedures for IPMs in a branch and bound context, so that we can quickly solve a sequence of related subproblems. We are interested in warm start heuristics using special problem structure, an area which has not been thoroughly studied. In particular, we will investigate how previous warm start techniques for linear programming [188, 189] can work for QPs, SOCPs and more general convex, nonlinear models. We will also develop new strategies for modifying the initial point to achieve efficient performance, establishing also the necessary conditions.

  Finally, as complexity remains one of the central issues in IPMs, we want to explore the relations of some geometric measures, based on radius of inscribed and circumscribed ellipses, to the complexity of IPMs. We will concentrate on lower bounds, as upper bounds are already available. Existing results for the Ellipsoidal Algorithm show that those measures can be used in connection to the number of iterations required by the algorithm, implying that an instance with poor geometry might require longer computation time [90]. We conjecture that similar results should hold for IPMs as well as for algorithms based on barrier functions. Of particular relevance to this line of research are the work of Todd [179] and Nesterov and Todd [151]. The results of this line could be used to address questions on how a certain decomposition of a problem might affect the geometry and complexity of the resulting subproblems.

3 Undergraduate and Graduate Training

Training plays a central role in this proposal, as we believe that a major impact in society is achieved through the incorporation of our students to the productive sector. We will carry out activities on three grounds: undergraduate, graduate, and postdoctoral training.

3.1 Undergraduate studies

ACGO Minor: The School of Engineering at the Universidad de Chile launched recently an initiative in which departments or groups of faculty put together a set of courses (either existing or new) which are then offered as minors to engineering students across all disciplines. Our group launched a minor in Algorithms, Combinatorics, Games and Optimization (ACGO) which combines courses from Math (Combinatorial Optimization, Complexity), Computer Science (Algorithms and Data Structures, Design and Analysis of Algorithms), and Industrial Engineering (Optimization, Operations Research). In addition we decided to offer a new course on Algorithmic Game Theory, the first such undegraduate level course at Universidad de Chile. This minor aims to provide simultaneously the mathematical rigor, the modeling ability and the computational skills to tackle relevant problems. The minor was recently approved by the School of Engineering, and thus, starting from 2010, we expect to see the first enrolled students. As an indicator of the interest that the ACGO minor might have, 37 students attended the Algorithmic Game Theory course taking place in this second semester of 2009. With time, we expect to add elective courses to this minor and to revise the fundamental subjects.

Winter Camp: One of the best ways to motivate young people’s interest in science is by exposing them to a first hand experience on scientific research. An initiative that we will carry out in this direction is a yearly ACGO winter camp. This will consist of a 3-day school in which students will have two or three courses thaught by ourselves on advanced topics, with lectures in the morning and exercise and open problem sessions in the afternoons. The location will be somewhere near Santiago, away from our daily duties. A subset of us (Correa, Kiwi, Matamala, Rapaport) organized two such schools in 2007 and 2008 with an attendance of 20 students. This activity was discontinued because of lack of funding. We expect to re-launch this activity for which we request moderate funding. We also expect that the student attendance will grow as the ACGO minor becomes better known.

Research Visits: Another activity which we believe is extremely useful for our advanced undergraduate students is the oportunity to visit research centers abroad. In the past, we have sent as many students as our funds have permitted (to places such as Charles University, TU-Berlin, CWI, Université Paris 6, Waterloo University, Yale University, UBC, among others). However, it is usually difficult to raise funds for such activities and therefore we are also requesting funding for them.

3.2 Graduate studies

ACGO Graduate Program: One of our mid-term goals is to develop a doctoral program in ACGO. Rather than creating a new program, we believe that a scheme along the ACO programs of Georgia Tech and Carnegie Mellon University, is well suited to our group. Indeed, Universidad de Chile currently has PhD programs in Applied Mathematics, Systems Engineering, and Computer Science. We plan to develop a joint curriculum for these doctoral programs that will allow students from all the involved programs to gain a solid backgroud in the ACGO topics. This will require a specific effort to adapt some of the course programs to make them accessible to students with different backgrounds. Furthermore, we plan to increase the course offering, incorporating selected topics which are not currently available, such as an advanced course on Game Theory and another one on Advanced Algorithms. Also, the ACGO program will provide a wider array of research subjects for graduate students to specialize in. Some of them may benefit from co-advising by researchers involved in this proposal. In addition, the ACGO program will also be open to PhD students at the Engineering School of Pontificia Universidad Católica de Chile, through an existing agreement between both Universities. Specific funds are requested to cover 8 doctoral scholarships per year, as well as some budget to allow students to attend international conferences and/or to spend some research periods abroad while working on their thesis. We also seek funds to cover one-semester visiting positions for external professors who will deliver advanced courses in the framework of the ACGO Graduate Program.

Summer School: In 2006, we started to organize a summer school in discrete mathematics for graduate students and advanced undergraduates. The format is 3 courses by invited professors (5 lectures per course, one 75 minute morning lecture per day) with local TA’s in charge of afternoon problem sessions and grading. The courses offered in the past and next versions have been:

2006

Graph exploration and graph searching, Pierre Fraigniaud, CNRS, U. Paris-Sud.
Many facets of graph colorings: structure and complexity, Jaroslav Nesetril, Charles U., Prague.
Foundations of distributed computation, Sergio Rajsbaum, U. Nacional Autónoma de México.

2007

Future leader selection for distributed systems with faults, Antonio Fernández, U. Rey Juan Carlos.
Enumeration of labelled graphs, Marc Noy, U. Politécnica de Cataluña.
Polyhedral techniques for combinatorial optimization problems, Mourad Baiou, U. Clermont II.

2008

Approximation algorithms for scheduling, packing and graph problems, Klaus Jansen, U. Kiel.
On-line, parametrized and adaptive algorithms: three faces of the same coin, Alex López-Ortiz, U.Waterloo.
Applications of chance to algorithms: from speed-up to self-correction, Nicolas Schabanel, CNRS, U. de Chile.

2009

Smaller and faster: succinct data structures, Jérémy Barbay, U. de Chile.
Algorithmic game theory, Christoph Dürr, Ecole Polytechnique, France.
Probabilistic combinatorics and concentration inequalities, Jacques Verstraete, U. California, San Diego.

2010

Geometric optimization problems, Friederich Eisenbrand, Ecole Polytechnique Federal de Lausanne.
An introduction to topological graph theory, Gelasio Salazar, U. Autónoma San Luis de Potosí
Games with reputational perturbations, Ennio Stacchetti, New York University

The last two versions already had an ACGO flavor, including topics in game theory, algorithms, optimization, and discrete mathematics. Attendance has grown from the original 25 to over 50 participants in 2009, with 2/3 of the students from mathematics and 1/3 from computer science, operations research and other disciplines.The school started to attract international students (9 students from Argentina, Brazil, México and Perú in 2009). In the coming years we expect the school to attract a larger number of students from other Latin-American countries, exceeding the currently available funds. In order to keep this activity alive we need significant funds which we plan to obtain through this proposal.

3.3 Post-Doctoral Training

We are strongly interested in attracting talented postdocs. In the past, we have been individually successful in attracting good postdocs and inserting them in academia. For example, Claudio Gutierrez has now a permanent position at the Computer Science Department of U. Chile, Eduardo Moreno and Karol Suchan are currently faculty at U. Adolfo Ibáñez, while Pedro Jara now holds a position at U. Santiago. Furthermore, we also had postdocs that have taken positions abroad, including Fedor Fomin (U. Bergen), Nicolas Nisse (INRIA), Fréderic Babonneau (ORDECSYS-Geneva), Thierry Champion (U. Toulon), Karine Pichard, and Jean-Philippe Mandallena (U. Nîmes). Our budget considers substantial funds in order to cover 3 postdocs per year.

4 Synergic activities

Since this proposal is inherently multidisciplinary most of our activities include people from different research areas. Of course, the ACGO minor and planned ACGO doctoral program are good examples of how this desirable interaction will certainly take place. However, we believe that the added value of a multidisciplinary approach becomes more evident in less formal activities which happen regularly. We list below some of the activities we intend to carry out in order to provide a collaborative atmosphere.

The heart of our current activities is the ACGO seminar, started over a year ago. This is an informal brainstorming session in which we discuss ongoing research, and one one of us, a visitor, or an invited speaker goes to the blackboard and presents a problem of his current interest. The seminar also provides a good opportunity to chat and see each other on a regular basis. Interestingly, the attendance has been growing with more faculty, students, and postdocs, and has already given rise to collaborations. We definitely expect to continue with this activity and keep it as stimulating as possible. In particular we would like to have modest funds to support it.

We also plan to have several instances in which we will escape from our daily duties to interact with students, visitors and with each other, in a flexible framework with plenty of time for research discussions. Specifically, we plan to have two workshops per year, one internal and one with external visitors. These thematic workshops will deal with topics at the interface of our research agendas. For instance, the first year we plan to organize a workshop in the interface of Algorithms and Economics. Our summer school and winter camp also fall in this category of activities having, additionally, a much larger number of student participants. In the annual internal workshop we will also spare some time to organize as a group and plan future activities. On the other hand, we plan to organize three larger conferences for the duration of the project, these require some substantial work but are good means to give international visibility to the local activities. Possible candidates are ISAAC, CPM, LATIN, LAGOS, and IPCO.

As our team is spread out among several departments and institutions we think it is important to set up some physical space for the Center. This will be located at the School of Engineering at U. de Chile and will provide comfortable space for the project participants, as well as students, visitors, and postdocs. The space will be designed so as to encourage discussion and cooperation, becoming the natural space for all involved researchers to work in their collaborative projects.

The previous activities will foster our ties with national peers as well. Not only the project already incorporates participants from several institutions (UCH, UTFSM, UAI, PUC, UNAB, Yahoo Research), but also we expect the project will promote, in Chile, the ACGO field as a whole and thus our national collaboration network will naturally grow.

5 International Cooperation

As it can be inferred from our economic proposal, for this group it is particularly important to both have a strong international presence and to permanently bring top researchers in the area to Chile. This can help us significantly in two key areas: training and scientific productivity. With these objectives in mind the group plans to both build up on well-established international connections and develop new ones. At the level of individual collaborations, the group has well-established links and active research collaborations mainly with researchers in the US, Canada, Germany, Brazil, and France. Moreover, there has been significant interaction over the years with researchers at MIT, Georgia Tech, U. Montréal, and different centers in France, which have led to many students pursuing their Ph.Ds in these centers, and a steady flow of researchers visiting in both directions. In what follows we describe some specific activities that we plan to develop in the 5-year period of this grant.

First, we are devoting particular attention in inviting foreign researchers to visit us and spend time collaborating with some of us. In particular, this will allow us to strengthen the research partnerships created in the past and explore new ones, and it is crucial to the basic research component of our proposal, significantly helping us to raise the output level of our scientific endeavors. Mirroring this, we plan that each of our members will spend part of the research funds to go abroad to work one on one with colleagues.

Secondly, we plan to invite key members of the international research community to spend some time with the group. The idea of these visits is twofold: on the one hand the direct scientific cooperation with the project members, on the other the teaching of some course in some important topic for advanced students and professors alike. Some of these will be semester-long visits, as this will expand the horizons of the project and reinforce the areas where we currently lack critical mass. In the same line, and strongly connected to our training program, we plan to have 3 invited speakers for each of our summer schools. We hope these visitors will eventually develop research projects with us, will bring new frontier topics to the school participants and will also strengthen the scope of our international presence.

Also connected to our training activities, we plan to finance students working on their research projects in Chile, and have them spend short-to-medium periods at research centers abroad. This will increase the quality of their research, make it more visible and also open new avenues of research to them. The quality of our students and our established connections abroad makes us confident that our students will go to top-notch institutions, their learning will be greatly enhanced, and this will reflect back in the quality of our group. Finally, an important activity will be our annual international workshop described in the previous section, and the organization of three international conferences.

6 Outreach activities

In the last few years we collaborated with the main science museum in Chile, Museo Interactivo Mirador (MIM), which over 50.000 visits per month. Under this collaboration program we set up two exhibits (one of them still on display), illustrating basic aspects of Geometry and Computer science. This activity was discontinued because of lack of funding. Since it was a very successful outreach strategy, we plan to create other interactive displays allowing kids and parents to learn aspects of Algorithms, Game Theory, and Optimization.

The topics of our research proposal appear in many fields of engineering. We believe that it is central to give undergraduate students a chance to integrate these ideas. In this line, in addition to our ACGO minor, we plan a series of special seminars (two each semester) showing experiences where the joint usage of Algorithms, Combinatorics, Games and Optimization have led to innovative and successful solutions of engineering issues.

Secondary education in Chile is deficient in developing math skills. Our research topics are well suited to develop advanced mathematical thinking. Networks and graphs, for instance, are simple and intuitive mathematical objects that can be introduced in the classroom as a very helpful learning tool. They can be easily motivated by interesting applications that allow elegant and concrete solutions. Young students can grasp fundamental algorithmic and mathematical concepts by learning basic graph theory. We intend to give short courses and talks, and to produce educational material on graph theory adequate for high school students and teachers. On the other hand, in order to reach students directly, we plan to develop a website and a facebook community where we will post problems every two weeks, and challenge students to come up with answers. Later, we will show the solution and different methods through which the problem can be tackled. Students who actively participate will be invited to a math camp at the end of the year.

As it can be inferred from the researchers curricula, our group has a substantial experience in developing joint projects with industry (e.g. airline revenue management for LAN-Chile and NCR, production planning for wineries, open-pit mining with CODELCO, inner-city routing for Lafarge, embarked system for automated conduction of freight trains, etc.). Although the main focus in this proposal is on research and education, we expect industrial collaboration to continue in the forthcoming years, including the development of industrially-oriented thesis subjects. Once a year, we will also organize a dissemination seminar providing professional audiences with an update on the progress of ACGO related areas and their potential impact on Chilean industry and public sector. Funding for applied projects should come primarily from the industrial partners, so we are not asking for such support in this proposal.

References