Search

Many modern day cloud hosted applications such as virtual reality, real time games require low latency data access and computation to improve response time. So it is essential to bring the computation and data storage edge servers closer to the user's geographical location to improve response times and save bandwidth. In particulars, in online gaming and on demand video services, the required application data present at cloud servers need to be placed on the edge servers to provide low latency app-functionalities. The transfer of huge amount of data from cloud server to edge server incurs high cost and time penalties. Thus, we need an efficient way to solve edge data distribution (EDD) problem which distribute the application data to the edge servers that minimizes transfer cost. In this work, we provide a refined formulation of an optimal approach to solve the EDD problem using integer linear programming (ILP) technique. Due to the time complexity limitation of the ILP approach, we propose an O(k) approximation algorithm based on network Steiner tree estimation (EDD-NSTE) for estimating solutions to dense large-scale EDD problem. The proposed approach is analyzed to be 11/6 approximation which is better than the state-of-the-art 2 approximation EDD-A approach. The experimental evaluation through simulation using real world EUA data set demonstrate that the EDD-NSTE outperform state-of-the-art approach and other representative approaches. [ABSTRACT FROM AUTHOR]

In this paper we analyze the links between the agent's reservation utility, bargaining power, and risk aversion in terms of their simultaneous effects on the structure of optimal static contracts. We compare the following principal-agent models in the symmetric and asymmetric information environments: the standard approach, which includes a participation constraint, and a multi-objective (MO) optimization approach in which the objective function is a convex combination of the expected utilities of the principal and the agent. The MO model does not include a participation constraint, but it includes a parameter for the agent's bargaining power. We also study an Evolutionary Algorithm implementation of the static principal-agent model to support and extend our analytical results. We show that the numerical solution approximated by our implementation of an evolutionary algorithm is in line with the analytical solutions mentioned before. That is, for every admissible value of the agent's reservation utility, there is a corresponding admissible value of the agent's bargaining parameter, both in the MO approach and the EA implementation. [ABSTRACT FROM AUTHOR]

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles. [ABSTRACT FROM AUTHOR]

The gate-based model is one of the leading quantum computing paradigms for representing quantum circuits. Within this paradigm, a quantum algorithm is expressed in terms of a set of quantum gates that are executed on the quantum hardware over time, subject to a number of constraints whose satisfaction must be guaranteed before running the circuit, to allow for feasible execution. The need to guarantee the previous feasibility condition gives rise to the Quantum Circuit Compilation Problem (QCCP). The QCCP has been demonstrated to be NP-Complete, and can be considered as a Planning and Scheduling problem. In this paper, we consider quantum compilation instances deriving from the general Quantum Approximation Optimization Algorithm (QAOA), applied to the MaxCut problem, devised to be executed on Noisy Intermediate Scale Quantum (NISQ) hardware architectures. More specifically, in addition to the basic QCCP version, we also tackle other variants of the same problem such as the QCCP-X (QCCP with crosstalk constraints), the QCCP-V (QCCP with variable qubit state initialization), as well as the QCCP-VX that includes both previous variants. All problem variants are solved using genetic algorithms. We perform an experimental study across a conventional set of instances taken from the literature, and show that the proposed genetic algorithm, termed G A VX , outperforms previous approaches in the literature. [ABSTRACT FROM AUTHOR]

In healthcare management, one important problem is how to efficiently allocate resources with limited capacities. From the point of view of a central decision maker with a long planning horizon, many healthcare resources such as appointment slots, operation rooms, and hospital beds can be regarded as reusable resources. Motivated by this observation, we study a new version of the assignment problem of reusable resources to sequentially arriving users. Different from previous works on reusable resources, we assume that each user will tell us the intended usage duration of each resource upfront before a decision needs to be made. In the setting where users arrive randomly according to a certain distribution, we propose an algorithm based on linear approximations of the optimal value functions, and show that it performs better than common methods developed for the case where usage times are known upon return in different simulations, as well as in a case study with real data. When users arrive in an adversarial order, we show by example that it is hard to design an algorithm with a lower-bounded competitive ratio. As users are much less likely to arrive in an adversarial order in reality, our proposed algorithm can be used to effectively schedule resources such as appointment slots and operation rooms in hospitals. [ABSTRACT FROM AUTHOR]

