35286842
On the NP-Isomorphism Problem with Respect to Random Instances
This paper takes a new approach to studying the NP-isomorphism problem initiated by Berman and Hartmanis. We consider polynomial-time computable and invertible bijections among NP-complete sets that preserve the underlying natural distributions on random instances. We show that there are natural NP-complete problems which are not polynomially isomorphic when instances are chosen at random because no polynomial-time isomorphisms can preserve the underlying natural distributions on instances of these problems, On the other hand, we show that all the known average-case NP-complete problems under many-one reductions are polynomially isomorphic with respect to their distributions on random instances. Simple and accessible proofs to the known average-case NP-complete problems are presented when establishing the isomorphism result. New average-case NP-complete problems are also presented.
15313247
Performance of a MAC protocol for WDM networks with on-line scheduling
This paper investigates the performance of media access protocols based on on-line scheduling for an optically connected star-coupled system with wavelength division multiple access channels. Hybrid access protocols combining reservation and pre-allocation of receiver channels have been previously proposed. Transmission consisted of a reservation phase followed by a data phase. Each node was allowed to place a reservation for one WDM channel. This protocol is extended in this paper by allowing reservations on multiple channels and using simple on-line scheduling algorithms. Existing scheduling algorithms (all are off-line) for similar reservation problems tend to have high implementation and computational complexity. We require that scheduling algorithms be real-time and amenable to hardware implementation. The performance of the extended protocol incorporating two simple on-line scheduling algorithms is presented in this paper. We show that the slight increased computational overhead with scheduling is justified by reduced packet latency and higher utilization, especially for client-server traffic.
17726002
Average-case completeness of a word problem for groups
This paper presents a bounded word problem for groups whose random instances are hard on average. The problem is to decide, when given a finitely presented group G, words ~, y, z, and an integer k, whether (Z–lyZ)Z can be obtained from Z(x–l yz) in G using elementary Tietze transformations for at most k times. We show that the problem is average-case NP-complete when instances are chosen at random under a uniform distribution. NP-completeness of more general bounded word problems for groups is shown as well.
7902129
Efficient Minimization of Numerical Summation Errors
Given a multiset X={x 1,... x n } of real numbers, the floating-point set summation (FPS) problem asks for S n = x 1+...+ x n , and the floating point prefix set summation problem (FPPS) asks for S k =x 1+...+x k for all k = 1, ... n. Let E k * denote the minimum worst-case error over all possible orderings of evaluating S k . We prove that if X has both positive and negative numbers, it is NP-hard to compute S n with the worst-case error equal to E n * . We then give the first known polynomial-time approximation algorithm for computing Sn that has a provably small error for arbitrary X. Our algorithm incurs a worstcase error at most 2([log(n−1)]+1) E n * . After X is sorted, it runs in O(n) time, yielding an O(n 2)-time approximation algorithm for computing S k for all k = 1, ..., n such that the worst-case error for each S k is less than 2(⌈ log(k−1)⌋+ 1)E k * .
32837558
On average P vs. average NP
Structures of polynomial-time computable distributions and polynomial-time many-one reductions on randomized decision problems are investigated. The scope is widened from the most studied class DNP (distributional-NP) to the class ANP (average-NP), which consists of randomized decision problems accepted by nondeterministic Turing machines in average polynomial time. Results indicate that the structures of average-case complexity classes are very different from their counterparts in worst-case complexity due to the complex structures of probability distributions and distribution functions.<<ETX>>
206565969
Immunity of Complete Problems
Abstract Two necessary and sufficient conditions for all E -complete sets to contain dense P subsets are shown. We then prove that every ≤ p m -hard for E set and its complement contain dense E ∩UP subsets. As a corollary, every NE -complete set and its complement contain dense E ∩UP subsets.
891661
Fast prefix matching of bounded strings
Longest Prefix Matching (LPM) is the problem of finding which string from a given set is the longest prefix of another, given string. LPM is a core problem in many applications, including IP routing, network data clustering, and telephone network management. These applications typically require very fast matching of bounded strings, i.e., strings that are short and based on small alphabets. We note a simple correspondence between bounded strings and natural numbers that maps prefixes to nested intervals so that computing the longest prefix matching a string is equivalent to finding the shortest interval containing its corresponding integer value. We then present retries, a fast and compact data structure for LPM on general alphabets. Performance results show that retries often outperform previously published data structures for IP look-up. By extending LPM to general alphabets, retries admit new applications that could not exploit prior LPM solutions designed for IP look-ups.
37577300
Probabilistic location problems with discrete demand weights
In this article we consider four models for locating a facility on an undirected network with demand weights, which are independent discrete random variables. These problems include the probabilistic versions of two models for locating desirable facilities: the 1-median and 1-minimax problems and two problems for locating undesirable facilities: the 1-antimedian and 1-maximin problems. The article contains analysis of special cases where a solution is determined by solving deterministic versions of the problems and efficient algorithms to solve the problems in general. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(1), 47–57 2004
7700079
On 1-Arc-regular Graphs
A graph is 1-arc-regular if its full automorphism group acts regularly on the set of its arcs. In this paper, we investigate 1-arc-regular graphs of prime valency, especially of valency 3. First, we prove that if G is a soluble group then a (G, 1)-arc-regular graph must be a Cayley graph of a subgroup of G. Next we consider trivalent Cayley graphs of a finite nonabelian simple group and obtain a sufficient condition under which one can guarantee that Cay(G, S) is 1-arc-regular. Finally, as an application of the result, we construct two infinite families of 1-arc-regular trivalent Cayley graphs with insoluble automorphism groups and, in particular, one of the families is not a Cayley graph.
22378712
Optimal management of cross-trained workers in services with negligible switching costs
In this paper we consider a retail service facility with cross-trained workers who can switch between the front room and the back room depending on the size of the queue in the front room. Two problems are presented. In the first problem, given a fixed number of cross-trained workers the objective is to find optimal switching points so that the expected customer waiting time is minimized subject to a back room service level constraint. In the second problem the number of workers is also a decision variable and the objective is to minimize it subject to both front room and back room service level constraints. The paper includes an analysis of the model and based on it several heuristics are suggested. Computational analysis with the recommended heuristics is presented and comparison to optimal solutions derived by complete enumeration shows excellent results.
19646455
The upper bound of essential cyclomatic numbers of hypergraphs
Abstract The essential cyclomatic number of a hypergraph is the maximum number of independent essential cycles of the hypergraph. In this paper, we first prove a general upper bound for the cyclomatic number in terms of the size, order and edge-size of a hypergraph. Then we give a sharp upper bound for ( n −2)-uniform hypergraphs of order n by solving an extremal problem of graphs. It is remarkable that this sharp upper bound is not generally achieved by the complete ( n −2)-uniform hypergraphs.