It is well known that every stable matching instance I has a rotation poset R(I) that can be computed efficiently and the downsets of R(I) are in one-to-one correspondence with the stable matchings of I. Furthermore, for every poset P, an instance I(P) can be constructed efficiently so that the rotation poset of I(P) is isomorphic to P. In this case, we say that I(P) realizes P. Many researchers exploit the rotation poset of an instance to develop fast algorithms or to establish the hardness of stable matching problems.

The random order mechanism (ROM) can be thought of as a sequential version of Gale and Shapley's deferred-acceptance (DA) algorithm, where agents are arriving one at a time, and each newly arrived agent has an opportunity to propose. Like the DA algorithm, ROM can be implemented in polynomial time. Unlike the DA algorithm, it is possible for ROM to output a stable matching that is different from the man-optimal and woman-optimal stable matchings. We say that a stable matching $\mu$ is ROM-reachable if ROM can output $\mu$. In this paper, we investigate computational questions related to ROM-reachability. First, we prove that determining if a particular stable matching is ROM-reachable is NP-complete. However, we show that there is an efficient algorithm for determining if ROM can reach a nontrivial stable matching in the case when every agent has at least two stable partners. We then study two restricted versions of this problem. In the first version, we consider stable matchings that can be reached by ROM in a “direct” manner. We show that they are computationally easy to recognize. In the second version, we restrict the class of stable matchings to what we call extreme stable matchings and prove that the computational complexity of determining if they are ROM-reachable depends on the number of unstable partners of the agents.

For stable marriage (SM) and solvable stable roommates (SR) instances, it is known that there are stable matchings that assign each participant to his or her (lower/upper) median stable partner. Moreover, for SM instances, a stable matching has this property if and only if it is a median of the distributive lattice formed by the instance's stable matchings. In this paper, we show that the above local/global median phenomenon first observed in SM stable matchings also extends to SR stable matchings because SR stable matchings form a median graph. In the course of our investigations, we also prove that three seemingly different structures are pairwise duals of each other—median graphs give rise to mirror posets and vice versa, and mirror posets give rise to SR stable matchings and vice versa. Together, they imply that for every median graph G with n vertices, there is an SR instance $I(G)$ with $O(n^2)$ participants whose graph of stable matchings is isomorphic to G. Our results are analogous to the pairwise duality results known for distributive lattices, posets, and SM stable matchings. Interestingly, some of these results can also be inferred from the work of Feder in the early 1990s. Our constructions and proofs, however, are more natural generalizations of those used for SM instances.

A vertex k-labeling of graph G is distinguishing if the only automorphism that preserves the labels of G is the identity map. The distinguishing number of G, $D(G)$, is the smallest integer k for which G has a distinguishing k-labeling. In this paper, we apply the principle of inclusion-exclusion and develop recursive formulas to count the number of inequivalent distinguishing k-labelings of a graph. Along the way, we prove that the distinguishing number of a planar graph can be computed in time polynomial in the size of the graph.

In this paper, we describe the operation of barter trade exchanges by identifying key techniques used by trade brokers to stimulate trade and satisfy member needs, and present algorithms to automate some of these techniques. In particular, we develop algorithms that emulate the practice of trade brokers by matching buyers and sellers in such a way that trade volume is maximized while the balance of trade is maintained as much as possible. We show that the buyer/seller matching and trade balance problems can be decoupled, permitting efficient solution as well as numerous options for matching strategies.We model the trade balance problem as a minimum cost circulation problem (MCC) on a network. When the products have uniform cost or when the products can be traded in fractional units, we solve the problem exactly. Otherwise, we present a novel stochastic rounding algorithm that takes the fractional optimal solution to the trade balance problem and produces a valid integer solution. We then make use of a greedy heuristic that attempts to match buyers and sellers so that the average number of suppliers that a buyer must use to satisfy a given product need is minimized.We present results on the empirical evaluation of our algorithms on test problems and simulations. Experiments show that our algorithm (MCC + stochastic rounding) runs in a fraction of the time of a commercial mixed integer programming (MIP) package while producing solutions that are always within 0.7% of the MIP solution. We evaluate the effectiveness of our algorithm on maintaining balance and on stimulating trade using two different simulation techniques, both based on transaction history data from a trade exchange. The simulation results support the barter trade exchange rule of thumb that maximizing single-period trade volume while maintaining balance of trade helps to maximize trade volume over the long run.

Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering schemeD, itsresponse timewith respect to a queryQ,rt(Q), is defined to be the maximum number of data blocks of the query stored by the scheme in any one of the disks. If |Q| is the number of data blocks inQandMis the number of disks, thenrt(Q) is at least ⌈|Q|/M⌉. One way to evaluate the performance ofDwith respect to a set of range queries Q is to measure itsadditive error---the maximum difference ofrt(Q) from ⌈|Q|/M⌉ over all range queriesQ∈ Q.In this article, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in ad-dimensional grid so that their additive errors with respect to range queries are as small as possible. It has been shown that for a fixed dimensiond≥ 2, any declustering scheme on anMdgrid, a grid with lengthMon each dimension, will always incur an additive error with respect to range queries of Ω(logM) whend= 2 and Ω(logd−1/2M) whend> 2.Asymptotically optimal declustering schemes exist for 2-dimensional data. However, the best general upper bound known so far for the worst-case additive errors ofd-dimensional declustering schemes,d≥ 3, isO(Md−1), which is large when compared to the lower bound. In this article, we propose two declustering schemes based on low-discrepancy points ind-dimensions. Whendis fixed, both schemes have an additive error ofO(logd−1M) with respect to range queries, provided that certain conditions are satisfied: the first scheme requires that the side lengths of the grid grow at a rate polynomial inM, while the second scheme requiresd≥ 2 andM=ptwhered≤p≤C,Ca constant, andtis a positive integer such thatt(d− 1) ≥ 2. These are the first multidimensional declustering schemes with additive errors proven to be near optimal.

