NPO-PB is the class of NP optimization problems with polynomially bounded values. In this paper we provide a new characterization for the class: That is, NPO-PB = MIN Σ0. This result shows that quantifiers are not relevant in characterizing approximability for minimization problems, unlike maximization problems. In proving the result, we develop a generic reduction, which combines maximization and minimization problems. Based on the new characterization, several problems are shown to be NPO-PB-complete. All of these problems are shown to be hard to approximate and tighter bounds are given.

Connectedness oriented communication denotes a mode of communication in which the activities of communication are more important than the contents of communication. It is targeted at maintaining and enhancing human social relationships. As our lifestyles and societies are shifting along with the progress of Information Technology, communication media that are connectedness oriented will play an important role. In this paper we propose a media called FaintPop, which is an example of such new media that are suitable for connectedness oriented communication. It is a communication media designed for a community, with which the sense of connectedness can be shared among members. Furthermore, it provides a general overview of the communication activities occurring in the community. We discuss several principles and points in designing the media, especially about the interaction of the users. Results and findings from the experiment using the media are reported.

As Information Technology progresses, our daily lives are getting "connected" more and more. At the same time, however, problems are appearing. The center of these problems can be captured as the "Communication Overflow. " To cope with such problems, we propose an approach that tries to provide a communication environment that assists users in managing their communication activities. The key notion of this approach is to enhance the "Awareness of Connectedness. " Here, agents which are suggestive of awareness of connectedness play an important role. In this paper, we describe the key notion and introduce a brief road-map towards the environment for the awareness of connectedness. Two candidate tools for the environment are described. The first one is a visualization tool for communication media that provides feedback of users' communication activities. Its purpose is to enhance the awareness for communication. The second tool is a simple, intuitive interactive media that exchanges the statuses of users. It is an alternative network communication media that might be suitable for very light-weight, almost-acknowledge-only communication mode. Some results on an experiment of these two tools are also reported.