MDP-Based Budget Allocation for Efficient Cooperative Task Solving

In order to facilitate crowdsourcing-based task solving,complex tasks are decomposed into interdependent subtasks that can be executed cooperatively by individual workers.Aiming to maximize the quality of the final solution subject to the self-interested worker's utility maximization,a key challenge is to allocate the limited budget among the subtasks as the rewards for workers having various levels of abilities.This study is the first attempt to show the value of Markov decision processes (MDPs) for the problem of optimizing the quality of the final solution by dynamically determining the budget allocation on sequentially dependent subtasks under the budget constraints and the uncertainty of the workers' abilities.Our simulation-based approach verifies that compared to some offiine methods where workers' abilities are fully known,our proposed MDP-based payment planning is more efficient at optimizing the final quality under the same limited budget.     

Consolidation of Subtasks for Target Task in Pipelined NLP Model

Most natural language processing tasks depend on the outputs of some other tasks. Thus, they involve other tasks as subtasks. The main problem of this type of pipelined model is that the optimality of the subtasks that are trained with their own data is not guaranteed in the final target task, since the subtasks are not optimized with respect to the target task. As a solution to this problem, this paper proposes a consolidation of subtasks for a target task (CST²). In CST², all parameters of a target task and its subtasks are optimized to fulfill the objective of the target task. CST² finds such optimized parameters through a backpropagation algorithm. In experiments in which text chunking is a target task and part‐of‐speech tagging is its subtask, CST² outperforms a traditional pipelined text chunker. The experimental results prove the effectiveness of optimizing subtasks with respect to the target task.     

Adaptive Methods for Linear Programming Decoding

Detectability of failures of linear programming (LP) decoding and the potential for improvement by adding new constraints motivate the use of an adaptive approach in selecting the constraints for the underlying LP problem. In this paper, we make a first step in studying this method, and show that by starting from a simple LP problem and adaptively adding the necessary constraints, the complexity of LP decoding can be significantly reduced. In particular, we observe that with adaptive LP decoding, the sizes of the LP problems that need to be solved become practically independent of the density of the parity-check matrix. We further show that adaptively adding extra constraints, such as constraints based on redundant parity checks, can provide large gains in the performance.      

Reliability and Performance of Star Topology Grid Service With Precedence Constraints on Subtask Execution

The paper considers grid computing systems with star architectures in which the resource management system (RMS) divides service tasks into subtasks, and sends the subtasks to different specialized resources for execution. To provide the desired level of service reliability, the RMS can assign the same subtasks to several independent resources for parallel execution. Some subtasks cannot be executed until they have received input data, which can be the result of other subtasks. This imposes precedence constraints on the order of subtask execution. The service reliability & performance indices are introduced, and a fast numerical algorithm for their evaluation given any subtask distribution is suggested. Illustrative examples are presented.     

Comparison of ILP formulations for the RWA problem

We present a review of the integer linear programming (ILP) formulations that have been proposed for the routing and wavelength assignment problem in WDM optical networks assuming asymmetrical traffic. We show that all formulations proposed under asymmetrical traffic assumptions, both link and path formulations, are equivalent in terms of the upper bound value provided by the optimal solution of their linear programming relaxation, although their number of variables and constraints widely differ. We propose improvements for some of the formulations that result in further reductions in the number of variables and constraints.Under the objective of minimizing the blocking rate, we propose an experimental comparison of the best lower and upper bounds that are available. We then discuss the easiness of exact ILP solution depending on the formulations. We observe that LP relaxation bounds often provide solutions with a value very close to the optimal ILP one. We solve exactly for the first time several RWA (Routing and Wavelength Assignment) realistic instances, including those proposed by Krishnaswamy and Sivarajan [R. Krishnaswamy, K. Sivarajan, Algorithms for routing and wavelength assignment based on solutions of LP-relaxation, IEEE Communications Letters 5 (10) (2001) 435–437], with a proof of the optimality.     

On the LP which finds a MMAE stack filter

Two methods are proposed to modify the linear program (LP) developed by E.J. Coyle and J.-H. Lin (1988) to find a stack filter which minimizes the mean absolute error (MAE). In the first approach, the number of constraints is substantially reduced at the expense of requiring a zero-one LP to solve for an optimal filter. This scheme reduces the number of constraints from O(n2ⁿ) to O(28ⁿ), which is exactly the cardinality of the set of possible binary vectors which can appear in the window of the filter. In the second approach, the LP is transformed into a max-flow problem. This guarantees that the problem can be solved in time which is a polynomial function of the number of variables in the LP, as opposed to the worst-case exponential time that may occur with the simplex method. It also allows the many fast algorithms for the max-flow problem to be used to find an optimal stack filter. Recursive algorithms for construction of the window width n constraint matrix for both the original LP and the max-flow modification are also provided     

