二供应商经济批量问题的多项式时间算法

为了从采购费用结构不同的供应商中找到最佳补货策略,考虑一个零售商从两个供应商补货的二供应商经济批量问题.零售商在两个供应商处的采购费用结构分别为复合安装费用和全单位数量折扣费用结构.通过对问题结构性质的分析论证,将问题的可行解转化为一个有向网络,降低问题求解的计算复杂性.综合动态规划和Dijkstra最短路算法证明了该问题是多项式时间可解的.     

工件可拒绝排序问题综述

可拒绝排序问题是兴起于2000年前后的有代表性、应用背景极强的的排序问题,是经典排序问题的衍生和推广.经典排序问题总是要求每个工件必须被加工,然而在实际中由于某些特殊原因,决策者会选择拒绝加工某些工件.把允许工件被拒绝的这类问题称为工件可拒绝排序问题,有的文献称之为外包的排序问题.这些问题不仅具有很强的应用价值,在理论上也有重要的意义.近年来该领域受到越来越广泛的关注,新的研究成果不断涌现.现就离线、在线情况下的可拒绝排序问题的进展情况作了全面介绍,展示了已有的研究成果和新的问题,给出了此方面的比较重要的参考文献,旨在帮助感兴趣的读者迅速了解问题研究的进展并由此进入此研究领域的前沿.     

Modeling complexity in musical rhythm

This article constructs a tree structure for the music rhythm using the L‐system. It models the structure as an automata and derives its complexity. It also solves the complexity for the L‐system. This complexity can resolve the similarity between trees. This complexity serves as a measure of psychological complexity for rhythms. It resolves the music complexity of various compositions including the Mozart effect K488. © 2009 Wiley Periodicals, Inc. Complexity, 2010     

Complexity of two coloring problems in cubic planar bipartite mixed graphs

In this note we consider two coloring problems in mixed graphs, i.e., graphs containing edges and arcs, which arise from scheduling problems where disjunctive and precedence constraints have to be taken into account. We show that they are both NP-complete in cubic planar bipartite mixed graphs, which strengthens some results of Ries and de Werra (2008) [9].     

How ∗ not ∗ to solve a Sudoku

We prove the NP-hardness of a consistency checking problem that arises in certain elimination strategies for solving Sudoku-type problems.     

The Stock Market Model with Delayed Information Impact from a Socioeconomic View

Finding the critical factor and possible “Newton’s laws” in financial markets has been an important issue. However, with the development of information and communication technologies, financial models are becoming more realistic but complex, contradicting the objective law “Greatest truths are the simplest.” Therefore, this paper presents an evolutionary model independent of micro features and attempts to discover the most critical factor. In the model, information is the only critical factor, and stock price is the emergence of collective behavior. The statistical properties of the model are significantly similar to the real market. It also explains the correlations of stocks within an industry, which provides a new idea for studying critical factors and core structures in the financial markets.     

The projected newton method for solving inverse eigenvalue problems - the case of multiple eigenvaues

This paper deals with the optimal solution of ill-posed linear problems, i.e..linear problems for which the solution operator is unbounded. We consider worst-case ar,and averagecase settings. Our main result is that algorithms having finite error (for a given setting) exist if and only if the solution operator is bounded (in that setting). In the worst-case setting, this means that there is no algorithm for solving ill-posed problems having finite error. In the average-case setting, this means that algorithms having finite error exist if and only lf the solution operator is bounded on the average. If the solution operator is bounded on the average, we find average-case optimal information of cardinality n and optimal algorithms using this information, and show that the average error of these algorithms tends to zero as n→∞. These results are then used to determine the [euro]-complexity, i.e., the minimal costof finding an [euro]-accurate approximation. In the worst-case setting, the [euro]comp1exity of an illposed problem is infinite for all [euro]>0; that is, we cannot find an approximation having finite error and finite cost. In the average-case setting, the [euro]-complexity of an ill-posed problem is infinite for all [euro]>0 iff the solution operator is not bounded on the average, moreover, if the the solutionoperator is bounded on the average, then the [euro]-complexity is finite for all [euro]>0.     

Confidence Bands for Isotonic Median Curves Using Sign Tests

Suppose that one observes independent random variables (X₁, Y₁), (X₂, Y₂), …, (X_n, Y_n) in R² with unknown distributions, except that Median(Y_i | X_i = M(x) for some unknown isotonic function M. We describe an explicit algorithm for the computation of confidence bands for the median function M whose running time is of order O(n²). The bands rely on multiscale sign tests and are shown to have desirable asymptotic properties.