基于秘密共享模数的一般性多方求逆协议

Catalano、Gennaro和Halevi提出了一个实用的基于秘密共享模数的分布式求逆协议,然而他们仅仅考虑了门限敌手结构的情况.文中考虑了一般敌手结构的情况,针对半诚实敌手和恶意敌手,利用Damgard和Thorbek提出的线性整数秘密共享方案,分别构造了一个多方模求逆协议.该协议在敌手结构是Q2(对应Q3以及强RSA假设)的条件下针对半诚实(对应恶意)敌手是安全的.该协议是Catalano等人方案的一个推广,可以用来分布式地计算RSA私钥以及构造标准模型下安全的分布式Gennaro-Halevi-Rabin、Cramer-Shoup和Mames-Joye签名方案.另外,文中的构造方法也是对环上的安全多方协议构造方法的一个有力补充.     

The distributed permutation flowshop scheduling problem

This paper studies a new generalization of the regular permutation flowshop scheduling problem (PFSP) referred to as the distributed permutation flowshop scheduling problem or DPFSP. Under this generalization, we assume that there are a total of F identical factories or shops, each one with m machines disposed in series. A set of n available jobs have to be distributed among the F factories and then a processing sequence has to be derived for the jobs assigned to each factory. The optimization criterion is the minimization of the maximum completion time or makespan among the factories. This production setting is necessary in today's decentralized and globalized economy where several production centers might be available for a firm. We characterize the DPFSP and propose six different alternative mixed integer linear programming (MILP) models that are carefully and statistically analyzed for performance. We also propose two simple factory assignment rules together with 14 heuristics based on dispatching rules, effective constructive heuristics and variable neighborhood descent methods. A comprehensive computational and statistical analysis is conducted in order to analyze the performance of the proposed methods.     

Min-degree constrained minimum spanning tree problem: New formulation via Miller–Tucker–Zemlin constraints

Given an undirected network with positive edge costs and a positive integer $d>2$, the minimum-degree constrained minimum spanning tree problem is the problem of finding a spanning tree with minimum total cost such that each non-leaf node in the tree has a degree of at least $d$. This problem is new to the literature while the related problem with upper bound constraints on degrees is well studied. Mixed-integer programs proposed for either type of problem is composed, in general, of a tree-defining part and a degree-enforcing part. In our formulation of the minimum-degree constrained minimum spanning tree problem, the tree-defining part is based on the Miller–Tucker–Zemlin constraints while the only earlier paper available in the literature on this problem uses single and multi-commodity flow-based formulations that are well studied for the case of upper degree constraints. We propose a new set of constraints for the degree-enforcing part that lead to significantly better solution times than earlier approaches when used in conjunction with Miller–Tucker–Zemlin constraints.     

The generalized assortment and best cutting stock length problems

This paper introduces two new one-dimensional cutting stock models: the generalized assortment problem (GAP) and the best cutting stock length (BSL) problem. These new models provide the potential to reduce waste to values lower than the optimum of current models, under the right management circumstances. In the GAP, management has a standard length and can select one or more of any additional custom stock lengths, and management wishes to minimize cutting stock waste. This model is different from existing models that assume that the selection is from a small fixed set of stock lengths. In the BSL problem, management chooses any number of custom stock lengths, but wishes to find the fewest custom stock lengths in order to have zero waste. Results show waste reductions of 80% with just one custom stock length compared with solutions from standard cutting stock formulations, when item lengths are long relative to the stock length. The models are most effective when the item lengths are nearly as long as the stock length. Solutions from the model have been implemented for a manufacturer. The model is easily generalized to allow multiple existing stock lengths and different costs.     

An enumeration algorithm for integer‐valued data envelopment analysis

Data envelopment analysis (DEA) models assume real‐valued inputs and outputs, but on many occasions, some inputs and/or outputs can only take integer values. In these cases, using DEA models can result in misleading efficiency assessments and inaccurate performance targets. In this paper, we propose an enumeration algorithm for computing efficiency scores and performance targets of decision‐making units with integer value inputs/outputs. In the presented algorithm, we do not use any of the mixed integer linear programming (MILP) models that are used in previous studies. We show that the result of our algorithm and that of the MILP model presented in this context is the same. We also generalize our algorithm for different types of returns to scale as well as for the hybrid setting with real‐valued data.     

一种AVS-M整数像素运动估计快速算法

根据AVS-M编码过程中运动估计的特点,在整数像素运动矢量搜索过程中,提出一种基于起点预测和早停止的自适应运动估计快速搜索算法.与MVFAST算法相比,大大减少了搜索点数,加速了搜索过程,平均速度提高了39.9%~45.7%,减少了整数像素运动估计的计算量,在保持较低的编码码率和较好的图像质量的同时,提高了编码速度.     

一种AVS-M运动搜索快速算法

针对AVS-M运动搜索算法的复杂性,根据其变换量化的特点,推导全零块判决准则,提出一种基于全零块检测的AVS-M运动搜索快速算法,在运动搜索的同时判决出全零块,从而节省运动搜索和变换量化的时间。实验数据显示,该算法节省的计算量最多可达77.4%,且比特率下降程度大于峰值信噪比下降程度。结果表明,在不降低编码性能的情况下,该算法能有效提高运动估计的编码速度。     

Selection of a dynamic supply portfolio in make-to-order environment withrisks

The problem of a multi-period supplier selection and order allocation in make-to-order environment in the presence of supply chain disruption and delay risks is considered. Given a set of customer orders for finished products, the decision maker needs to decide from which supplier and when to purchase product-specific parts required for each customer order to meet customer requested due date at a low cost and to mitigate the impact of supply chain risks. The selection of suppliers and the allocation of orders over time is based on price and quality of purchased parts and reliability of supplies. For selection of dynamic supply portfolio a mixed integer programming approach is proposed to incorporate risk that uses conditional value-at-risk via scenario analysis. In the scenario analysis, the low-probability and high-impact supply disruptions are combined with the high probability and low impact supply delays. The proposed approach is capable of optimizing the dynamic supply portfolio by calculating value-at-risk of cost per part and minimizing expected worst-case cost per part simultaneously. Numerical examples are presented and some computational results are reported.     

A computational study of parametric tabu search for 0–1 mixed integer programs

We present a computational study of parametric tabu search for solving 0–1 mixed integer programming (MIP) problems, a generic heuristic for general MIP problems proposed by Glover [Glover F. Parametric tabu-search for mixed integer programs. Computers and Operations Research 2006; 33: 2449–94.]. This approach solves a series of linear programming problems by incorporating branching inequalities as weighted terms in the objective function. New strategies are proposed for uncovering feasible and high-quality solutions and extensive computational tests are performed on instances from the literature.     

A heuristic approach for packing identical rectangles in convex regions

In this paper we propose a heuristic approach for the problem of packing equal rectangles within a convex region. The approach is based on an Iterated Local Search scheme, in which the key step is the perturbation move. Different perturbation moves, both combinatorial and continuous ones, are proposed and compared through extensive computational experiments on a set of test instances. The overall results are quite encouraging.