Search

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2006.06.039 Byline: H. Noltemeier, J. Spoerhase, H.-C. Wirth Keywords: Group decisions and negotiations; Facility location; Condorcet; Simpson score; Efficient graph algorithms Abstract: We examine voting location problems in which the goal is to place, based on an election amongst the users, a given number of facilities in a graph. The user preference is modeled by shortest path distances in the graph. A Condorcet solution is a set of facilities to which there does not exist an alternative set preferred by a majority of the users. Recent works generalize the model to additive indifference and replaced user majority by [gamma]-proportion. We show that for multiple voting location, Condorcet and Simpson decision problems are [SIGMA].sub.2.sup.p-complete, and investigate the approximability of the Simpson and the Simpson score optimization problem. Further we contribute a result towards lower bounds on the complexity of the single voting location problem. On the positive side we develop algorithms for the optimization problems on tree networks which are substantially faster than the existing algorithms for general graphs. Finally we suggest a generalization of the indifference notion to threshold functions. Author Affiliation: Lehrstuhl fur Informatik I, Universitat Wurzburg, Am Hubland, 97074 Wurzburg, Germany Article History: Received 20 January 2006; Accepted 30 June 2006

Abstract: An instance of the -centroid problem is given by an edge and node weighted graph. Two competitors, the leader and the follower, are allowed to place  and  facilities, respectively, into the graph. Users at the nodes connect to the closest facility. A solution of the -centroid problem is a leader placement such that the maximum total weight of the users connecting to any follower placement is as small as possible. We show that the absolute -centroid problem is NP-hard even on a path which answers a long-standing open question of the complexity of the problem on trees (Hakimi, 1990 ). Moreover, we provide polynomial time algorithms for the discrete -centroid on paths and the -centroid on trees, and complementary hardness results for more complex graph classes. [Copyright &y& Elsevier]

We study the classical  NP -hard problems of finding maximum-size subsets from given sets of  k terminal pairs that can be routed via edge-disjoint paths (MaxEDP) or node-disjoint paths (MaxNDP) in a given graph. The approximability of MaxEDP/MaxNDP is currently not well understood; the best known lower bound is  2 Ω ( log n ) , assuming  NP ⊈ DTIME ( n O ( log n ) ) . This constitutes a significant gap to the best known approximation upper bound of  O ( n ) due to Chekuri et al. (Theory Comput 2:137-146, 2006), and closing this gap is currently one of the big open problems in approximation algorithms. In their seminal paper, Raghavan and Thompson (Combinatorica 7(4):365-374, 1987) introduce the technique of randomized rounding for LPs; their technique gives an  O ( 1 ) -approximation when edges (or nodes) may be used by  O log n / log log n paths. In this paper, we strengthen the fundamental results above. We provide new bounds formulated in terms of the feedback vertex set number r of a graph, which measures its vertex deletion distance to a forest. In particular, we obtain the following results:For MaxEDP, we give an  O ( r log ( k r ) ) -approximation algorithm. Up to a logarithmic factor, our result strengthens the best known ratio  O ( n ) due to Chekuri et al., as  r ≤ n .Further, we show how to route  Ω ( OPT ∗ ) pairs with congestion bounded by  O ( log ( k r ) / log log ( k r ) ) , strengthening the bound obtained by the classic approach of Raghavan and Thompson.For MaxNDP, we give an algorithm that gives the optimal answer in time  ( k + r ) O ( r ) · n . This is a substantial improvement on the run time of  2 k r O ( r ) · n , which can be obtained via an algorithm by Scheffler. We complement these positive results by proving that MaxEDP is  NP -hard even for  r = 1 , and MaxNDP is  W [ 1 ] -hard when  r is the parameter. This shows that neither problem is fixed-parameter tractable in  r unless  FPT = W [ 1 ] and that our approximability results are relevant even for very small constant values of  r .

Scatter plots are diagrams that visualize two-dimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the x-coordinates of the points in Q by s and the y-coordinates by 1=s yields a point set P(s) that optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on real-world instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize. In conclusion, minimizing the total edge length and minimizing what we call the 'uncompactness' of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test.