6323270
Capacity-achieving probability measure for conditionally Gaussian channels with bounded inputs
A conditionally Gaussian channel is a vector channel in which the channel output, given the channel input, has a Gaussian distribution with (well-behaved) input-dependent mean and covariance. We study the capacity-achieving probability measure for conditionally Gaussian channels subject to bounded-input constraints and average cost constraints. Many practical communication systems, including additive Gaussian noise channels, certain optical channels, fading channels, and interference channels fall within this framework. Subject to bounded-input constraint (and average cost constraints), we show that the channel capacity is achievable and we derive a necessary and sufficient condition for a probability measure to be capacity achieving. Under certain conditions, the capacity-achieving measure is proved to be discrete.
15993467
On a relation between information inequalities and group theory
We establish a one-to-one correspondence between information inequalities and group inequalities. The major implication of our result is that we can prove information inequalities by proving the corresponding group inequalities, and vice versa. By giving a group-theoretic proof for all Shannon-type inequalities, we suggest that new inequalities could be discovered by making use of the rich set of tools in group theory. On the other hand, via a non-Shannon-type information inequality discovered by Zhang and Yeung (1997), we obtain a new inequality in group theory whose meaning is yet to be understood.
16750516
Spanners with Slack
Given a metric (V,d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion. In this paper, we study the problem of spanners with slack: e.g., can we find sparse spanners where we are allowed to incur an arbitrarily large distortion on a small constant fraction of the distances, but are then required to incur only a constant (independent of n) distortion on the remaining distances? We answer this question in the affirmative, thus complementing similar recent results on embeddings with slack into l p spaces. For instance, we show that if we ignore an e fraction of the distances, we can get spanners with O(n) edges and O(log 1 ∈) distortion for the remaining distances. We also show how to obtain sparse and low-weight spanners with slack from existing constructions of conventional spanners, and these techniques allow us to also obtain the best known results for distance oracles and distance labelings with slack. This paper complements similar results obtained in recent research on slack embeddings into normed metric spaces.
6808464
Geometric applications of a randomized optimization technique
We propose a simple, general, randomized technique to reduce certain geo- metric optimization problems to their corresponding decision problems. These reductions increase the expected time complexity by only a constant factor and eliminate extra log- arithmic factors in previous, often more complicated, deterministic approaches (such as parametric searching). Faster algorithms are thus obtained for a variety of problems in computational geometry: finding minimal k-point subsets, matching point sets under trans- lation, computing rectilinear p-centers and discrete 1-centers, and solving linear programs with k violations.
2808758
Towards in-place geometric algorithms and data structures
For many geometric problems, there are efficient algorithms that surprisingly use very little extra space other than the given array holding the input. For many geometric query problems, there are efficient data structures that need no extra space at all other than an array holding a permutation of the input. In this paper, we obtain the first such space-economical solutions for a number of fundamental problems, including three-dimensional convex hulls, two-dimensional Delaunay triangulations, fixed-dimensional range queries, and fixed-dimensional nearest neighbor queries.
10486597
A fully dynamic algorithm for planar
We show how to maintain the width of a set of $n$ planar points subjec t to insertions and deletions of points in $O(\sqrt{n}\log^3n)$ amortized time per update. Previously, no fully dynamic algorithm with a guaranteed sublinear time bound was known.
32811638
Timing of Software Replacement
Analogous to the replacement of an old machine, such as a car, replacing an aged softwitre may contain its escalating cost of maintenance. Prior research has assumed that increasing maintenance cost is due to the deterioration of the system maintainability. However, cost of maintenance depends also on the number of incoming maintenance requests. While software maintainability is determined by its complexity and development environment, number of maintenance requests is affected by the business environment. This distinction is significant in analyzing economic tradeoffs in software maintenance because replacement improves system maintainability but will not affect the number of maintenance requests. Unlike replacement of hardware, rewriting software takes an extended length of time, Thus, the old software must still be maintained before the new software is ready. We develop an economic model that considers the number of maintenance requests and the rewriting period explicitly. The model is an extension of Gode, Barua, and Mukhopadhyay (1990), which assumes a constant number of maintenance requests and instantaneous replacement. Our model allows us to draw some additional policy implications about software inaintenatice aild replacement. For instance, we show that in certain situations delaying a system replacement can be inore cost effective when the user environment changes more rapidly, contrary to our intuition. Moreover, it is shown that rewriting should begin earlier when the instantane(,us replacement assumption is relaxed.