Online knapsack with resource augmentation

It is known that online knapsack is not competitive. This negative result remains true even if items are removable. In this paper we consider online removable knapsack with resource augmentation, in which we hold a knapsack of capacity R?1 and aim at maintaining a feasible packing to maximize the total profit of items packed into the knapsack. Both scenarios that removal of accepted items is allowed and is not allowed are investigated. We evaluate an online algorithm by comparing the resulting packing to an optimal packing that uses a knapsack of capacity one. Optimal online algorithms are derived for both the weighted case (items have arbitrary profits) and the unweighted case (the profit of an item is equal to its size).     

Worst Case Execution Time Analysis for a Processor with Branch Prediction

The fundamental requirement for hard real-time systems is that task deadlines be never missed. As a consequence, knowing tasks worst case execution times (WCET) is crucial for such systems. Taking into account modern architectural features makes it possible to determine tighter WCET bounds than with program analysis that ignores such features. While effects of caches and pipelines on WCET analysis have been extensively studied, to our knowledge the effect of the branch prediction on WCET evaluation has not been studied yet. This paper describes a method for statically bounding the number of timing penalties due to erroneous branch predictions. The proposed method is based on static program analysis and branch target buffer modelling. It consists in collecting information on branch target buffer evolution by considering all possible execution paths of a program. Collected information can then be used to classify control transfer instructions so that their worst case branching cost can be estimated and incorporated into the program WCET. A method is also given to tightly predict the WCET of loops whose number of iterations depend on counter variables of outer loops. Experimental results show that the timing penalty due to wrong branch predictions estimated by the proposed technique is close to the real one, which demonstrates the practical applicability of our method.     

Tight bounds on the number of minimum-mean cycle cancellations and related results

We prove a tight (min(nm log(nC), nm²)) bound on the number of iterations of the minimum-mean cycle-canceling algorithm of Goldberg and Tarjan [13]. We do this by giving the lower bound and by improving the strongly polynomial upper bound on the number of iterations toO(nm ²). We also give an improved version of the maximum-mean cut canceling algorithm of [7], which is a dual of the minimum-mean cycle-canceling algorithm. Our version of the dual algorithm runs in O(nm²) iterations.Partially supported by NSF Presidential Young Investigator Grant CCR-8858097 with matching funds provided by AT&T, IBM Faculty Development Award, and a grant from the 3M Corporation.     

Dropout training for SVMs with data augmentation

Dropout and other feature noising schemes have shown promise in controlling over-fitting by artificially corrupting the training data. Though extensive studies have been performed for generalized linear models, little has been done for support vector machines (SVMs), one of the most successful approaches for supervised learning. This paper presents dropout training for both linear SVMs and the nonlinear extension with latent representation learning. For linear SVMs, to deal with the intractable expectation of the non-smooth hinge loss under corrupting distributions, we develop an iteratively re-weighted least square (IRLS) algorithm by exploring data augmentation techniques. Our algorithm iteratively minimizes the expectation of a reweighted least square problem, where the re-weights are analytically updated. For nonlinear latent SVMs, we consider learning one layer of latent representations in SVMs and extend the data augmentation technique in conjunction with first-order Taylor-expansion to deal with the intractable expected hinge loss and the nonlinearity of latent representations. Finally, we apply the similar data augmentation ideas to develop a new IRLS algorithm for the expected logistic loss under corrupting distributions, and we further develop a non-linear extension of logistic regression by incorporating one layer of latent representations. Our algorithms offer insights on the connection and difference between the hinge loss and logistic loss in dropout training. Empirical results on several real datasets demonstrate the effectiveness of dropout training on significantly boosting the classification accuracy of both linear and nonlinear SVMs.     

Autonomic resource provisioning for multilayer cloud applications with K-nearest neighbor resource scaling and priority-based resource allocation

Providing a pool of various resources and services to customers on the Internet in exchanging money has made cloud computing as one of the most popular technologies. Management of the provided resources and services at the lowest cost and maximum profit is a crucial issue for cloud providers. Thus, cloud providers proceed to auto-scale the computing resources according to the users' requests in order to minimize the operational costs. Therefore, the required time and costs to scale-up and down computing resources are considered as one of the major limits of scaling which has made this issue an important challenge in cloud computing. In this paper, a new approach is proposed based on MAPE-K loop to auto-scale the resources for multilayered cloud applications. K-nearest neighbor (K-NN) algorithm is used to analyze and label virtual machines and statistical methods are used to make scaling decision. In addition, a resource allocation algorithm is proposed to allocate requests on the resources. Results of the simulation revealed that the proposed approach results in operational costs reduction, as well as improving the resource utilization, response time, and profit.     

