Interpolation by a Game

We introduce a notion of a real game (a generalisation of the Karchmer-Wigderson game (cf. [3]) and of real communication complexity, and relate this complexity to the size of monotone real formulas and circuits. We give an exponential lower bound for tree-like monotone protocols (defined in [4, Definition 2.2]) of small real communication complexity solving the monotone communication complexity problem associated with the bipartite perfect matching problem. This work is motivated by a research in interpolation theorems for prepositional logic (by a problem posed in [5, Section 8], in particular). Our main objective is to extend the communication complexity approach of [4, 5] to a wider class of proof systems. In this direction we obtain an effective interpolation in a form of a protocol of small real communication complexity. Together with the above mentioned lower bound for tree-like protocols this yields as a corollary a lower bound on the number of steps for particular semantic derivations of Hall's theorem (these include tree-like cutting planes proofs for which an exponential lower bound was demonstrated in [2]).     

Transparent Long Proofs: A First PCP Theorem for NPR

We introduce and study the notion of probabilistically checkable proofs (PCP) for real number algorithms. Our starting point is the computational model of Blum, Shub, and Smale (BSS) and the real analogue NP_R of NP in that model. We define in a straightforward manner verifiers as well as complexity classes PCP_R(r(n),q(n)) for the BSS model. Our main result is, to the best of our knowledge, the first PCP theorem for NP_R. It states that each problem in NP_R has transparent long proofs, i.e.,NP_R \subseteq PCP_R(poly,1), where poly denotes the class of univariate polynomial functions. The techniques used extend ideas from [12] for self-testing and self-correcting certain functions over so-called rational domains to more general domains over the real numbers. The latter arise from the particular NP_R-complete problem for which we construct a verifier of the required form.     

Wang’s B machines are efficiently universal,as is Hasenjaeger’s small universal electromechanical toy

In the 1960s Gisbert Hasenjaeger built Turing Machines from electromechanical relays and uniselectors. Recently, Glaschick reverse engineered the program of one of these machines and found that it is a universal Turing machine. In fact, its program uses only four states and two symbols, making it a very small universal Turing machine. (The machine has three tapes and a number of other features that are important to keep in mind when comparing it to other small universal machines.) Hasenjaeger’s machine simulates Hao Wang’s B machines, which were proved universal by Wang. Unfortunately, Wang’s original simulation algorithm suffers from an exponential slowdown when simulating Turing machines. Hence, via this simulation, Hasenjaeger’s machine also has an exponential slowdown when simulating Turing machines. In this work, we give a new efficient simulation algorithm for Wang’s B machines by showing that they simulate Turing machines with only a polynomial slowdown. As a second result, we find that Hasenjaeger’s machine also efficiently simulates Turing machines in polynomial time. Thus, Hasenjaeger’s machine is both small and fast. In another application of our result, we show that Hooper’s small universal Turing machine simulates Turing machines in polynomial time, an exponential improvement.     

Scheduling parallel machines with inclusive processing set restrictions and job release times

We consider the problem of scheduling a set of jobs with different release times on parallel machines so as to minimize the makespan of the schedule. The machines have the same processing speed, but each job is compatible with only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. We present an efficient algorithm for this problem with a worst-case performance ratio of 2. We also develop a polynomial time approximation scheme (PTAS) for the problem, as well as a fully polynomial time approximation scheme (FPTAS) for the case in which the number of machines is fixed.     

Analytical properties of resource-bounded real functionals

Computable analysis is an extension of classical discrete computability by enhancing the normal Turing machine model. It investigates mathematical analysis from the computability perspective. Though it is well developed on the computability level, it is still under developed on the complexity perspective, that is, when bounding the available computational resources. Recently Kawamura and Cook developed a framework to define the computational complexity of operators arising in analysis. Our goal is to understand the effects of complexity restrictions on the analytical properties of the operator. We focus on the case of norms over C[0, 1] and introduce the notion of dependence of a norm on a point and relate it to the query complexity of the norm. We show that the dependence of almost every point is of the order of the query complexity of the norm. A norm with small complexity depends on a few points but, as compensation, highly depends on them. We briefly show how to obtain similar results for non-deterministic time complexity. We characterize the functionals that are computable using one oracle call only and discuss the uniformity of that characterization.     

Solving multi-objective production scheduling problems using metaheuristics

Most of research in production scheduling is concerned with the optimization of a single criterion. However the analysis of the performance of a schedule often involves more than one aspect and therefore requires a multi-objective treatment. In this paper we first present (Section 1) the general context of multi-objective production scheduling, analyze briefly the different possible approaches and define the aim of this study i.e. to design a general method able to approximate the set of all the efficient schedules for a large set of scheduling models. Then we introduce (Section 2) the models we want to treat––one machine, parallel machines and permutation flow shops––and the corresponding notations. The method used––called multi-objective simulated annealing––is described in Section 3. Section 4 is devoted to extensive numerical experiments and their analysis. Conclusions and further directions of research are discussed in the last section.     

Feasible Real Random Access Machines

We present a modified real RAM model which is equipped with the usual discrete and real-valued arithmetic operations and with a finite precision test <_kwhich allows comparisons of real numbers only up to a variable uncertainty 1/(k+1). Furthermore, ourfeasible RAMhas an extended semantics which allows approximative computations. Using a logarithmic complexity measure we prove that all functions computable on a RAM in time (t) can be computed on a Turing machine in time (t²·log(t)·log log(t)). Vice versa all functions computable on a Turing machine in time (t) are computable on a RAM in time (t). Thus, our real RAM model does not only express exactly the computational power of Turing machines on real numbers (in the sense of Grzegorczyk), but it also yields a high-level tool for realistic time complexity estimations on real numbers.     

投资项目的期权评价与最优投资规则

本文介绍了不确定环境下的投资项目的期权评价方法和最优投资规则，研究了单期项目和连续投资项目的投资决策问题，探讨了实物期权评价方法与传统的净现值评价方法中最优投资规则的差异，并对影响最优投资规则的差异因素进行了敏感性分析，得出了直观而有实用价值的结论。     

Parallel machine scheduling problems with a single server

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.     

Multi-stage IT project evaluation: The flexibility value obtained by implementing and resolving Berk, Green and Naik (2004) model

In this paper, we evaluate a multi-stage information technology investment project, by implementing and resolving Berk, Green and Naik’s (2004) model, which takes into account specific features of IT projects and considers the real option to suspend investment at each stage. We present a particular case of the model where the project value is the solution of an optimal control problem with a single state variable. In this case, the model is more intuitive and tractable. The case study confirms the practical potential of the model and highlights the importance of the real-option approach compared to classical discounted cash flow techniques in the valuation of IT projects.     

Subagging for credit scoring models

The logistic regression framework has been for long time the most used statistical method when assessing customer credit risk. Recently, a more pragmatic approach has been adopted, where the first issue is credit risk prediction, instead of explanation. In this context, several classification techniques have been shown to perform well on credit scoring, such as support vector machines among others. While the investigation of better classifiers is an important research topic, the specific methodology chosen in real world applications has to deal with the challenges arising from the real world data collected in the industry. Such data are often highly unbalanced, part of the information can be missing and some common hypotheses, such as the i.i.d. one, can be violated. In this paper we present a case study based on a sample of IBM Italian customers, which presents all the challenges mentioned above. The main objective is to build and validate robust models, able to handle missing information, class unbalancedness and non-iid data points. We define a missing data imputation method and propose the use of an ensemble classification technique, subagging, particularly suitable for highly unbalanced data, such as credit scoring data. Both the imputation and subagging steps are embedded in a customized cross-validation loop, which handles dependencies between different credit requests. The methodology has been applied using several classifiers (kernel support vector machines, nearest neighbors, decision trees, Adaboost) and their subagged versions. The use of subagging improves the performance of the base classifier and we will show that subagging decision trees achieve better performance, still keeping the model simple and reasonably interpretable.     

On centain decompositions of Gödel numberings

Summary We define certain decompositions of the functions that describe Gödel numberings of the partial recursive functions (Section 2). These decompositions reflect the way in which concrete Gödel numberings may be obtained from the known computability formalisms. We show that such decompositions exist for all partial recursive functions (Section 3). It turns out that there is an intimate connection between these decompositions and Blum's step counting functions which yields a suggestive interpretation of Blum's notion (Section 4). In terms of these decompositions we, finally, give an exact formulation for a basic problem in the theory of computability formalisms, which, on an intuitive level, would read as follows: Find conditions on the expressive power of one step in a given computability formalism such that all partial recursive functions can be represented within that formalism. We derive two theorems which may be regarded as a first step in a thorough study of this problem.     

Scheduling incompatible tasks on two machines

The paper studies the problem of scheduling tasks on two machines to minimize the makespan. The tasks are assigned to the machine in advance. An incompatibility relation is defined over the tasks which forbids any two incompatible tasks to be processed at the same time. The problem can serve as a mathematical model for some batching problems in which the jobs are grouped in pairs on two machines. A linear-time algorithm is presented.     

On NP-Completeness for Linear Machines

We consider linear and scalar versions of the Blum–Shub–Smale model of computation over the reals. The permitted computing operations of linear machines are addition and multiplication by constants. The scalar machines can only multiply by constants. The size of an input is its dimension, and the cost of any instruction is one. For each of these structures we consider DNP and NP, the corresponding complexity classes with respect to digital nondeterminism and standard real nondeterminism, respectively. We give DNP- and NP-complete problems for linear and real scalar machines. On the other hand, we show that the NP-class restricted to scalar machines over the integers with equality-tests does not own a complete problem.     

极小化完工时间和的有界批调度问题

考虑m台并行批加工同型机上n个带有释放时间的工件的调度问题,目标是极小化完工时间和.给出了一个多项时间近似方案.     

Real Computational Universality: The Word Problem for a Class of Groups with Infinite Presentation

The word problem for discrete groups is well known to be undecidable by a Turing Machine; more precisely, it is reducible both to and from and thus equivalent to the discrete Halting Problem. The present work introduces and studies a real extension of the word problem for a certain class of groups which are presented as quotient groups of a free group and a normal subgroup. As a main difference to discrete groups these groups may be generated by uncountably many generators with index running over certain sets of real numbers. We study the word problem for such groups within the Blum–Shub–Smale (BSS) model of real number computation. The main result establishes the word problem to be computationally equivalent to the Halting Problem for such machines. It thus gives the first non-trivial example of a problem complete, that is, computationally universal for this model. M. Ziegler supported by (project Zi1009/1-2).     

Invariant domains of holomorphy: Twenty years later

This review is devoted to the domains of holomorphy invariant under holomorphic actions of real Lie groups. We have collected here the results on this subject obtained during the last twenty years, which have passed since the publication of the first review of the authors on this topic. This first review was mainly devoted to the case of compact transformation groups, while the first two sections of the present review deal mostly with noncompact groups. In Section 3 we discuss the problem of rigidity of automorphism groups of domains of holomorphy invariant under compact transformation groups.     

Real time disruption management for a two-stage batch production–inventory system with reliability considerations

In this research, a two-stage batch production–inventory system is introduced. In this system, the production may be disrupted, for a given period of time, either at one or both stages. In this paper, firstly, a mathematical model has been developed to suggest a recovery plan for a single occurrence of disruption at either stage. Secondly, multiple disruptions have been considered, for which a new disruption may or may not affect the recovery plan of earlier disruptions. We propose a new approach that deals with a series of disruptions over a period of time, which can be implemented for disruption recovery on a real time basis. In this approach, the model formulated for single disruption has been integrated to generate initial solutions for individual disruptions and the solutions have been revised for multiple dependent disruptions with changed parameters. With the proposed approach, an optimal recovery plan can be obtained in real time, whenever the production system experiences either a sudden disruption or a series of disruptions, at different points in time. Some numerical examples and a real-world case study are presented to explain the benefits of our proposed approach.     

An algebraic geometry algorithm for scheduling in presence of setups and correlated demands

We study here a problem of schedulingn job types onm parallel machines, when setups are required and the demands for the products are correlated random variables. We model this problem as a chance constrained integer program.Methods of solution currently available—in integer programming and stochastic programming—are not sufficient to solve this model exactly. We develop and introduce here a new approach, based on a geometric interpretation of some recent results in Gröbner basis theory, to provide a solution method applicable to a general class of chance constrained integer programming problems.Out algorithm is conceptually simple and easy to implement. Starting from a (possibly) infeasible solution, we move from one lattice point to another in a monotone manner regularly querying a membership oracle for feasibility until the optimal solution is found. We illustrate this methodology by solving a problem based on a real system.Corresponding author.     

Tropical differential equations

Tropical differential equations are introduced and an algorithm is designed which tests solvability of a system of tropical linear differential equations within the complexity polynomial in the size of the system and in the absolute values of its coefficients. Moreover, we show that there exists a minimal solution, and the algorithm constructs it (in case of solvability). This extends a similar complexity bound established for tropical linear systems. In case of tropical linear differential systems in one variable a polynomial complexity algorithm for testing its solvability is designed.We prove also that the problem of solvability of a system of tropical non-linear differential equations in one variable is NP-hard, and this problem for arbitrary number of variables belongs to NP. Similar to tropical algebraic equations, a tropical differential equation expresses the (necessary) condition on the dominant term in the issue of solvability of a differential equation in power series.