We provide here an optimal method of approximating a signal by piecewise constant functions. To this end, we minimize over the signal subdomains a fidelity term between the signal and its corresponding piecewise approximations; subdomains being determined by the number of approximations samples used for. An optimal recursive relationship is then obtained and proven, which helps us to derive the proposed approximation algorithm. The complexity of the algorithm is O( MN 2 ), where N is the number of samples of the processed signal and M is the number of piecewise constant approximation functions. There are different techniques to approximate a signal using piecewise constant functions, wavelet decomposition is one of them by means of a Haar wavelet. Our approach is then compared to linear and nonlinear wavelet-based approximations, and both qualitative and quantitative results are provided on various tested signals, showing the efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

In this paper, a new group of optimization algorithms named Human Strategy Algorithm (HS) is proposed which is inspired by human strategies to problem solving. The main idea of HS is based on human actions to find the problem’s optima by means of accessible instruments. As the environment of an unknown problem assumed to be a black box, it is supposed that the environment of our problem is a dark room occupied by several men named blind men. The main mission of these men is to look for the optimum solution. Each man has at least one instrument as his assistance. Like real life, the instrument might be any tool such as stick, billy, rope, stone, yoyo, sweep. Any instrument by its unique features is suitable in some situations. In fact, this algorithm maps problem space and searches agents to dark room and people, respectively. In this paper, one sample algorithm of the group of human strategy, YOYO Blind Man Algorithm (YOYO-BMA), is introduced which uses yoyos as men’s accessible instruments. The performance of the YOYO-BMA is evaluated on a set of benchmark problems provided for CEC’2010 Special Session and Competition on Large-Scale Global Optimization (Tang et al. 2010). The results show superior performance of proposed algorithm in comparison with others. Moreover, the problem of designing urban traffic network is solve to evaluate the algorithm using a real complex problem. [ABSTRACT FROM AUTHOR]

Missing value imputation with crowdsourcing is a novel method in data cleaning to capture missing values that could hardly be filled with automatic approaches. However, the time cost and overhead in crowdsourcing are high. Therefore, we have to reduce cost and guarantee the accuracy of crowdsourced imputation. To achieve the optimization goal, we present COSSET+, a crowdsourced framework optimized by knowledge base. We combine the advantages of both knowledge-based filter and crowdsourcing platform to capture missing values. Since the amount of crowd values will affect the cost of COSSET+, we aim to select partial missing values to be crowdsourced. We prove that the crowd value selection problem is an NP-hard problem and develop an approximation algorithm for this problem. Extensive experimental results demonstrate the efficiency and effectiveness of the proposed approaches. [ABSTRACT FROM AUTHOR]

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple, linear time 2-approximation algorithm for this problem, improving on the previous best known algorithm for the problem, which has approximation ratio 3. [ABSTRACT FROM AUTHOR]

Greedy algorithms which use only function evaluations are applied to convex optimization in a general Banach space $$X$$ . Along with algorithms that use exact evaluations, algorithms with approximate evaluations are treated. A priori upper bounds for the convergence rate of the proposed algorithms are given. These bounds depend on the smoothness of the objective function and the sparsity or compressibility (with respect to a given dictionary) of a point in $$X$$ where the minimum is attained. [ABSTRACT FROM AUTHOR]