The high-level synthesis of digital systems

High-level synthesis systems start with an abstract behavioral specification of a digital system and find a register-transfer level structure that realizes the given behavior. The various tasks involved in developing a register-transfer level structure from an algorithmic level specification are described. In particular, it is shown how the high-level synthesis task can be decomposed into a number of distinct but not independent subtasks. The techniques that have been developed for solving those subtasks are presented. Areas related to high-level synthesis that are still open problems are examined     

RTDT: A static QoS manager, RT scheduling, HW/SW partitioning CAD tool

The hardware/software partitioning/scheduling relies on two subtasks: the cost function and the real time (RT) analysis. Besides these two subtasks, the proposed generic framework, also called RT design trotter (RTDT), processes the problem of the Quality of Service (QoS) management. The aim is to add a new dimensions to solution selection, namely the guarantee of QoS from both application quality and RT issue points of view. The proposed framework defines an iteration loop of three steps that solve the sub-problems. The cost function takes into account the system on chip (SoC) area and the static and dynamic power dissipation. We show how our tool can be used to rapidly evaluate the impact of the application quality and the RT constraints choices (QoS parameters) over the final cost.     

Computing lower bounds on functional units before scheduling

The authors present a new polynomial-time algorithm for computing lower bounds on the number of functional units (FUs) of each type required to schedule a data flow graph in a specified number of control steps. A formal approach is presented that is guaranteed to find the tightest possible bounds that can be found by relaxing either the precedence constraints or integrality constraints on the scheduling problem. This tight, yet fairly efficient, bounding method can be used to estimate FU area, to generate resource constraints for reducing the search space, or in conjunction with exact techniques for efficient optimal design space exploration     

Constraint transformation for IC physical design

In a top-down design methodology, design tasks are divided into simpler subtasks across levels of a hierarchy as an effective divide-and-conquer technique. For every task, tolerances are defined on all performance characteristics to take into account parasitics, mismatches, and other nondeterministic process parameter variations. Constraint transformation is a process used to translate performance specifications into subtask requirements. This paper introduces the problem of constraint transformation and describes some formal solutions for analog circuit applications. Examples illustrate the methodology and show the suitability of this approach in industrial-strength applications     

MAP estimation via agreement on trees: message-passing and linear programming

We develop and analyze methods for computing provably optimal maximum a posteriori probability (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is tight if and only if all the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: a) a tree-relaxed linear program (LP), which is derived from the Lagrangian dual of the upper bounds; and b) a tree-reweighted max-product message-passing algorithm that is related to but distinct from the max-product algorithm. In this way, we establish a connection between a certain LP relaxation of the mode-finding problem and a reweighted form of the max-product (min-sum) message-passing algorithm.     

协作制造环境下子任务调度的优化方法

协作制造模式为分布式生产设备的高效利用提供了共享合作平台,如何将生产任务高效调度到各设备中是一个复杂的优化问题.基于对任务结构和过程的分析提出子任务调度模型,使不同位置和功能的设备能协作处理一批任务.基于对生产代价和时延的建模,采用遗传算法实现3种优化调度策略,优化目标分别为设备负载均衡、最小化总生产时延和最小化总生产开销.仿真结果表明这3种策略能分别实现对应的优化目标.     

Quantization on the Grassmann Manifold

The problem of quantization in an Euclidean space with unitary constraints can be formulated as an unconstrained problem on a Grassmann manifold. Such constraints arise in areas such as wireless communication with multiple antennas at the transmitter and at the receiver. Due to the constraints, the distortion rate analysis developed for Euclidean spaces cannot be applied directly. This paper extends Gersho's asymptotic (large rate, small distortion) distortion bounds to the case when the source is distributed on the complex Grassmann manifold. The special structure of the Grassmann manifold and the distortion measures defined on it differentiate this problem from the traditional vector quantization in Euclidean spaces.     

Bounds from noisy linear measurements

An estimation problem in which a finite number of linear measurements of an unknown function is available, and in which the only prior information available concerning the unknown function consists of inequality constraints on its magnitude, is ill-posed in that insufficient information is available from which point estimates of the unknown function can be made with any reliability, even with exact measurements. An alternative to point estimation involves the computation of bounds on linear functionals of the unknown function in terms of the measurements. A generalization is described of the bounding technique to problems in which the measurements are inexact. The bounds are defined in terms of a primal optimization problem. A deterministic interpretation of the bounds is given, as well as a probabilistic one for the case of additive Gaussian measurement noise. An unconstrained dual optimization problem is derived that has an interesting data-adaptive filtering interpretation and provides an attractive basis for computation. Several aspects of the primal and dual optimization problems are investigated that have important implications for the reliable computation of the bounds.     

