This paper presents a polynomial-time 1/2-approximation algorithm for maximizing nonnegative k-submodular functions. This improves upon the previous max{l/3,1/(1+ a)}-approximation by Ward and Živný [18], where a...
详细信息
ISBN:
(纸本)9781510819672
This paper presents a polynomial-time 1/2-approximation algorithm for maximizing nonnegative k-submodular functions. This improves upon the previous max{l/3,1/(1+ a)}-approximation by Ward and Živný [18], where a = max{l, √(k - l)/4}. We also show that for monotone k-submodular functions there is a polynomial-time k/(2k - l)-approximation algorithm while for any ϵ > 0 a ((k + l)/2k + ϵ)-approximation algorithm for maximizing monotone/e-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skewbisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.
As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and w...
详细信息
As a fundamental optimization problem, the vehicle routing problem has wide application backgrounds and has been paid lots of attentions in past decades. In this paper we study its applications in data gathering and wireless energy charging for wireless sensor networks, by devising improved approximation algorithms for it and its variants. The key ingredients in the algorithm design include exploiting the combinatorial properties of the problems and making use of tree decomposition and minimum weighted maximum matching techniques. Specifically, given a metric complete graph G and an integer k > 0, we consider rootless, uncapacitated rooted, and capacitated rooted min-max cycle cover problems in G with an aim to find k rootless (or rooted) edge-disjoint cycles covering the vertices in V such that the maximum cycle weight among the k cycles is minimized. For each of the mentioned problems, we develop an improved approximate solution. That is, for the rootless min-max cycle cover problem, we develop a (5 1/3 + epsilon)-approximation algorithm;for the uncapacitated rooted min-max cycle cover problem, we devise a (6 1/3 + epsilon)-approximation algorithm;and for the capacitated rooted min-max cycle cover problem, we propose a (7 + epsilon)-approximation algorithm. These algorithms improve the best existing approximation ratios of the corresponding problems 6 + epsilon, 7 + epsilon, and 13 + epsilon, respectively, where epsilon is a constant with 0 < + < 1. We finally evaluate the performance of the proposed algorithms through experimental simulations. Experimental results show that the actual approximation ratios delivered by the proposed algorithms are always no more than 2, much better than their analytical counterparts.
Compressive sensing (CS) states that a sparse signal can be recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. The framework of model-based CS...
详细信息
Compressive sensing (CS) states that a sparse signal can be recovered from a small number of linear measurements, and that this recovery can be performed efficiently in polynomial time. The framework of model-based CS (model-CS) leverages additional structure in the signal and provides new recovery schemes that can reduce the number of measurements even further. This idea has led to measurement-efficient recovery schemes for a variety of signal models. However, for any given model, model-CS requires an algorithm that solves the model-projection problem: given a query signal, report the signal in the model that is closest to the query signal. Often, this optimization can be computationally very expensive. Moreover, an approximation algorithm is not sufficient for this optimization to provably succeed. As a result, the model-projection problem poses a fundamental obstacle for extending model-CS to many interesting classes of models. In this paper, we introduce a new framework that we call approximation-tolerant model-CS. This framework includes a range of algorithms for sparse recovery that require only approximate solutions for the model-projection problem. In essence, our work removes the aforementioned obstacle to model-CS, thereby extending model-CS to a much wider class of signal models. Interestingly, all our algorithms involve both the minimization and the maximization variants of the model-projection problem. We instantiate this new framework for a new signal model that we call the constrained earth mover distance (CEMD) model. This model is particularly useful for signal ensembles, where the positions of the nonzero coefficients do not change significantly as a function of spatial (or temporal) location. We develop novel approximation algorithms for both the maximization and the minimization versions of the model-projection problem via graph optimization techniques. Leveraging these algorithms and our framework results in a nearly sample-optimal sparse recove
We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n(3)) and O(n(2)), respectively. For a penny graph, our proposed 2-approximat...
详细信息
We propose a 2-approximation algorithm for the maximum independent set problem for a unit disk graph. The time and space complexities are O(n(3)) and O(n(2)), respectively. For a penny graph, our proposed 2-approximation algorithm works in O(n logn) time using O(n) space. We also propose a polynomial-time approximation scheme (PTAS) for the maximum independent set problem for a unit disk graph. Given an integer k > 1, it produces a solution of size 1/(1+1/k)(2) vertical bar OPT vertical bar in O(k(4)n(sigma k) (logk) + nlogn) time and O(n + klogk) space, where OPT is the subset of disks in an optimal solution and ak sigma k <= 2. For a penny graph, the proposed PTAS produces a solution of size 1/(1+1/k) vertical bar OPT vertical bar in O(2(2 sigma k)nk + nlogn) time using O(2(2 sigma k)+n) space. (C) 2014 Elsevier B.V. All rights reserved.
Given a set of communication links in cognitive radio networks, assume that the underlying channel state information along each link is unknown;however, we can estimate it by exploiting the feedbacks and evolutions of...
详细信息
ISBN:
(纸本)9781467399548
Given a set of communication links in cognitive radio networks, assume that the underlying channel state information along each link is unknown;however, we can estimate it by exploiting the feedbacks and evolutions of channel states. Assume time is divided into time-slots. Under the protocol interference model, the opportunistic spectrum scheduling problem aims to select interference-free links to transmit at each time-slot to maximize the average throughput over the long time horizon. Existing works on the opportunistic spectrum scheduling problem cannot satisfyingly address the wireless interference constraints. We apply the framework of restless multi-armed bandit and develop approximation algorithms for the problem with stochastic identical links and nonidentical links respectively. Based on the updated estimations of channel states, the proposed algorithms keep refining future link scheduling decisions. We also obtain approximation bounds of these two proposed algorithms.
We study the problem of approximating the quality of a disperser. A bipartite graph G on ([N], [M]) is a (ρN, (1 -δ)M)-disperser if for any subset S ⊆ [N] of size ρN, the neighbor set Γ (S) contains at least (1-δ...
详细信息
The modularity is a quality function in community detection, which was introduced by Newman and Girvan (2004). Community detection in graphs is now often conducted through modularity maximization: given an undirected ...
详细信息
We consider the problem of scheduling a set of jobs on a single machine subject to inventory constraints, i.e., conditions that jobs add or remove items to or from a centralized inventory, respectively. Jobs that remo...
详细信息
We consider the problem of scheduling a set of jobs on a single machine subject to inventory constraints, i.e., conditions that jobs add or remove items to or from a centralized inventory, respectively. Jobs that remove items cannot be processed if the required number of items is not available. We focus on scheduling problems on a single machine where the objective is to minimize the total weighted completion time. In this paper, we design 2-approximation algorithms for special cases of the problem that run in polynomial time.
Co-flow scheduling is a recent networking abstraction introduced to capture application-level communication patterns in datacenters. In this paper, we consider the offline co-flow scheduling problem with release times...
详细信息
ISBN:
(纸本)9781450342100
Co-flow scheduling is a recent networking abstraction introduced to capture application-level communication patterns in datacenters. In this paper, we consider the offline co-flow scheduling problem with release times to minimize the total weighted completion time. Recently, Qiu, Stein and Zhong [1] obtained the first constant approximation algorithms for this problem with a deterministic 67/3-approximation and a randomized (9 + 16√2/3) ≈ 16.54-approximation. In this paper, we improve upon their algorithm to yield a deterministic 12-approximation algorithm. For the special case when all release times are zero, we obtain a deterministic 8-approximation and a randomized (3 + 2√2) ≈ 5.83-approximation.
The Joint Replenishment Problem () is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the r...
详细信息
The Joint Replenishment Problem () is a fundamental optimization problem in supply-chain management, concerned with optimizing the flow of goods from a supplier to retailers. Over time, in response to demands at the retailers, the supplier ships orders, via a warehouse, to the retailers. The objective is to schedule these orders to minimize the sum of ordering costs and retailers' waiting costs. We study the approximability of , the version of with deadlines, where instead of waiting costs the retailers impose strict deadlines. We study the integrality gap of the standard linear-program (LP) relaxation, giving a lower bound of , a stronger, computer-assisted lower bound of , as well as an upper bound and approximation ratio of . The best previous upper bound and approximation ratio was;no lower bound was previously published. For the special case when all demand periods are of equal length, we give an upper bound of , a lower bound of , and show APX-hardness.
暂无评论