We extend the classic notion of well-separated pair decomposition [10] to the (weighted) unit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the ...
详细信息
ISBN:
(纸本)9781581136746
We extend the classic notion of well-separated pair decomposition [10] to the (weighted) unit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unit-disk graph metric of n points in the plane and for any constant c≥1, there exists a c-well-separated pair decomposition with O(n log n) pairs, and the decomposition can be computed in O(n log n) time. We also show that for the unit-ball graph metric in k dimensions where k≥3, there exists a c-well-separated pair decomposition with O(n2-2/k) pairs, and the bound is tight in the worst case. We present the application of the well-separated pair decomposition in obtaining efficient algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unit-disk graph metric.
In order to solve the nonlinear programming problem with inequality constraints, a method for smoothing the square-root exact penalty function is proposed. Error estimations are obtained among the optimal objectiv...
详细信息
In order to solve the nonlinear programming problem with inequality constraints, a method for smoothing the square-root exact penalty function is proposed. Error estimations are obtained among the optimal objective function values of the smoothed penalty problem, of the nonsmooth exact penalty problem and of the original constrained optimization problem. Based on the smoothed penalty function, an efficient algorithm for solving the optimization problem with inequality constraints is presented. Moreover, the convergence of the algorithm is proved.
The construction of alphabetic prefix codes with unequal letter costs and unequal probabilities is considered. A variant of the noiseless coding theorem is proved giving closely matching lower and upper bounds for the...
详细信息
Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let P and ...
详细信息
In this article, we study approximation algorithms for the problem of computing minimum dominating set for a given set S of n unit disks in R2. We first present a simple O(nlogk) time 5-factor approximation algorithm ...
详细信息
We study a maximization problem for geometric network design. Given a set of n compact neighborhoods in R-d, select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has max...
详细信息
We study a maximization problem for geometric network design. Given a set of n compact neighborhoods in R-d, select a point in each neighborhood, so that the longest spanning tree on these points (as vertices) has maximum length. Here, we give an approximation algorithm with ratio 0.511, which represents the first, albeit small, improvement beyond 1/2. While we suspect that the problem is NP-hard already in the plane, this issue remains open.
Numerous approximation algorithms for problems on unit disk graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a variation of the kno...
详细信息
We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching *** processing time of each job is defined by an interval and any number of jobs can be assigned into a batch...
详细信息
We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching *** processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not *** problems are considered:(1)minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2)minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;(3)minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted *** provide an O(n2)time algorithm for the first ***,for the other two problems,we first show that they are NP-hard,and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them,respectively.
Beaconing is a primitive communication task in which every node locally broadcasts a packet to all its neighbors within a fixed distance. Assume that all communications proceed in synchronous time-slots and each node ...
详细信息
ISBN:
(纸本)9781424458363
Beaconing is a primitive communication task in which every node locally broadcasts a packet to all its neighbors within a fixed distance. Assume that all communications proceed in synchronous time-slots and each node can transmit at most one fixed-size packet in each time-slot. The problem Minimum-latency beaconing schedule (MLBS) in multihop wireless networks seeks a shortest schedule for beaconing subject to the interference constraint. MLBS has been intensively studied since the mid-1980s, but all assume the protocol interference model with uniform interference radii. In this paper, we first present a constant-approximation algorithm for MLBS under the protocol interference model with arbitrary interference radii. Then, we develop a constant-approximation algorithm for MLBS under the physical interference model. Both approximation algorithms have efficient implementations in a greedy first-fit manner.
The resource allocation problem deals with distributing a number of indivisible, nonshareable resources among a set of agents so as to optimizing social welfare. Assuming all agents to have additive utility functions ...
详细信息
ISBN:
(纸本)9781450319935
The resource allocation problem deals with distributing a number of indivisible, nonshareable resources among a set of agents so as to optimizing social welfare. Assuming all agents to have additive utility functions and focusing on two particular measures of social welfare, envy-ratio and average-Nash product, we investigate the two resulting optimization problems. We give the first hardness of approximation result for a factor better than 3/2 for the problem of minimum envy-ratio, and we design an FPTAS for the case when the number of agents is fixed. For the special case when the number of agents and the number of resources are equal, we show that the problem is even solvable in polynomial time. Next, we propose the first approximation algorithm for maximizing the average-Nash product in the general case, and we prove that this problem admits a PTAS if all agents' utility functions are the same. Finally, we study the problem of how hard it is to design a truthful mechanism for these two optimization problems.
暂无评论