Tight bounds for k-set agreement with limited-scope failure detectors

In a system with limited-scope failure detectors, there are q disjoint clusters of processes such that some correct process in each cluster is never suspected by any process in that cluster. The failure detector class S_x,q satisfies this property all the time, while ⋄S_x,q satisfies it eventually. This paper gives the first tight bounds for the k-set agreement task in asynchronous message-passing models augmented with failure detectors from either the S_x,q or ⋄S_x,q classes. For S_x,q, we show that any k-set agreement protocol that tolerates f failures must satisfy f < k + x − q if q < k and f < x otherwise, where x is the combined size of the q disjoint clusters if q < k (or the k largest, otherwise). This result establishes for the first time that the protocol of Mostèfaoui and Raynal for the S_x = S_x,1 failure detector is optimal. For ⋄S_x,q, we show that any k-set agreement protocol that tolerates f failures must satisfy if q < k and otherwise, where n + 1 is the total number of processes. We give a novel protocol that matches our lower bound, disproving a conjecture of Mostèfaoui and Raynal for the ⋄S_x = ⋄S_x,1 failure detector. Our lower bounds exploit techniques borrowed from Combinatorial Topology, demonstrating for the first time that this approach is applicable to models that encompass failure detectors.     

Worst case analysis of decomposed software pipelining for cyclic unitary RCPSP with precedence delays

In this paper, we address a cyclic scheduling problem of finding a periodic schedule with minimal period for the unitary resource constrained cyclic scheduling problem. The main originality is in being able to cope with both precedence delays and complex resource settings which make the problem NPmathcal{NP}-complete, in general.     

Strong Converse Theorems for Multimessage Networks with Tight Cut-Set Bound

Problems of Information Transmission - This paper considers a multimessage network where each node may send a message to any other node in the network. Under the discrete memoryless model, we prove...     

A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation

Multiagent resource allocation provides mechanisms to allocate bundles of resources to agents, where resources are assumed to be indivisible and nonshareable. A central goal is to maximize social welfare of such allocations, which can be measured in terms of the sum of utilities realized by the agents (utilitarian social welfare), in terms of their minimum (egalitarian social welfare), and in terms of their product (Nash product social welfare). Unfortunately, social welfare optimization is a computationally intractable task in many settings. We survey recent approximability and inapproximability results on social welfare optimization in multiagent resource allocation, focusing on the two most central representation forms for utility functions of agents, the bundle form and the k-additive form. In addition, we provide some new (in)approximability results on maximizing egalitarian social welfare and social welfare with respect to the Nash product when restricted to certain special cases.     

Algorithms for propagating resource constraints in AI planning and scheduling: Existing approaches and new results

This paper summarizes the main existing approaches to propagate resource constraints in Constraint-Based scheduling and identifies some of their limitations for using them in an integrated planning and scheduling framework. We then describe two new algorithms to propagate resource constraints on discrete resources and reservoirs. Unlike most of the classical work in scheduling, our algorithms focus on the precedence relations between activities rather than on their absolute position in time. They are efficient even when the set of activities is not completely defined and when the time window of activities is large. These features explain why our algorithms are particularly suited for integrated planning and scheduling approaches. All our algorithms are illustrated with examples. Encouraging preliminary results are reported on pure scheduling problems as well as some possible extensions of our framework.     

Sensor-data augmentation for human activity recognition with time-warping and data masking

Multimedia Tools and Applications - Human activity recognition (HAR) using an accelerometer can provide valuable information for understanding user context. Therefore, several studies have been...     

Worst case optimal observer design for linear discrete-time systems with unknown bounded square summable disturbances

The problem of the existence and design of an optimal observer is considered for linear discrete-time systems with unknown disturbances additive to the output. The optimal observer reconstructs the best estimate of the state at a given time with respect to the worst disturbances constrained to a ball in l ². It is proved that an observability condition is necessary and sufficient for the existence of such an observer. An explicit formula for the optimal observer is derived (it includes the degenerate case when some of the outputs are disturbance free).     

Worst case control of uncertain jumping systems with multi-state and input delay information

