We study graph orientations that minimize the entropy of the in-degree sequence. We prove that the minimum entropy orientation problem is NP-hard even if the graph is planar, and that there exists a simple linear-time...
详细信息
We study graph orientations that minimize the entropy of the in-degree sequence. We prove that the minimum entropy orientation problem is NP-hard even if the graph is planar, and that there exists a simple linear-time algorithm that returns an approximate solution with an additive error guarantee of 1 bit. (C) 2008 Universite Libre de Bruxelles. Belgium. Published by Elsevier B.V. All rights reserved.
Partitioning a permutation into a minimum number of monotone subsequences is NP-hard. We extend this complexity result to minimum partitioning into k-modal subsequences;here unimodal is the special case k = 1. Based o...
详细信息
Partitioning a permutation into a minimum number of monotone subsequences is NP-hard. We extend this complexity result to minimum partitioning into k-modal subsequences;here unimodal is the special case k = 1. Based on a network flow interpretation we formulate both, the monotone and the k-modal version, as mixed integer programs. This is the first proposal to obtain provably optimal partitions of permutations. LP rounding gives a 2-approximation for minimum monotone partitions and a (k + 1)approximation for minimum (upper) k-modal partitions. For the online problem, in which the permutation becomes known to an algorithm sequentially, we derive a logarithmic lower bound on the competitive ratio for minimum monotone partitions, and we analyze two (bin packing) online algorithms. These immediately apply to online cocoloring of permutation graphs. (C) 2008 Elsevier B.V. All rights reserved.
We study the problem of allocating students to projects, where both students and lecturers have preferences over projects, and both projects and lecturers have capacities. In this context we seek a stable matching of ...
详细信息
We study the problem of allocating students to projects, where both students and lecturers have preferences over projects, and both projects and lecturers have capacities. In this context we seek a stable matching of students to projects, which respects these preference and capacity constraints. Here, the stability definition generalises the corresponding notion in the context of the classical Hospitals/Residents problem. We show that stable matchings can have different sizes, which motivates MAX-SPA-P, the problem of finding maximum cardinality stable matching. We prove that MAX-SPA-P is NP-hard and not approximable within delta, for some delta > 1, unless P = NP. On the other hand, we give an approximation algorithm with a performance guarantee of 2 for MAX-SPA-P. (C) 2008 Elsevier B.V. All rights reserved.
Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive "power" from at most...
详细信息
Suppose that each vertex of a graph G is either a supply vertex or a demand vertex and is assigned a positive real number, called the supply or the demand. Each demand vertex can receive "power" from at most one supply vertex through edges in G. One thus wishes to partition G into connected components by deleting edges from G so that each component C either has no supply vertex or has exactly one supply vertex whose supply is at least the sum of demands in C, and wishes to maximize the fulfillment, that is, the sum of demands in all components with supply vertices. This maximization problem is known to be NP-hard even for trees having exactly one supply vertex and strongly NP-hard for general graphs. In this paper, we focus on the approximability of the problem. We first show that the problem is MAXSNP-hard and hence there is no polynomial-time approximation scheme (PTAS) for general graphs unless P = NP. We then present a fully polynomial-time approximation scheme (FPTAS) for series-parallel graphs having exactly one supply vertex. (C) 2008 Elsevier B.V. All rights reserved.
Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S subset of V of minimal size such that every vertex in V \ S is adjacent to at least k ...
详细信息
Minimum m-connected k-dominating set problem is as follows: Given a graph G=(V,E) and two natural numbers m and k, find a subset S subset of V of minimal size such that every vertex in V \ S is adjacent to at least k vertices in S and the induced graph of S is m-connected. In this paper we study this problem with unit disc graphs and small m, which is motivated by the design of fault-tolerant virtual backbone for wireless sensor networks. We propose two approximation algorithms with constant performance ratios for m <= 2. We also discuss how to design approximation algorithms for the problem with arbitrarily large m.
We present a new multi-dimensional data structure, which we call the skip quadtree ( for point data in R-2) or the skip octree (for point data in R., with constant d > 2). Our data structure combines the best featu...
详细信息
We present a new multi-dimensional data structure, which we call the skip quadtree ( for point data in R-2) or the skip octree (for point data in R., with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined "box"-shaped regions of region quadtrees and the logarithmicheight search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.
This paper deals with an important problem of mobile communication. The objective is to place k base stations of equal range on the boundary of a convex polygonal region P such that each point inside P is covered by a...
详细信息
This paper deals with an important problem of mobile communication. The objective is to place k base stations of equal range on the boundary of a convex polygonal region P such that each point inside P is covered by at least one base station. We name this problem as region-cover(k) problem. A simplified form of this problem is the vertex-cover(k) problem, where the objective is to communicate with only the vertices of P instead of covering the entire polygon. We first present efficient algorithms for vertex-cover(2) and region-cover(2) problems, where the base stations are to be installed on a pair of specified edges. The time complexity of these algorithms are O(n log n) and O(n(2)) respectively, where n is the number of vertices in the polygon P. Next, we consider the case where k >= 3. We first concentrate on a restricted version of the vertex-cover(k) and region-cover(k) problems, where all the k base stations are to be installed on the same edge of P. Our proposed algorithm for the restricted vertex-cover(k) problem produces optimum result in O(min(n(2), nk log n)) time, whereas the algorithm for the restricted region-cover(k) problem produces an (1 + epsilon)-factor approximation result in O((n + k)log(n + k) + nlog([1/epsilon])) time. Finally, we propose efficient heuristic algorithm for the unrestricted version of the region-cover(k) problem for k >= 3. Experimental results demonstrate that our proposed algorithm runs fast and produces near optimum solutions.
We prove that a generalization of the edge dominating set problem, in which each edge e needs to be covered b(e) times for all e is an element of E, admits a linear time 2-approximation for general unweighted graphs a...
详细信息
We prove that a generalization of the edge dominating set problem, in which each edge e needs to be covered b(e) times for all e is an element of E, admits a linear time 2-approximation for general unweighted graphs and that it can be solved optimally for weighted trees. We show how to solve it optimally in linear time for unweighted trees and for weighted trees in which b(e)is an element of{0,1} for all e is an element of E. Moreover, we show that it solves generalizations of weighted matching, vertex cover, and edge cover in trees.
In this paper generalizations of Heilbronn's triangle problem to convex hulls of j points in the unit square [0,1](2) are considered. By using results on the independence number of linear hypergraphs, for fixed in...
详细信息
In this paper generalizations of Heilbronn's triangle problem to convex hulls of j points in the unit square [0,1](2) are considered. By using results on the independence number of linear hypergraphs, for fixed integers k >= 3 and any integers n >= k a deterministic o(n(6k-4)) time algorithm is given, which finds distributions of n points in [0,1](2) such that, simultaneously for j = 3,...,k, the areas of the convex hulls determined by any j of these n points are Omega((log n)(1/(j-2))/n((j-1)/(j-2))).
This paper studies the following variant of the Vehicle Routing Problem that we call the Grasp and Delivery for Moving Objects (GDMO) problem, motivated by robot navigation: The input to the problem consists of n prod...
详细信息
This paper studies the following variant of the Vehicle Routing Problem that we call the Grasp and Delivery for Moving Objects (GDMO) problem, motivated by robot navigation: The input to the problem consists of n products, each of which moves on a predefined path with a fixed constant speed, and a robot arm of capacity one. In each round, the robot arm grasps one product and then delivers it to the depot. The goal of the problem is to find a collection of tours such that the robot arm grasps and delivers as many products as possible. In this paper we prove the following results: (i) If the products move on broken lines with at least one bend, then the GDMO is MAXSNP-hard, and (ii) it can be approximated with ratio 2. However, (iii) if we impose the "straight line without bend" restriction on the motion of every product, then the GDMO becomes tractable.
暂无评论