In the demand routing and slotting problem on unit demands (unit-DRSP), we are given a set of unit demands on an n-node ring. Each demand, which is a (source, destination) pair, must be routed clockwise or counterclockwise and assigned a slot so that no two routes that overlap occupy the same slot. The objective is to minimize the total number of slots used. It is well known that unit-DRSP is NP-complete. The best deterministic approximation algorithm guarantees a solution that is 2 × OPT. A demand of unit-DRSP can be viewed as a chord on the ring. Let w denote the size of the largest set of demand chords that mutually cross in the interior of the ring. We present a simple approximation algorithm that uses at most $(2 - 1/\lceil w/2 \rceil)\times OPT$ slots in an n-node network; this is the first deterministic approximation algorithm that beats the factor of 2 for all values of OPT and therefore for all instances of the input. If randomization is allowed, an algorithm by Kumar produces, with high probability, a solution that uses asymptotically $(1.5 + \frac{1}{2e} +o(1)) \times OPT$ slots. However, when OPT is not large enough, the factor can exceed 2. In this paper, we show how combining our algorithm with Kumar's yields a randomized approximation algorithm that has, with high probability, a constant factor of $2 - 1/\theta(\log n)$. While asymptotically it is not better than Kumar's, the approximation factor holds for all values of OPT.

Aside from enhancing data availability during disk failures, replication of data is also used to speed up I/O performance of read-intensive applications. There are two issues that need to be addressed: (a) data placement (Which disks should store the copies of each data block?) and (b) scheduling (Given a query Q, and a placement scheme P of the data, from which disk should each block in Q be retrieved so that retrieval time is minimized?) In this paper, we consider range queries and assume that the dataset is a multidimensional grid and r copies of each unit block of the grid must be stored among M disks. To accurately measure performance of a scheduling algorithm, we consider a metric that takes into account the scheduling overhead as well as the time it takes to retrieve the data blocks from the disks. We describe several combinations of data placement schemes and scheduling algorithms and analyze their performance for range queries with respect to the above metric. We then present simulation results for the most interesting case r=2, showing that the strategies do perform better than the previously known method, especially for large queries.

Declustering schemes allocate data blocks among multiple disks to enable parallel retrieval. Given a declustering scheme D, its response time with respect to a query Q, rt(Q), is defined to be the maximum number of disk blocks of the query stored by the scheme in any one of the disks. If |Q| is the number of data blocks in Q and M is the number of disks then rt(Q) is at least |Q|/M. One way to evaluate the performance of D with respect to a set of queries 𝑄 is to measure its additive error - the maximum difference between rt(Q) from |Q|/M over all range queries Q ε 𝑄.In this paper, we consider the problem of designing declustering schemes for uniform multidimensional data arranged in a d-dimensional grid so that their additive errors with respect to range queries are as small as possible. It has been shown that such declustering schemes will have an additive error of Ω(log M) when d = 2 and Ω(log d-1/2 M) when d > 2 with respect to range queries.Asymptotically optimal declustering schemes exist for 2-dimensional data. For data in larger dimensions, however, the best bound for additive errors is O(Md-1), which is extremely large. In this paper, we propose the two declustering schemes based on low discrepancy points in d-dimensions. When d is fixed, both schemes have an additive error of O(logd-1 M) with respect to range queries provided certain conditions are satisfied: the first scheme requires d ≥ 3 and M to be a power of a prime where the prime is at least d while the second scheme requires the size of the data to grow within some polynomial of M, with no restriction on M. These are the first known multidimensional declustering schemes with additive errors near optimal.

In a mobile wireless ad-hoc network, nodes move about and relay packets destined for other nodes. One of the biggest challenges in this area is the design of scalable routing protocols. A family of routing protocols has emerged that is potentially more scalable than the protocols that discover and/or maintain end-to-end routes. These protocols are location-based-the network maintains nodes' approximate geographic locations and use the information to route packets. An important component of these protocols is the management of the location information at network nodes. We present one such scheme called SLALoM which scales well in large, mobile ad-hoc networks. In particular, we prove that under a specific environment the overhead cost of SLALoM is asymptotically lower than SLURP, the only other location management scheme that has been analyzed theoretically. We also provide simulation results that show our scheme performs well in comparison to SLURP under a variety of scenarios not incorporated into the analysis.