Optimality guarantees for crystal structure prediction.

Crystalline materials enable essential technologies, and their properties are determined by their structures. Crystal structure prediction can thus play a central part in the design of new functional materials1,2. Researchers have developed efficient heuristics to identify structural minima on the potential energy surface3-5. Although these methods can often access all configurations in principle, there is no guarantee that the lowest energy structure has been found. Here we show that the structure of a crystalline material can be predicted with energy guarantees by an algorithm that finds all the unknown atomic positions within a unit cell by combining combinatorial and continuous optimization. We encode the combinatorial task of finding the lowest energy periodic allocation of all atoms on a lattice as a mathematical optimization problem of integer programming6,7, enabling guaranteed identification of the global optimum using well-developed algorithms. A single subsequent local minimization of the resulting atom allocations then reaches the correct structures of key inorganic materials directly, proving their energetic optimality under clear assumptions. This formulation of crystal structure prediction establishes a connection to the theory of algorithms and provides the absolute energetic status of observed or predicted materials. It provides the ground truth for heuristic or data-driven structure prediction methods and is uniquely suitable for quantum annealers8-10, opening a path to overcome the combinatorial explosion of atomic configurations.

Network Pollution Games.

The problem of pollution control has been mainly studied in the environmental economics literature where the methodology of game theory is applied for the pollution control. To the best of our knowledge this is the first time this problem is studied from the computational point of view. We introduce a new network model for pollution control and present two applications of this model. On a high level, our model comprises a graph whose nodes represent the agents, which can be thought of as the sources of pollution in the network. The edges between agents represent the effect of spread of pollution. The government who is the regulator, is responsible for the maximization of the social welfare and sets bounds on the levels of emitted pollution in both local areas as well as globally in the whole network. We first prove that the above optimization problem is NP-hard even on some special cases of graphs such as trees. We then turn our attention on the classes of trees and planar graphs which model realistic scenarios of the emitted pollution in water and air, respectively. We derive approximation algorithms for these two kinds of networks and provide deterministic truthful and truthful in expectation mechanisms. In some settings of the problem that we study, we achieve the best possible approximation results under standard complexity theoretic assumptions. Our approximation algorithm on planar graphs is obtained by a novel decomposition technique to deal with constraints on vertices. We note that no known planar decomposition techniques can be used here and our technique can be of independent interest. For trees we design a two level dynamic programming approach to obtain an FPTAS. This approach is crucial to deal with the global pollution quota constraint. It uses a special multiple choice, multi-dimensional knapsack problem where coefficients of all constraints except one are bounded by a polynomial of the input size. We furthermore derive truthful in expectation mechanisms on general networks with bounded degree.