Limitations of Incremental Dynamic Programming

We consider so-called “incremental” dynamic programming algorithms, and are interested in the number of subproblems produced by them. The classical dynamic programming algorithm for the Knapsack problem is incremental, produces nK subproblems and nK ² relations (wires) between the subproblems, where n is the number of items, and K is the knapsack capacity. We show that any incremental algorithm for this problem must produce about nK subproblems, and that about nKlogK wires (relations between subproblems) are necessary. This holds even for the Subset-Sum problem. We also give upper and lower bounds on the number of subproblems needed to approximate the Knapsack problem. Finally, we show that the Maximum Bipartite Matching problem and the Traveling Salesman problem require exponential number of subproblems. The goal of this paper is to leverage ideas and results of boolean circuit complexity for proving lower bounds on dynamic programming.     

Assessment of post-Kyoto climate change mitigation regimes impact on sustainable development

This article analyzes post-Kyoto climate change mitigation regimes and their impact on sustainable development. Wide range of post-Kyoto climate change mitigation architectures have different impact on different groups of countries, therefore sustainability assessment is performed for four main group of countries: EU and other Annex-I countries, USA, Advanced Developing Countries and Least Developed Countries. The post-Kyoto climate change mitigation regimes are evaluated based on their economical, environmental, social and political impact for different groups of countries. For the assessment the scoring is applied. The architectures are further ranked according to the best results or highest score obtained during assessment according to all criteria and for all groups of countries.     

The Concept and RELAP5 Model of Thermal-Hydraulic System,Employing a Rapid Condensation for Coolant Circulation

The rapid condensation event is mostly considered a dangerous and undesirable side effect in thermal-hydraulic systems. This work demonstrates a different viewpoint, where condensation implosion is employed to perform mechanical work. Previous experimental study of the condensation implosion event, briefly presented in this article, showed that condensation implosion can be induced intentionally. These results were used as the basis for further investigations. In this work, a concept of the thermal-hydraulic system has been developed, where condensation-implosions-generated pressure difference could be used as a driving force. Numerical study has been performed to investigate the operation of the developed conceptual thermal-hydraulic system. A thermal-hydraulic computer code RELAP5 was selected for modeling the system operation. The RELAP5 code was found not able to predict the condensation implosion; therefore, a modified heat transfer model was implemented into the code. This modification allowed simulating the condensation implosion artificially in the thermal-hydraulic system and modeling the system response to the event. Final results show that a proposed circulation principle is possible and such a thermal-hydraulic system can operate.     

Conceptual Framework for Coordinated Great Lakes Monitoring

The utility of conceptual models is discussed as a basis for effective development of coordinated monitoring efforts on the Great Lakes. The use of conceptual models is illustrated in two ways: (1) the development of a methodology for specifying monitoring objectives of the Great Lakes, based on a conceptual model, and (2) presentation of a comprehensive method for defining resource needs to achieve monitoring objectives.     

Evaporation and condensing augmentation of water droplets in flue gas

The unsteady heat and mass transfer of sprayed water in the flue gas is modelled according to the iterative method of numerical research. The complex “droplet problem” covers the analysis of combined energy transfer in a semitransparent droplet, also combined heating and evaporation of the droplet. The surface temperature of the evaporating droplet is determined, at which the balance of energy fluxes taken to the surface and taken from the surface is reached. The thermal state mode of an evaporating droplet depends on the way of droplet heating as well. The change of thermal state and phase transformations parameters of water droplets warming in flue gas is analysed in the universal time scale. The initial evaluation of heat energy accumulated in exhaust flue gas utilization by water injection is presented.     

Min-rank conjecture for log-depth circuits

A completion of an m-by-n matrix A with entries in {0,1,?} is obtained by setting all ?-entries to constants 0 and 1. A system of semi-linear equations over GF₂ has the form Mx=f(x), where M is a completion of A and f:n{0,1}→m{0,1} is an operator, the ith coordinate of which can only depend on variables corresponding to ?-entries in the ith row of A. We conjecture that no such system can have more than ²n−?⋅mr(A) solutions, where ?>0 is an absolute constant and mr(A) is the smallest rank over GF₂ of a completion of A. The conjecture is related to an old problem of proving super-linear lower bounds on the size of log-depth boolean circuits computing linear operators x?Mx. The conjecture is also a generalization of a classical question about how much larger can non-linear codes be than linear ones. We prove some special cases of the conjecture and establish some structural properties of solution sets.