We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p(...
详细信息
We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p(i,j) time units and incurs a cost c(i,) j, and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [1], we construct a more general approach that can be used to derive approximation schemes for a wider class of load balancing problems with linear constraints. (c) 2020 Elsevier B.V. All rights reserved.
Electric autonomous vehicles provide a promising solution to the traffic congestion and air pollution problems in future smart cities. Considering intensive energy consumption, charging becomes of paramount importance...
详细信息
ISBN:
(纸本)9781728164120
Electric autonomous vehicles provide a promising solution to the traffic congestion and air pollution problems in future smart cities. Considering intensive energy consumption, charging becomes of paramount importance to sustain the operation of these systems. Motivated by the innovations in renewable energy harvesting, we leverage solar energy to power autonomous vehicles via charging stations and solar-harvesting rooftops, and design a framework that optimizes the operation of these systems from end to end. With a fixed budget, our framework first optimizes the locations of charging stations based on historical spatial-temporal solar energy distribution and usage patterns, achieving (2+epsilon) factor to the optimal. Then a stochastic algorithm is proposed to update the locations online to adapt to any shift in the distribution. Based on the deployment, a strategy is developed to assign energy requests in order to minimize their traveling distance to stations while not depleting their energy storage. Equipped with extra harvesting capability, we also optimize route planning to achieve a reasonable balance between energy consumed and harvested en-route. Our extensive simulations demonstrate the algorithm can approach the optimal solution within 10-15% approximation error, and improve the operating range of vehicles by up to 2-3 times compared to other competitive strategies.
Delay is known to be a critical performance metric for various real-world routing applications including multimedia communication and freight delivery. Provisioning delay-minimal (or at least delay-bounded) routing se...
详细信息
Delay is known to be a critical performance metric for various real-world routing applications including multimedia communication and freight delivery. Provisioning delay-minimal (or at least delay-bounded) routing services for all traffic of an application is highly important. As a basic paradigm of networking, multi-path routing has been proven to be able to obtain lower delay performance than the single-path routing, since traffic congestions can be avoided. However, to our best knowledge, (i) many of existing delay-aware multi-path routing studies only consider the aggregate traffic delay. Considering that even the solution achieving the optimal aggregate traffic delay has a possibly unbounded delay performance for certain individual traffic unit, those studies may be insufficient in practice; besides, (ii) most existing studies which optimize or bound delays of all traffic are best-effort, where the achieved solutions have no theoretical performance guarantee. In this dissertation, we study four delay-aware multi-path routing problems, with the delay performances of all traffic taken into account. Three of them are in communication and one of them is in transportation. Note that our study differ from all related ones as we are the first to study the four fundamental problems to our best knowledge. Although we prove that our studied problems are all NP-hard, we design approximationalgorithms with theoretical performance guarantee for solving each of them. To be specific, we claim the following contributions. Minimize maximum delay and average delay. First, we consider a single-unicast setting where in a multi-hop network a sender requires to use multiple paths to stream a flow at a fixed rate to a receiver. Two important delay metrics are the average sender-to-receiver delay and the maximum sender-to-receiver delay. Existing results say that the two delay metrics of a flow cannot be both within bounded-ratio gaps to the optimal. In comparison, we design three d
We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same su...
详细信息
We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We study several problems in framework of classic complexity and approximation for which the compatibility graph is bipartite (star, chain, ...). In such a context, we design some efficient polynomial-time approximation algorithms for an intractable scheduling problem according to some parameters.
To promise on-line and adaptive traffic engineering in software defined networks (SDNs), the control messages, e.g., the first packet of every new flow and network traffic statistics, should be forwarded from software...
详细信息
To promise on-line and adaptive traffic engineering in software defined networks (SDNs), the control messages, e.g., the first packet of every new flow and network traffic statistics, should be forwarded from software defined switches to the controller(s) in a fast and robust manner. As many signaling events and control plane operations are required in SDNs, they could easily generate a significant amount of control traffic that must be addressed together with the data traffic. However, the usage of in-band control channel imposes a great challenge into timely and reliable transmissions of control traffic, while out-band control is usually cost-prohibitive. To counter this, in this paper, the control traffic balancing problem is first formulated as a nonlinear optimization framework with an objective to find the optimal control traffic forwarding paths for each switch in such a way the average control traffic delay in the whole network is minimized. This problem is extremely critical in SDNs because the timely delivery of control traffic initiated by Openflow switches directly impacts the effectiveness of the routing strategies. Specifically, the fundamental mathematical structures of the formulated nonlinear problem and solution set are provided and accordingly, an efficient algorithm, called polynomial-time approximation algorithm (PTAA), is proposed to yield the fast convergence to a near optimal solution by employing the alternating direction method of multipliers (ADMM). Furthermore, the optimal controller placement problem in in-band mode is examined, which aims to find the optimal switch location where the controller can be collocated by minimizing the control message delay. While it is not widely researched except quantitative or heuristic results, a simple and efficient algorithm is proposed to guarantee the optimum placement with regards of traffic statistics. Simulation results confirm that the proposed PTAA achieves considerable delay reduction, greatly
We explore in this paper some complexity issues inspired by the contig scaffolding problem in bioinformatics. We focus on the following problem: given an undirected graph with no loop, and a perfect matching on this g...
详细信息
We explore in this paper some complexity issues inspired by the contig scaffolding problem in bioinformatics. We focus on the following problem: given an undirected graph with no loop, and a perfect matching on this graph, find a set of cycles and paths covering every vertex of the graph, with edges alternatively in the matching and outside the matching, and satisfying a given constraint on the numbers of cycles and paths. We show that this problem is NP-complete, even in planar bipartite graphs. Moreover, we show that there is no subexponential-timealgorithm for several related problems unless the Exponential-time Hypothesis fails. Lastly, we also design two polynomial-time approximation algorithms for complete graphs. (C) 2015 Elsevier B.V. All rights reserved.
We tackle the makespan minimization coupledtasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and id...
详细信息
ISBN:
(纸本)9781479967735
We tackle the makespan minimization coupledtasks problem in presence of compatibility constraints. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. In such context, we propose some complexity results according to several parameters and we design an efficient polynomial-time approximation algorithm.
We study the problem of graph summarization. Given a large graph we aim at producing a concise lossy representation that can be stored in main memory and used to approximately answer queries about the original graph m...
详细信息
ISBN:
(纸本)9781479943036
We study the problem of graph summarization. Given a large graph we aim at producing a concise lossy representation that can be stored in main memory and used to approximately answer queries about the original graph much faster than by using the exact representation. In this paper we study a very natural type of summary: the original set of vertices is partitioned into a small number of supernodes connected by superedges to form a complete weighted graph. The superedge weights are the edge densities between vertices in the corresponding supernodes. The goal is to produce a summary that minimizes the reconstruction error w.r.t. the original graph. By exposing a connection between graph summarization and geometric clustering problems (i.e., k-means and k-median), we develop the first polynomial-time approximation algorithm to compute the best possible summary of a given size.
The data association problem appears in many applications and is considered as the most challenging problem in intelligent systems. In this paper, we consider the Bayesian formulation of data association problems and ...
详细信息
ISBN:
(纸本)9781457705137
The data association problem appears in many applications and is considered as the most challenging problem in intelligent systems. In this paper, we consider the Bayesian formulation of data association problems and present a deterministic polynomial-time approximation algorithm with guaranteed error bounds using correlation decay from statistical physics. We then show that the proposed algorithm naturally partitions a complex problem into a set of local problems and develop a distributed version of the algorithm. The performance of the proposed algorithm is evaluated in simulation.
We consider the problem of scheduling n independent jobs on m parallel machines, where the machines differ in their functionality but not in their processing speeds. Each job has a restricted set of machines to which ...
详细信息
We consider the problem of scheduling n independent jobs on m parallel machines, where the machines differ in their functionality but not in their processing speeds. Each job has a restricted set of machines to which it can be assigned, called its processing set. Preemption is not allowed. Our goal is to minimize the makespan of the schedule. We study two variants of this problem: (1) the case of tree-hierarchical processing set and (2) the case of nested processing set. We first give a fast algorithm for the case of tree-hierarchical processing set with a worst-case bound of 4/3, which is better than the best known algorithm whose worst-case bound is 2. We then give a more complicated algorithm for the case of nested processing set with a worst-case bound of 5/3, which is better than the best known algorithm whose worst-case bound is 7/4. In both cases, we will give examples achieving the worst-case bounds. (C) 2010 Elsevier B.V. All rights reserved.
暂无评论