1. Peter N. Yianilos, NEC "Sequence Comparison in Theory and Practice" We review three examples of recent theoretical work in the general area of sequence comparison that also have an applied component: i) Linear time quasi-convex bipartite matching and its relationship to intelligent text retrieval, ii) learning string edit distance costs and its application to pronunciation modeling in speech recognition, and iii) inexact context data compression and its application to DNA modeling. See: http://www.neci.nj.nec.com/homepages/pny/papers/quasi/main.html /sed/main.html /cdna/main.html for background information. 2. Ryan Martin, Rutgers University The Shannon Capacity and Ramsey Theory We will summarize some of the major results on the Shannon Capacity and review some more recent results of Alon and Orlitsky. We will show that the question of computing the Shannon capacity for any graph is a Ramsey-like problem. We will use this view to achieve some other results in the area of Shannon capacity. 3. Greg Perkins (paper in collaboration with Diane Souvaine), Rutgers University "Efficient Radio Wave Front Propagation for Wireless Radio Signal Prediction" As wireless network design and implementation is complicated, wireless network engineers increasingly depend on wireless network simulation engines. A signal-strength prediction system lies at the foundation of every wireless simulator, making signal-strength prediction for microcells and picocells an important research topic in the radio field. Efficient and accurate methods are needed for use in current wireless network design and future wireless network research. This paper describes a system, PREDICT, designed for use in wireless radio signal prediction research. PREDICT tracks the expansion of a transmitter's wavefront by modeling the wavefront as an ever expanding sphere centered upon the transmitter. The sphere's expansion is tracked by discretizing the sphere's surface with a triangulation and then propagating each triangular wavefront through the environment. In the propagation prediction of these triangular wave fronts, PREDICT supports reflection, transmission and diffraction based upon the geometric optics (GO) model of electromagnetic waves. Signal prediction is performed through summation of the predicted multi-path components at a receiver. PREDICT's algorithms have been specifically designed for use in radio signal prediction. The current environments supported by PREDICT are urban with flat or varied terrain and a single floor of a building, where all obstacles in the environment have vertical or horizontal walls. The system design is flexible, allowing PREDICT to be expanded for use in many different environments. Modularity allows for easy modification to the GO model or implementation of alternate radio modeling methods. 4. Gruia Calinescu, Rutgers University "An Improved Approximation Algorithm for MULTIWAY CUT" Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. MULTIWAY CUT is the Max SNP-Hard problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due to Dahlhaus, Johnson, Papadimitriou, Seymour, and Yannakakis gave a performance guarantee of 2(1-1/k). In this talk, we present a new linear programming relaxation for MULTIWAY CUT and an approximation algorithm based on it. The algorithm breaks the threshold of 2 for approximating MULTIWAY CUT, achieving a performance ratio of at most 1.5 - 1/k. This is joint work with Howard Karloff and Yuval Rabani. 5. Victoria Ungureanu, Rutgers University "A Mechanism for Establishing Policies for Electronic Commerce" We introduce a mechanism for establishing policies for electronic commerce in a unified and secure manner. A commercial policy can be viewed as the embodiment of a contract between the principals involved in a certain type of commercial activity, and it may be concerned with such issues as: ensuring that a payment for services is refunded under specified circumstances; preventing certificates representing e-cash from being duplicated; ensuring that credit card numbers are used only for the transaction they are intended for; and, for certain socially sensitive transactions like the purchase of drugs, ensuring auditability by proper authorities. Our mechanism is based on a previously published concept of law-governed interaction. It makes a strict separation between the formal statement of a policy, which we call a ``law,'' and the enforcement of this law, which is carried our by a set of policy-independent trusted controllers. A new policy under this scheme is created basically by formulating its law, and can be easily deployed throughout a distributed system. This mechanism enables a single agent to engage in several different activities, subject to disparate policies. 6. Xin Guo, Rutgers University "Is the market complete?: Towards a new model for the stick market" A new model of an incomplete market allowing for stochastic volatility is posed. The usual assumption that the stock price is Markovian is modified by adjoining a hidden Markov process to the Black-Scholes exponential Brownian motion model for stock fluctuations. The drift and volatility parameters take different values when the hidden Markov process is in different states. For example, it is 0 when there is no subset of the market which has or which believes it has, extra information, that is, when the market is complete. However, the hidden process is in state 1 when information is not equally shared by all, and then the behavior of the members in the subset causes increased fluctuations in the stock price. Numerical simulation and discretization of the new model are given. Corresponding optimal stopping times and option pricing procedure are discussed.Other Workshops

DIMACS Homepage

Contacting the Center

Document last modified on September 4, 1998.