5726313
Finding the shortest bottleneck edge in a parametric minimum spanning tree
<b>The result.</b> <i>Parametric optimization problems</i> that concern graphs with continuously changing edge weights have been explored by numerous researchers, with motivation ranging from sensitivity analysis to mobile-data applications. For instance, Dey [5] has shown that for an undirected graph with <i>n</i> vertices and <i>m</i> edges where the edge weights are linear functions in one parameter ("time"), the minimum spanning tree (MST) can undergo at most <i>O</i>(<i>mn</i><sup>1/3</sup>) changes (edge swaps). Agarwal <i>et al.</i> [1] have given data structures to maintain the MST over time, with a cost of <i>O</i>(<i>n</i><sup>2/3</sup> polylog <i>n</i>) per change. Fernandez-Baca <i>et al.</i> [7] have given an algorithm to compute all changes to the MST in <i>O</i>(<i>mn</i> log <i>n</i>) total time.
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.
18265362
Approximation Algorithms for Maximum Cliques in 3D Unit-Disk Graphs
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.
15997426
On levels in arrangements of curves
Analyzing the worst-case complexity of the k-level in a planar arrangement of n curves is a fundamental problem in combinatorial geometry. We give the first subquadratic upper bound (roughly O(nk/sup 1-2/3/*)) for curves that are graphs of polynomial functions of an arbitrary fixed degree s. Previously, nontrivial results were known only for the case s=1 and s=2. We also improve the earlier bound for pseudo-parabolas (curves that pairwise intersect at most twice) to O(nk/sup 7/9/log/sup 2/3/ k). The proofs are simple and rely on a theorem of Tamaki and Tokuyama on cutting pseudo-parabolas into pseudo-segments, as well as a new observation for cutting pseudo-segments into pieces that can be extended to pseudo-lines. We mention applications to parametric and kinetic minimum spanning trees.
10262363
Approximate nearest neighbor queries revisited
This paper proposes new methods to answer approximate nearest neighbor queries on a set of n points in d -dimensional Euclidean space. For any fixed constant d , a data structure with O(\(\varepsilon\) (1-d)/2 n log n) preprocessing time and O(\(\varepsilon\) (1-d)/2 log n) query time achieves an approximation factor 1+\(\varepsilon\) for any given 0 < \(\varepsilon\) < 1; a variant reduces the \(\varepsilon\) -dependence by a factor of \(\varepsilon\) -1/2 . For any arbitrary d , a data structure with O(d 2 n log n) preprocessing time and O(d 2 log n) query time achieves an approximation factor O(d 3/2 ) . Applications to various proximity problems are discussed.
15943063
Enterprise Systems Success: A Measurement Model
This paper presents a validated measurement model and instrument for assessing enterprise systems success from multiple perspectives. The final validated study model employs 27 measures of the four dimensions: information quality, system quality, individual impact, and organizational impact. The model is empirically tested with survey data gathered from 27 public sector organizations that implemented SAP R/3 in the late 1990s. The study consists of an exploratory inventory survey (model building) to identify the salient success dimensions and measures, followed by a confirmatory weights survey, for testing model validity (model testing). Test results demonstrate the discriminant validity of the four dimensions, as well as their convergence on a single higher-order phenomenon: enterprise systems success (ESS). Criterion validity testing further demonstrates the additivity of the four dimensions of success, and the completeness of the resultant overarching, second-order measure of ESS.
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.
18182246
Total variation blind deconvolution
In this paper, we present a blind deconvolution algorithm based on the total variational (TV) minimization method proposed. The motivation for regularizing with the TV norm is that it is extremely effective for recovering edges of images as well as some blurring functions, e.g., motion blur and out-of-focus blur. An alternating minimization (AM)implicit iterative scheme is devised to recover the image and simultaneously identify the point spread function (psf). Numerical results indicate that the iterative scheme is quite robust, converges very fast (especially for discontinuous blur), and both the image and the psf can be recovered under the presence of high noise level. Finally, we remark that psf's without sharp edges, e.g., Gaussian blur, can also be identified through the TV approach.
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.
15821497
An Examination Of Barriers To Benefits-realisation From Enterprise Systems In The Public Service
Examination of barriers to benefits-realisation from Enterprise Systems (ES) has potential to provide an innovative perspective on strategic management of large-scale packaged software, and on the extended virtual enterprise explicitly or implicitly deployed across the ES life-cycle. Private sector experience has revealed distinctive conditions applying to ES that create barriers to benefit-realisation. For public service organisations, ES have the potential to enable the provision of end-to-end integrated services, consistent with the demands of public accountability, but are encumbered by a poor track record in large systems implementation and associated process-reengineering. This research analyses the Australian Public Service ES experience, with the aim of dismantling barriers to public sector exploitation of ES. Early results reflect conventional perceptions of implementation issues, but application of the distinctive Dephi-based methodology designed for this study is expected to yield a basis for shared action on the part of government administration, vendors and consultants.