Ramamoorthi Ravi - US grants

Abstract for GRAPH-THEORETIC APPROXIMATION ALGORITHMS (NSF #0105548)
PI: Ramamoorthi Ravi, Carnegie Mellon University.

The increasing size of communication and information networks has motivated
several new problems in the design of networks with low cost and high
resilience; Many of these problems are known to be prohibitively expensive
in terms of computing power to solve to full accuracy. Yet these problem
abstractions capture models from a variety of application areas such as
communication network routing, multicasting messages in large
networks, VLSI layout, and transportation networks with economies of scale.
The research in this proposal aims to advance our fundamental knowledge of
the structure of good solutions to such inherently intractable computational
problems involving networks. The investigators will develop approximation
algorithms for these problems -- these are heuristic methods that trade off
some accuracy in the solution in return for lowered computational resources,
in a quantifiable way. The research will involve the application of and new
discovery of results in the theory of graphs to guide the design of these
heuristic solutions.

In particular, the investigators will design polynomial-time approximation
algorithms with improved performance ratios for many basic graph-theoretic
problems including the problem of augmenting a tree to make it
two-connected, buy-at-bulk network design problems and the minimum $k$-cut
problem. The investigators will continue their ongoing study of bicriteria
network design problems (problems that involve two objective functions to be
optimized simultaneously) to design improved bicriteria approximation
algorithms for many spanning tree problems arising in practice; These
problems involve a combination of commonly studied objectives such as the
maximum node degree, diameter and total cost of the tree. The research
effort will focus on the theme of studying natural mathematical programming
formulations for these NP-hard problems and attempt to derive improved
approximation guarantees via rounding algorithms that will also establish
the integrality gap of these basic formulations.

Algorithms are the basic procedures by which computers solve problems. With the explosion in the use and connectivity of computers, and in the sizes of the data sets being used, the performance of algorithms is becoming increasingly important. Being able to solve a problem ten times faster, for example, could mean designing a drug next year instead of several years later, or reducing the cost of developing a new space structure by allowing faster and more extensive computer simulations. Over the past 30 years there have been significant advances in the basic theory of algorithms. These advances have led to a "core knowledge" concerning algorithms and algorithmic techniques that has now been applied across an amazing diversity of fields and applications---surely more broadly than calculus is now applied.

The problem, however, is that there is a large gap between ongoing theoretical research, and the current use of algorithms in applications. It often takes more than ten years for the core ideas in a new algorithm to make it into an application, and ongoing theoretical research often does not properly address the needs of the applications. The purpose of the Center is to bridge this gap so that efficient and effective algorithms can be deployed more rapidly. This will be achieved through (1) a set of Problem Oriented Explorations (PROBEs), (2) developing an extensive set of web resources on algorithms, and (3) educational activities including holding workshops for educating teachers. The PROBEs will bring together algorithm designers and domain experts to rapidly deploy new algorithmic ideas within a specific domain.

This proposal seeks continued funding for the PI's work in his principal research area of Approximation Algorithms. Previous NSF-funded work by the PI's research group has successfully formulated and solved several interesting problems for approximation including the Buy-at-Bulk Network Design, $k$-Minimum Spanning Tree, Group Steiner Tree, and the Degree-bounded Minimum Spanning Tree problems. Our contributions to this area include mathematical programming relaxations of hard problems and novel ways to round such relaxations using deterministic and randomized rounding techniques, as well as new problem formulations.

The focus of this proposal is to address the solution of computationally hard problems in the vein of approximation algorithms by moving closer to more real-world constraints.
Specifically, we propose work in directions involving incorporating integration, heterogeneity, competition, uncertainty, and hybrid input models into classical problems. The proposal reports on preliminary successes and ongoing investigation in each of these directions, and formulates specific new problems and approaches. The intellectual merit of the proposal is to push the frontiers of approximation algorithms in terms of expanding its scope and applicability, as well as the potential for discovery of new underlying techniques.

The proposal is complemented with an educational and outreach plan that continues the PI's involvement in broader educational goals such as participation in surveys, tutorials and teaching workshops, as well as new course and lecture note development. The
broader impact of the proposal include graduate student training and placement in this research area as well as an extensive education plan aimed at increased dissemination of the PI's research to a broader audience including four-year college lecturers.

This project will develop a combination of novel computational methods to improve inferences of human genomic history from data on genetic variability between individuals. Large amounts of data have recently been gathered on the small genetic differences that distinguish one person from another. Such information is valuable for inferring how the genome has changed over the course of human history and for understanding the specific biological processes that have shaped it over time. These basic scientific results in turn have relevance to many practical problems in identifying the functions of genes, facilitating future genetic studies, and finding and mitigating risk factors for disease. Making optimal use of this information will, however, require new advances in mathematical models of how genetic variations are produced and in the computer algorithms needed to use those models to analyze real sequence data. The proposed work is based on a strategy to overcome limitations of the data and current computational capabilities by combining theoretical tools for haplotype structure identification, which finds segments of DNA that have been largely conserved over long periods of human history, with tools for phylogenetics, which infers how different individuals or populations are related to one another. Executing this strategy will involve a multidisciplinary effort, bringing together techniques from population genetics, computer science, mathematics, and operations research. In addition to its direct scientific outputs, the project will develop human resources by creating new course material and student research projects to help prepare future scientists to work at the intersection of these fields.

Networks underlie much of the progress in global connectivity and communications, and have enabled many of the advances in modern life. Network optimization studies networks in the abstract by formulating problems on the construction and usage of such networks. Many of the computational problems posed in this area are intractable motivating the design of heuristic approximation algorithms that run fast and deliver solutions that are provably near-optimal. The key thrust of the proposal is to design new and improved approximation algorithms for basic network problems incorporating side constraints and directionality of links building on some recent successes.

Fundamental problems in network optimization remain unresolved in their approximation guarantee achievable in polynomial time, particularly problems with side constraints (such as bi-criteria
network design problems) as well as those in directed graphs (such as the directed Steiner tree problem). This proposal addresses these shortcomings. A secondary thrust of this proposal is to formulate new network optimization problems drawing upon frameworks from Operations Research such as chance-constrained programming. The intellectual merit of the proposal include pushing the frontiers of approximation algorithms, and introducing new theoretical models for network optimization. The proposal will enable the continuation of the investigator's strong involvement in broader educational goals such as participation in invited talks, tutorials and teaching workshops, as well as new course and lecture note development. The broader impacts of the proposal include training and placement of very strong graduate students in the interdisciplinary areas of
algorithms, combinatorics and optimization.

The traveling salesperson problem (TSP) is a benchmark problem for combinatorial optimization that asks for a shortest tour that visits all the cities in a given network. The graph version where the distances arise from an underlying undirected graph captures a significant portion of the difficulty of designing good algorithms for solving this problem. This proposal will develop a consolidated understanding of the new techniques used in recent developments in the design of improved approximation algorithms for the graph-TSP problem and suggest new ones to move towards optimal performance guarantees. It will also examine carefully which of these will apply to the more general metric version of the problem, as well their relation to the well-known subtour elimination linear programming relaxation for the problem.

Designing better heuristic methods for solving prototypically hard optimization problems can improve our ability to solve larger real-scale instances arising in a variety of practical applications. This project will develop methods for improving the mathematically provable quality of the heuristic solutions for the fundamental traveling salesperson problem. New methods developed by the proposal will find applications to broader classes of problems in designing fault-tolerant minimum-distance networks, and also lead to new insights in graph theory and combinatorial optimization.

Fundamental problems in network design have served as benchmarks for the development of new techniques and evaluating their effectiveness in combinatorial optimization. This proposal will investigate a class of connectivity problems including the traveling salesperson problem and its closely related variants such as the bridge connectivity augmentation problem, two-edge-connected subgraph problem and vertex connectivity network design problems, in order to design improved approximation algorithms by advancing current techniques and developing new methods. The proposal also develops new theoretical models for network design problems from practice that incorporate sub-additive demands in information aggregation, and that integrate inventory storage and vehicle routing costs in logistics planning.

Due to the ubiquity of their applications, and the fundamental nature of their theory, network design problems are important both in practice and theory. New methods developed can be incorporated into practical heuristic approaches for solving prototypically hard optimization problems of real-life scale that arise in a host of applications from communications to logistics networks. The theoretical analysis developed will improve the mathematically provable quality of fast heuristic solutions for this important class of computational optimization problems.

The Principal Investigator (PI) formulates the information procuration problem of converting unstructured data into structured information as one of using limited resources (such as processing time and collection costs) among several available strategies for information acquisition, extraction, collation and aggregation in a sequential and adaptive manner. The proposal aims to build a Markov decision process (MDP) for which both the states and the rewards will be learned, and from which an optimal adaptive strategy for effective information procuration will be extracted.

Recent methods for designing adaptive strategies for multi-armed bandit problems and budgeted learning approaches by the PI will be extended for this purpose, as well as techniques from inverse reinforcement learning. Moreover, given the intended size of the application data sets, the focus will be on on scalable algorithms for these problems. Due to the centrality of the problem, new approaches to making better sense of unstructured data will have much impact both in terms of developing new methods and in practice. The proposed synthesis of methods from Operations Research, Approximation Algorithms and Machine Learning is novel in this context. This proposal will increase the cross-fertilization of ideas between Operations Research and Machine Learning, via a collaboration team formed at this intersection.

Optimization problems that often arise in practice can be cast as those of designing appropriate networks that connect specified locations. Many such network design problems such as the traveling salesperson problem are computationally hard to solve exactly; nevertheless, approximation algorithms that run quickly yet deliver near-optimal solutions have been devised for solving them, often using these problems as exemplars to develop new techniques. A large set of these techniques for designing approximation algorithms are based on applying the mathematical modeling formalism of linear programming to obtain a starting point, and using different ways to convert them to actual solutions that are cheap. This project will study some prototypical network design problems under the linear programming formalism to establish the limits of its accuracy. In the process, the project will attempt to discover new techniques for designing such approximation algorithms, adding to the existing toolkit. Methods from the project will be useful in designing new stand-alone solutions for many network design problems as well as enhancing current methods that employ the linear programming framework. The project will synthesize diverse ideas from algorithm design, optimization theory and combinatorial discrete mathematics, and will broaden participation by supporting two female doctoral students. The educational plan will disseminate the results to a broad audience in Computer Science, Mathematics, Operations Research and Business where the PI is a professor.

The set of problems examined in this project contains some of the long standing open problems in the theory of approximation algorithms, such as the symmetric traveling salesperson problem and its variants: the traveling salesperson path and two-edge-connected subgraph problems; it also includes other classical problems such as tree augmentation and prize-collecting Steiner forest that arise in a variety of network design applications. All these problems share the property that for their natural linear programming relaxations, the limits of these relaxations, also known as their integrality gaps, have not yet been established. The goal of the project is to design new approximation algorithms with performance ratios that match the exact integrality gap for these problems. These algorithms will be based on advancing current techniques such as primal-dual methods and iterated rounding, and developing new methods based on structural decompositions.

The project addresses a new set of problems that will increasingly
arise with a gradual shift to massively open online courses and
large classes where new assessments to test active learning of the
concepts are costly to design. The context of the project is a
prototype cloud-based quiz management system that leads the online
learners through scaffolded activities, such as creating,
answering, and improving of student-sourced quiz items. The system
then automatically evaluates the competence of learners and the
quality of questions from outcomes of these activities. This
project addresses the key algorithmic issue in such systems of
efficiently determining the quality of the students and the
submitted items. Preliminary ideas for new algorithms will be
developed and deployed in the test system to understand their
advantages and shortcomings. The development and testing of
algorithms will provide opportunities for training two graduate
students. This will also lead to a refinement of the eventual
algorithmic design of a system for scalable online assessments with
significant societal impacts.

In particular, the project develops new algorithmic frameworks for
problems in the joint ranking of students and student-sourced quiz
questions based on feedback in the form of peer performance and
review. A key contribution is the formulation of these problems in
terms of abstract problems amenable to both combinatorial and
continuous optimization, which in turn allows a completely
unrelated subfield of people (those of optimization) to work on
these problems in the future. At the same time, the project will
undertake the groundwork of developing the first such algorithms
that solve these problems with current approaches.