Capacity reservation optimization for distributed satellite cluster networks

We investigate the problem of link capacity reservation in distributed satellite cluster networks. In the optimization problem, the objective is to minimize the link reservation cost under the link capacity constraints. The original optimization problem can be formulated as a set of the linear programs. For the small‐scale networks, the general linear program solvers have the capability to solve the problem within an acceptable time. To solve the problem in the large‐scale network, we propose a heuristic method on the basis of the alternating direction method of multipliers, in which the original problem is decoupled to parallel small problems that can be solved simply. In the heuristic, the upper and lower bounds are computed iteratively. When the upper and lower bounds are close enough, then the optimal value can be obtained approximately. The simulation results show that the proposed method is comparatively exact when the stopping criterion is properly chosen.     

Online task interleaving scheduling for the digital array radar

Aiming at the task scheduling problem in the DAR (digital array radar), an online task interleaving scheduling algorithm is proposed. The full structure of the DAR task is explicitly considered in a way that the waiting duration can be utilized to transmit or receive subtasks, which is called the task interleaving, as well as the receiving durations of different tasks can be overlapped. The algorithm decomposes the task interleaving analysis into the time resource constraint analysis and the energy resource constraint analysis, and online schedules all kinds of tasks that can be interleaved. Thereby the waiting durations and receiving durations can be fully utilized. The simulation results demonstrate that the proposed algorithm improves the successfully scheduling ratio by 73%, the high value ratio by 86% and the time utilization ratio by 55% compared with the HPEDF (highest priority and earliest deadline first) algorithm.     

Bounds on the capacity of a spectrally constrained Poisson channel

An upper bound is derived on the capacity of a Poisson channel that has a stationary input process of a given spectrum and is subjected to peak and average power constraints. The bound is shown to be asymptotically tight with the relaxation of the spectral constraints. Its maximization over a given set of admissible spectra is closely related to an analogous problem in the AWGN regime. The results are used for bounding the capacity of a Poisson channel under a second-moment-bandwidth constraint, as well as the capacity under a strict bandwidth constraint. Asymptotically tight lower bounds on the channel capacity for the above two cases are also presented. The approach for lower bounding the capacity for the latter case yields, as a by-product, improved bounds on the bit-error probability in uncoded amplitude shift keying (and on-off modulation as a special case) operating over a Poisson channel impaired by intersymbol interference     

Module replication for fault-tolerant real-time distributed systems

This paper considers the problem of replicating and scheduling periodic tasks in a multiprocessor system, under timing and dependency constraints. The objective is to maximize the probability of successful completion (logically correct execution, within the time constraints) of all the tasks in the system. The authors assume a precedence graph that is general with chain, AND, OR and loop subgraphs. To achieve high probability of successful completion of the tasks in the system, several modules (that constitute the tasks) are chosen for replication and executed, regardless of whether a failure actually occurs or not. The replicated modules are chosen in an optimal way, and are added to the set of the executable tasks only if that increases the probability of successful completion. The failure model of the modules in the system is general and realistic. The allocation scheme assigns the original and the replicated modules to the processing nodes of the system, and determines their starting time as well as the schedule for communication among them. Their results improve upon the work done previously     

A Lagrangean relaxation approach for QoS networks CFA problems

This paper is about design methodologies for packet networks, under the constraints of end-to-end quality of service (QoS) metrics. The network modeling also considers the dynamics of today's packet networks. We are particularly considering the problem of capacity and flow assignment where the routing assignments and capacities are considered to be decision variables. An efficient Lagrangean relaxation-based heuristic procedure is developed to find bounds and solutions for a corporate virtual private network (VPN), where the traffic is mostly based on TCP connections. Numerical results for a variety of problem instances are reported.     

Augmented Lagrangean Based Algorithms for Centralized Network Design

Capacitated spanning tree problems appear frequently as fundamental problems in many communication network design problems. An integer programming formulation and a new set of valid inequalities are presented for the linear characterization of the problem. A combination of a subgradient optimization procedure and an augmented Lagrangean-based procedure is used to generate tight lower bounds. The procedure begins with an explicit representation of a subset of the constraints, and the corresponding Lagrangean problem is solved. The solution is examined in order to identify implicit constraints that are violated. Those are added to the Lagrangean problem, forming an expanded problem, and an efficient dual ascent procedure is then applied. When no further improvement is possible through this procedure, a subgradient optimization procedure is invoked in order to further tighten the lower bound value. An exchange heuristic is applied to the nonfeasible Lagrangean solution, in an attempt to generate good feasible solutions to the problem. The procedure has been tested and has generated bounds that are significantly better than ones obtained through previously published procedures.