20186109
Balanced information inequalities
In this correspondence, we are interested in linear information inequalities, both discrete and continuous ones. We show that every discrete information inequality is associated with a "balanced" information inequality and a set of "residual weights." To prove the inequality, it is necessary and sufficient to prove that its "balanced" version is valid and all its residual weights are nonnegative. For a continuous information inequality, we prove that it is valid if and only if its discrete counterpart is balanced and valid.
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.
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.
26929194
Balanced k-colorings
Abstract While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k -coloring, for k ⩾2, a set of vertices to minimize imbalance among a family of subsets of vertices. The imbalance is the maximum, over all subsets in the family, of the largest difference between the size of any two color classes in that subset. The discrepancy is the minimum possible imbalance. We show that the discrepancy is always at most 4 d −3, where d (the “dimension”) is the maximum number of subsets containing a common vertex. For 2-colorings, the bound on the discrepancy is atmost max{2 d −3,2}. Finally, we prove that several restricted versions of computing the discrepancy are NP-complete.
6064358
Fixed-dimensional linear programming queries made easy
We derive two results from Clarkson’s randomized algorithm for linear programming in a fixed dimension d. The first is a simple general method that reduces the problem of answering linear programming queries to the problem of answering halfspace range queries. For example, this yields a randomized data structure with O(n) space and 0(nl-li[d12~ 2°f10g* ‘)) query time for linear programming on n halfspaces (d > 3). The second result is a simpler proof of the following: a sequence of q linear programming queries on n halfspaces can be answered in O (n log q) time, if q s nud for a certain const ant ad > 0. Unlike previous methods, our algorithms do not require parametric searching.
43287547
Low-dimensional linear programming with violations
Megiddo (1984) and Dyer (1984) showed that linear programming in 2 and 3 dimensions (and subsequently, any constant number of dimensions) can be solved in linear time. In this paper, we consider linear programming with at most k violations: finding a point inside all but at most k of n given halfspaces. We give a simple algorithm in 2-d that runs in O((n + k/sup 2/) log n) expected time; this is faster than earlier algorithms by Everett, Robert, and van Kreveld (1993) and Matousek (1994) and is probably near-optimal for all k /spl Lt/ n/2. A (theoretical) extension of our algorithm in 3-d runs in near O(n + k/sup 11/4/n/sup 1/4/) expected time. Interestingly; the idea is based on concave-chain decompositions (or covers) of the (/spl les/ k)-level, previously used in proving combinatorial k -level bounds. Applications in the plane include improved algorithms for finding a line that misclassifies the fewest among a set of bichromatic points, and finding the smallest circle enclosing all but k points. We also discuss related problems of finding local minima in levels.
43482019
Three problems about simple polygons
We give three related algorithmic results concerning a simple polygon P: 1. Improving a series of previous work, we show how to find a largest pair of disjoint congruent disks inside P in linear expected time. 2. As a subroutine for the above result, we show how to find the convex hull of any given subset of the vertices of P in linear worst-case time. 3. More generally, we show how to compute a triangulation of any given subset of the vertices or edges of P in almost linear time.
2540178
Balanced k-Colorings
While discrepancy theory is normally only studied in the context of 2-colorings, we explore the problem of k-coloring, for k ≥ 2, a set of vertices to minimize imbalance among a family of subsets of vertices. The imbalance is the maximum, over all subsets in the family, of the largest difference between the size of any two color classes in that subset. The discrepancy is the minimum possible imbalance. We show that the discrepancy is always at most 4d-3, where d (the "dimension") is the maximum number of subsets containing a common vertex. For 2- colorings, the bound on the discrepancy is at most max{2d-3, 2}. Finally, we prove that several restricted versions of computing the discrepancy are NP-complete.