The natural relaxation for the group Steiner tree problem, as well as for its generalization, the directed Steiner tree problem, is a flow‐based linear programming relaxation. We prove new lower bounds on the integrality ratio of this relaxation. For the group Steiner tree problem, we show that the integrality ratio is $\Omega(\log^2 k)$, where k denotes the number of groups; this holds even for input graphs that are hierarchically well‐separated trees, introduced by Bartal [in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, 1996, pp. 184–193], in which case this lower bound is tight. This also applies for the directed Steiner tree problem. In terms of the number n of vertices, our results for the directed Steiner problem imply an $\Omega(\frac{\log^2 n}{(\log \log n)^2})$ integrality ratio. For both problems, these are the first lower bounds on the integrality ratio that are superlogarithmic in the input size. This exhibits, for the first time, a relaxation of a natural optimization problem whose integrality ratio is known to be superlogarithmic but subpolynomial. Our results and techniques have been used by Halperin and Krauthgamer [in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003, pp. 585–594] to show comparable inapproximability results, assuming that NP has no quasi‐polynomial Las Vegas algorithms. We also show algorithmically that the integrality ratio for the group Steiner tree problem is much better for certain families of instances, which helps pinpoint the types of instances (parametrized by optimal solutions to their flow‐based relaxations) that appear to be most difficult to approximate.

Abstract We study two packing problems that arise in the area of dissemination‐based information systems; a second theme is the study of distributed approximation algorithms. The problems considered have the property that the space occupied by a collection of objects together could be significantly less than the sum of the sizes of the individual objects. In the Channel Allocation Problem , there are requests that are subsets of topics. There are a fixed number of channels that can carry an arbitrary number of topics. All the topics of each request must be broadcast on some channel. The load on any channel is the number of topics that are broadcast on that channel; the objective is to minimize the maximum load on any channel. We present approximation algorithms for this problem, and also show that the problem is MAX‐SNP hard. The second problem is the Edge Partitioning Problem addressed by Goldschmidt, Hochbaum, Levin, and Olinick ( Networks, 41:13–23, 2003 ). Each channel here can deliver topics for at most k requests, and we aim to minimize the total load on all channels. We present an O ( n 1/3 )–approximation algorithm, and also show that the algorithm can be made fully distributed with the same approximation guarantee; we also generalize the (nondistributed) Edge Partitioning Problem of graphs to the case of hypergraphs. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(4), 225–236 2006

Much recent work has focused on constructing efficient digital signature schemes whose security is tightly related to the hardness of some underlying cryptographic assumption. With this motivation in mind, we show here two approaches which improve both the computational efficiency and signature length of some recently-proposed schemes: Diffie-Hellman signatures. Goh and Jarecki [18] recently analyzed a signature scheme which has a tight security reduction to the computational Diffie-Hellman problem. Unfortunately, their scheme is less efficient in both computation and bandwidth than previous schemes relying on the (related) discrete logarithm assumption. We present a modification of their scheme in which signing is 33% more efficient and signatures are 75% shorter; the security of this scheme is tightly related to the decisional Diffie-Hellman problem. PSS. The...