Motivated by issues in allocating limited preventative resources to protect a landscape against the spread of a wildfire from a stochastic ignition point, we give approximation algorithms for a new family of stochastic optimization problems. We study several models in which we are given a graph with edge costs and node values, a budget, and a probabilistic distribution over ignition nodes: the goal is to find a budget-limited set of edges whose removal protects the largest expected value from being reachable from a stochastic ignition node. In particular, 2-stage stochastic models capture the tradeoffs between preventative treatment and real-time response. The resulting stochastic cut problems are interesting in their own right, and capture a number of related interdiction problems, both in the domain of computational sustainability, and beyond. In trees, even the deterministic problem is (weakly) NP hard: we give a Polynomial-time approximation scheme for the single-stage stochastic case in trees when the number of scenarios is constant. For the 2-stage stochastic model in trees we give a $(1-\frac {1}{e})<(1-(1-1/2\delta )^{2\delta })$-approximation in trees which violates the budget by a factor of at most 2 (δ is the tree diameter), and a 0.387-approximation that is budget-balanced. For the single-stage stochastic case in trees we can save (1− (1 − 1/ δ) OPT without violating the budget. Single-stage results extend to general graphs with an additional O(log n) loss in budget-balancedness. Multistage results have a similar extension when the number of scenarios is constant. In an extension of the single-stage model where both ignition and spread are stochastic we give a $(1-\frac {1}{e})$-approximation in trees. Our approximation guarantees in trees also hold for multistage and probabilistic-element-failure generalizations of the Maximum Coverage with Knapsack Constraint problem (MCKP). [ABSTRACT FROM AUTHOR]

Given a vertex-weighted undirected graph $$G=(V,E,w)$$ and a positive integer $$k$$ , we consider the $$k$$ -separator problem: it consists in finding a minimum-weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to $$k$$ . We show that this problem can be solved in polynomial time for some graph classes including bounded treewidth, $$m K_2$$ -free, $$(G_1, G_2, G_3, P_6)$$ -free, interval-filament, asteroidal triple-free, weakly chordal, interval and circular-arc graphs. Polyhedral results with respect to the convex hull of the incidence vectors of $$k$$ -separators are reported. Approximation algorithms are also presented. [ABSTRACT FROM AUTHOR]

Approximation mechanism design without money was first studied in Procaccia and Tennenholtz () by considering a facility location game. In general, a facility is being opened and the cost of an agent is measured by its distance to the facility. In order to achieve a good social cost, a mechanism selects the location of the facility based on the locations reported by agents. It motivates agents to strategically report their locations to get good outcomes for themselves. A mechanism is called strategyproof if no agents could manipulate to get a better outcome by telling lies regardless of any configuration of other agents. The main contribution in this paper is to explore the strategyproof mechanisms without money when agents are distinguishable. There are two main variations on the nature of agents. One is that agents prefer getting closer to the facility, while the other is that agents prefer being far away from the facility. We first consider the model that directly extends the model in Procaccia and Tennenholtz (). In particular, we consider the strategyproof mechanisms without money when agents are weighted. We show that the strategyproof mechanisms in the case of unweighted agents are still the best in the weighted cases. We establish tight lower and upper bounds for approximation ratios on the optimal social utility and the minimum utility when agents prefer to stay close to the facility. We then provide the lower and upper bounds on the optimal social utility and lower bound on the minimum distance per weight when agents prefer to stay far away from the facility. We also extend our study in a natural direction where two facilities must be built on a real line. Secondly, we propose an novel threshold based model to distinguish agents. In this model, we present a strategyproof mechanism that leads to optimal solutions in terms of social cost. [ABSTRACT FROM AUTHOR]

As mobile nodes roam in a wireless network, they continuously associate with different access points and perform handoff operations. Frequent handoffs performed by a mobile device may have undesirable consequences, as they can cause interruptions for interactive applications and increase the energy usage of mobile devices. While existing approaches to this issue focus entirely on improving the latency incurred by individual handoffs, in this paper, we initiate a novel approach to association control of mobile devices with the goal of reducing the frequency of handoffs for mobile devices. We study the handoff minimization problem across multiple dimensions: offline versus online where the complete knowledge of mobility patterns of users is known in advance or unknown respectively; capacity constrained versus unconstrained access points, which imposes limits on the number of mobile devices which could be associated with a given access point at any given point in time; group mobility versus arbitrary mobility of users, which are contrasting ways to model the mobility patterns of the mobile users. We consider various combinations of the above dimensions and present the following: (1) optimal algorithms, (2) provably-good online and offline approximation algorithms, (3) complexity (NP-Completeness) results, and (4) a practical heuristic which is demonstrated to work well on real network traces. [ABSTRACT FROM AUTHOR]

High Dimensional Model Representation (HDMR) method is a technique that represents a multivariate function in terms of less-variate functions. Even though the method has a finite expansion, to determine the components of this expansion is very expensive due to integration based natures of the components. Hence, the HDMR expansion is generally truncated at certain multivariance level and such approximations are produced to represent the given multivariate function approximately. The weight function selection becomes an important issue for the HDMR based applications when it is desired to give different importances to function values at different points. An appropriately chosen weight function may increase the quality of the approximation incredibly. This work aims at a multivariate weight function optimization to obtain high quality approximations through the HDMR method to represent multivariate functions. The proposed optimization considers constancy measurer maximization which produces a quadratic vector equation to be solved. Another contribution of this work is to use a recently developed method, fluctuation free integration, with HDMR, to solve this equation easily. This work is an extension of a previous work about weight optimization in HDMR for univariate functions. [ABSTRACT FROM AUTHOR]

In this paper, an improved training algorithm based on the terminal attractor concept for feedforward neural network learning is proposed. A condition to avoid the singularity problem is proposed. The effectiveness of the proposed algorithm is evaluated by various simulation results for a function approximation problem and a stock market index prediction problem. It is shown that the terminal attractor based training algorithm performs consistently in comparison with other existing training algorithms. [ABSTRACT FROM AUTHOR]