In this paper, the problem of worst case (also called H_∞) Control for a class of uncertain systems with Markovian jump parameters and multiple delays in the state and input is investigated. The jumping parameters are modelled as a continuous-time, discrete-state Markov process and the parametric uncertainties are assumed to be real, time-varying and norm-bounded that appear in the state, input and delayed-state matrices. The time-delay factors are unknowns and time-varying with known bounds. Complete results for instantaneous and delayed state feedback control designs are developed which guarantee the weak-delay dependent stochastic stability with a prescribed H_∞-performance. The solutions are provided in terms of a finite set of coupled linear matrix inequalities (LMIs). Application of the developed theory to a typical example has been presented.     

Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP

2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world” Euclidean instances both with respect to running time and approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on 2-dimensional Euclidean instances was known so far. We clarify this issue by presenting, for every $p\in\mathbb{N}$ , a family of L _p instances on which 2-Opt can take an exponential number of steps. Previous probabilistic analyses were restricted to instances in which n points are placed uniformly at random in the unit square [0,1]², where it was shown that the expected number of steps is bounded by $\tilde{O}(n^{10})$ for Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions on [0,1] ^d , for an arbitrary d≥2. In particular, we allow different distributions for different points. We study the expected number of local improvements in terms of the number n of points and the maximal density ? of the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of $\tilde{O}(n^{4+1/3}\cdot\phi^{8/3})$ . When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to $\tilde{O}(n^{4+1/3-1/d}\cdot\phi^{8/3})$ . If the distances are measured according to the Manhattan metric, then the expected number of steps is bounded by $\tilde{O}(n^{4-1/d}\cdot\phi)$ . In addition, we prove an upper bound of $O(\sqrt[d]{\phi})$ on the expected approximation factor with respect to all L _p metrics. Let us remark that our probabilistic analysis covers as special cases the uniform input model with ?=1 and a smoothed analysis with Gaussian perturbations of standard deviation σ with ?～1/σ ^d .     

Tight Bounds for Selfish and Greedy Load Balancing

We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it chooses, among its permissible servers, to run its job on the server having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness.     

几何约束求解的去并拟合方法

依据有向图理论提出了去并拟合方法,由此导出了对于几何约束求解问题的去并拟合的并行处理及串行处理策略,进而得到了一套求解几何约束问题的完备算法。通过将该理论引入到参数化CAD的设计中,使得在算法复杂度增加不大的情况下,几何自动作图的范围大大拓宽。还将其应用于智能动态几何软件的设计中,取得了较好的结果。     

Corner cutting with trapezoidal augmentation for area-preserving smoothing of polygons and polylines

Recently, a new subdivision method was introduced by the author for smoothing polygons and polylines while preserving the enclosed area [Gordon D. Corner cutting and augmentation: an area-preserving method for smoothing polygons and polylines. Computer Aided Geometric Design 2010; 27(7):551–62]. The new technique, called “corner cutting and augmentation” (CCA), operates by cutting corners with line segments and adding the cut area of each corner to two augmenting structures constructed on the two incident edges; this operation can be iterated as needed. Area is preserved in a local sense, meaning that when a corner is cut, the cut area is added to the other side of the line in immediate proximity to the cut corner. Thus, CCA is also applicable to self-intersecting polygons and polylines, and it enables local control. CCA was originally developed with triangular augmentation, which was called CCA1. This work presents CCA2, in which the augmenting structures are trapezoids. A theoretical result from previous work is used to show that certain implementation restrictions guarantee the existence and the G¹-continuity of the limit curve of CCA2, and also the preservation of convexity. The main difference between CCA1 and CCA2 is that the limit curve of CCA1 does not contain straight line segments, while CCA2 can contain such segments. CCA2 allows the user to determine how closely each iteration follows its previous polygon. Potential applications include computer aided geometric design, an alternative to spline approximation, an aid to artistic design, and a possible alternative to multiresolution curves.     

Deep reinforcement learning for solving resource constrained project scheduling problems with resource disruptions

The resource-constrained project scheduling problem (RCPSP) is encountered in many fields, including manufacturing, supply chain, and construction. Nowadays, with the rapidly changing external environment and the emergence of new models such as smart manufacturing, it is more and more necessary to study RCPSP considering resource disruptions. A framework based on reinforcement learning (RL) and graph neural network (GNN) is proposed to solve RCPSP and further solve the RCPSP with resource disruptions (RCPSP-RD) on this basis. The scheduling process is formulated as sequential decision-making problems. Based on that, Markov decision process (MDP) models are developed for RL to learn scheduling policies. A GNN-based structure is proposed to extract features from problems and map them to action probability distributions by policy network. To optimize the scheduling policy, proximal policy optimization (PPO) is applied to train the model end-to-end. Computational results on benchmark instances show that the RL-GNN algorithm achieves competitive performance compared with some widely used methods.