Large fault-tolerant network systems with high Quality of Service (QoS) guarantee are critical in many real world applications and entail diverse replica placement problems. In this paper, the replica placement proble...
详细信息
ISBN:
(纸本)9781728192192
Large fault-tolerant network systems with high Quality of Service (QoS) guarantee are critical in many real world applications and entail diverse replica placement problems. In this paper, the replica placement problem in terms of minimizing the replica placement cost subject to both QoS and fault-tolerant constraints is formulated as a binary integer linear programming problem first and then relaxed as a linear programming problem. Given the optimal fractional linear programming solution, we propose a two-step rounding algorithm to obtain its integer solution. In the first step, a half rounding algorithm is used to simplify the problem. In the second step, a cheapest amortized cost rounding algorithm uses a novel metric, named amortized cost, to make locally optimal rounding decision for the remaining vertices independently. Furthermore, a conflict resolution algorithm is presented to tackle the situations when different vertices make conflicting rounding decisions. Finally, we prove that the proposed two-step rounding algorithm has a 2-approximation ratio when the additional conflict cost meets a given constraint.
The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative gen...
详细信息
ISBN:
(纸本)9781450320290
The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.
We study the covering-type k-violation linear program where at most k of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we prese...
详细信息
We study the covering-type k-violation linear program where at most k of the constraints can be violated. This problem is formulated as a mixed integer program and known to be strongly NP-hard. In this paper, we present a simple (k + 1)approximation algorithm using a natural LP relaxation. We also show that the integrality gap of the LP relaxation is k + 1. This implies we can not get better approximation algorithms when we use the LP-relaxation as a lower bound of the optimal value.
The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best...
详细信息
The hypergraph matching problem is to find a largest collection of disjoint hyperedges in a hypergraph. This is a well-studied problem in combinatorial optimization and graph theory with various applications. The best known approximation algorithms for this problem are all local search algorithms. In this paper we analyze different linear and semidefinite programming relaxations for the hypergraph matching problem, and study their connections to the local search method. Our main results are the following: We consider the standard linear programming relaxation of the problem. We provide an algorithmic proof of a result of Furedi, Kahn and Seymour, showing that the integrality gap is exactly for k-uniform hypergraphs, and is exactly k - 1 for k-partite hypergraphs. This yields an improved approximation algorithm for the weighted 3-dimensional matching problem. Our algorithm combines the use of the iterative rounding method and the fractional local ratio method, showing a new way to round linear programming solutions for packing problems. We study the strengthening of the standard LP relaxation by local constraints. We show that, even after linear number of rounds of the Sherali-Adams lift-and-project procedure on the standard LP relaxation, there are k-uniform hypergraphs with integrality gap at least k - 2. On the other hand, we prove that for every constant k, there is a strengthening of the standard LP relaxation by only a polynomial number of constraints, with integrality gap at most for k-uniform hypergraphs. The construction uses a result in extremal combinatorics. We consider the standard semidefinite programming relaxation of the problem. We prove that the Lovasz -function provides an SDP relaxation with integrality gap at most . The proof gives an indirect way (not by a rounding algorithm) to bound the ratio between any local optimal solution and any optimal SDP solution. This shows a new connection between local search and linear and semidefinite programming
Due to the limited computing power and energy resources of lightweight mobile user devices, offloading their tasks to fog nodes is a promising solution. Partial offloading is a more efficient way to allocate and use t...
详细信息
Due to the limited computing power and energy resources of lightweight mobile user devices, offloading their tasks to fog nodes is a promising solution. Partial offloading is a more efficient way to allocate and use the whole system's resources than binary offloading. In this article, three algorithms are proposed to address the three issues of partial offloading in fog computing. Different from the strategy of minimizing task delay or minimizing power consumption adopted in the existing works of literature, the first algorithm considers both of these two strategies concurrently. The second is proposed to maximize task admission under the constraints of the user device power and system resource. The third is proposed to expand the system resource with the least cost to improve the admission when the system resource is insufficient. The above three are non-deterministic polynomial-time (NP)-hard problems, which will be solved by adopting the strategy of rounding algorithm in this article. Through theoretical analysis, a small gap exists between the solved solution and the optimal one of the problem. Additionally, a large number of simulations will be carried out to verify that their performance is better than that of the recent related works and close to the best performance.
A large number of interesting combinatorial optimization problems like MAX CUT, MAX k-SAT, and UNIQUE GAMES fall under the class of constraint satisfaction problems (CSPs). Recent work [32] by one of the authors ident...
详细信息
ISBN:
(纸本)9780769538501
A large number of interesting combinatorial optimization problems like MAX CUT, MAX k-SAT, and UNIQUE GAMES fall under the class of constraint satisfaction problems (CSPs). Recent work [32] by one of the authors identifies a semidefinite programming (SDP) relaxation that yields the optimal approximation ratio for every CSP, under the Unique Games Conjecture (UGC). Very recently [33], the authors also showed unconditionally that the integrality gap of this basic SDP relaxation cannot be reduced by adding large classes of valid inequalities (e.g., in the fashion of Sherali-Adams LP hierarchies). In this work, we present an efficient rounding scheme that achieves the integrality gap of this basic SDP relaxation for every CSP (and by [33] it also achieves the gap of much stronger SDP relaxations). The SDP relaxation we consider is stronger or equivalent to any relaxation used in literature to approximate CSPs. Thus, irrespective of the truth of the UGC, our work yields an efficient generic algorithm that for every CSP, achieves an approximation at least as good as the best known algorithm in literature. The rounding algorithm in this paper can be summarized succinctly as follows: Reduce the dimension of SDP solution by random projection, discretize the projected vectors, and solve the resulting CSP instance by brute force! Even the proof is simple in that it avoids the use of the machinery from unique games reductions such as dictatorship tests, Fourier analysis or the invariance principle. A common theme of this paper and the subsequent paper [33] is a robustness lemma for SDP relaxations which asserts that approximately feasible solutions can be made feasible by "smoothing" without changing the objective value significantly.
We consider the problem of computing IEEE floating-point squares by means of integer arithmetic. We show how to exploit the specific properties of squaring in order to design and implement algorithms that have much lo...
详细信息
ISBN:
(纸本)9780769543185
We consider the problem of computing IEEE floating-point squares by means of integer arithmetic. We show how to exploit the specific properties of squaring in order to design and implement algorithms that have much lower latency than those for general multiplication, while still guaranteeing correct rounding. Our algorithms are parameterized by the floating-point format, aim at high instruction-level parallelism (ILP) exposure, and cover all rounding modes. We show further that their C implementation for the binary32 format yields efficient codes for targets like the ST231 VLIW integer processor from STMicroelectronics, with a latency at least 1.75x smaller than that of general multiplication in the same context.
The evolution of 5G (Fifth Generation) and B5G (Beyond 5G) wireless networks and edge IoT (Internet of Things) devices generates an enormous volume of data. The growth of mobile applications, such as augmented reality...
详细信息
The evolution of 5G (Fifth Generation) and B5G (Beyond 5G) wireless networks and edge IoT (Internet of Things) devices generates an enormous volume of data. The growth of mobile applications, such as augmented reality, virtual reality, network gaming, and self-driving cars, has increased demand for computation-intensive and latency-critical applications. However, these applications require high computation power and low communication latency, which hinders the large-scale adoption of these technologies in IoT devices due to their inherent low computation and low energy capabilities. MEC (mobile edge computing) is a prominent solution that improves the quality of service by offloading the services near the users. Besides, in emergencies where network failure exists due to natural calamities, UAVs (Unmanned Aerial Vehicles) can be positioned to reinstate the networking ability by serving as flying base stations and edge servers for mobile edge networks. This article explores computation service caching in a multi-unmanned aerial vehicle-assisted MEC system. The limited resources at the UAV node induce added problems of assigning the existing restricted edge resources to satisfy the user requests and the associate of users to utilize the finite resources effectively. To address the above mentioned problems, we formulate the service caching and user association problem by placing the diversified latency-critical services to maximize the time utility with the deadline and resource constraints. The problem is formulated as an integer linear programming (ILP) problem for service placement in mobile edge networks. An approximation algorithm based on the rounding technique is designed to solve the formulated ILP problem. Moreover, a genetic algorithm is designed to address the larger instance of the problem. Simulation results indicate that the proposed service placement schemes considerably enhance the cache hit ratio, load on the cloud and time utility performance compared
暂无评论