On complexity of unconstrained hyperbolic 0-1 programming problems

Single- and multiple-ratio unconstrained hyperbolic 0-1 programming problems are considered. We prove that checking whether these problems have a unique solution is NP-hard. Furthermore, we show that finding the global maximizer of problems with unique solution remains NP-hard. We also discuss complexity of local search and approximability for multiple-ratio problems.     

Non-associative Lambek Categorial Grammar in Polynomial Time

We present a new axiomatization of the non-associative Lambek calculus. We prove that it takes polynomial time to reduce any non-associative Lambek categorial grammar to an equivalent context-free grammar. Since it is possible to recognize a sentence generated by a context-free grammar in polynomial time, this proves that a sentence generated by any non-associative Lambek categorial grammar can be recognized in polynomial time.     

Note on the computational complexity ofj-radii of polytopes in ℝ n

We show that, for fixed dimensionn, the approximation of inner and outerj-radii of polytopes in ℝ ⁿ , endowed with the Euclidean norm, is in ℙ. Our method is based on the standard polynomial time algorithms for solving a system of polynomial inequalities over the reals in fixed dimension.     

Coordination through De Bruijn sequences

Let (x_t) be an n-periodic sequence in which the first n elements are drawn i.i.d. according to some rational distribution. We prove there exists a constant C such that whenever mlnm?Cn, with probability close to 1, there exists an automaton of size m that matches the sequence at almost all stages.     

Complexity theory and collaboration: An agent-based simulator for a space mission design team

In this paper, we investigate how complexity theory can benefit collaboration by applying an agent-based computer simulation approach to a new form of synchronous real-time collaborative engineering design. Fieldwork was conducted with a space mission design team during their actual design sessions, to collect data on their group conversations, team interdependencies, and error monitoring and recovery practices. Based on the fieldwork analysis, an agent-based simulator was constructed. The simulation shows how error recovery and monitoring is affected by the number of small group, or sidebar, conversations, and consequent noise in the room environment. This simulation shows that it is possible to create a virtual environment with cooperating agents interacting in a dynamic environment. This simulation approach is useful for identifying the best scenarios and eliminating potential catastrophic combinations of parameters and values, where error recovery and workload in collaborative engineering design could be significantly impacted. This approach is also useful for defining strategies for integrating solutions into organizations. Narjès Bellamine-Ben Saoud is an Associate Professor at the University of Tunis and Researcher at RIADI-GDL Laboratory, Tunisia. After Computer Science engineering diploma (1993) of the ENSEEIHT of Toulouse, France, she received her PhD (1996), on groupware design applied to the study of cooperation within a space project, from the University of Toulouse I, France. Her main research interests concern studying complex systems particularly by modeling and simulating collaborative and socio-technical systems; developing Computer Supported Collaborative Learning in tunisian primary schools; and Software Engineering. Her current reserach projects include modeling and simulation of emergency rescue activities for large-scale accidents, modeling of epidemics and study of malaria, simulation of collabration artifacts. Gloria Mark is an Associate Professor in the Department of Informatics, University of California, Irvine. Dr. Mark received her Ph.D. in Psychology from Columbia University in 1991. Prior to UCI, she was a Research Scientist at the GMD, in Bonn, Germany, a visiting research scientist at the Boeing Company, and a research scientist at the Electronic Data Systems Center for Advanced Research. Dr. Mark’s research focuses on the design and evaluation of collaborative systems. Her current projects include studying worklife in the network-centric organization, multi-tasking of information workers, nomad workers, and a work in a large-scale medical collaboratory. Dr. Mark is widely published in the fields of CSCW and HCI, is currently the program co-chair for the ACM CSCW’06 conference and is on the editorial board of Computer Supported Cooperative Work: The Journal of Collaborative Computing, and e-Service Qu@rterly.     

Complexity of the min-max and min-max regret assignment problems

This paper investigates the complexity of the min-max and min-max regret assignment problems both in the discrete scenario and interval data cases. We show that these problems are strongly NP-hard for an unbounded number of scenarios. We also show that the interval data min-max regret assignment problem is strongly NP-hard.     

从事实逻辑到任务逻辑

在经典命题逻辑语言中引入附加算子几，较系统地研究近几年刚刚被提出的任务逻辑。这里把公式理解为“任务”，介绍了“任务逻辑”的语义理论，并从语构上定义形式系统L与之对应，证明该系统的可靠性、完备性及可判定性定理．最后建立系统L中的一系列基本定理。     

The inverse optimal value problem

This paper considers the following inverse optimization problem: given a linear program, a desired optimal objective value, and a set of feasible cost vectors, determine a cost vector such that the corresponding optimal objective value of the linear program is closest to the desired value. The above problem, referred here as the inverse optimal value problem, is significantly different from standard inverse optimization problems that involve determining a cost vector for a linear program such that a pre-specified solution vector is optimal. In this paper, we show that the inverse optimal value problem is NP-hard in general. We identify conditions under which the problem reduces to a concave maximization or a concave minimization problem. We provide sufficient conditions under which the associated concave minimization problem and, correspondingly, the inverse optimal value problem is polynomially solvable. For the case when the set of feasible cost vectors is polyhedral, we describe an algorithm for the inverse optimal value problem based on solving linear and bilinear programming problems. Some preliminary computational experience is reported.Mathematics Subject Classification (1999):49N45, 90C05, 90C25, 90C26, 90C31, 90C60Acknowledgement This research has been supported in part by the National Science Foundation under CAREER Award DMII-0133943. The authors thank two anonymous reviewers for valuable comments.     

On the complexity of the planar directed edge-disjoint paths problem

The edge-disjoint paths problem and many special cases of it are known to be NP-complete. We present a new NP-completeness result for a special case of the problem, namely the directed edge-disjoint paths problem restricted to planar supply graphs and demand graphs consisting of two sets of parallel edges.     

Some Properties for the Euclidean Distance Matrix and Positive Semidefinite Matrix Completion Problems

The Euclidean distance matrix (EDM) completion problem and the positive semidefinite (PSD) matrix completion problem are considered in this paper. Approaches to determine the location of a point in a linear manifold are studied, which are based on a referential coordinate set and a distance vector whose components indicate the distances from the point to other points in the set. For a given referential coordinate set and a corresponding distance vector, sufficient and necessary conditions are presented for the existence of such a point that the distance vector can be realized. The location of the point (if it exists) given by the approaches in a linear manifold is independent of the coordinate system, and is only related to the referential coordinate set and the corresponding distance vector. An interesting phenomenon about the complexity of the EDM completion problem is described. Some properties about the uniqueness and the rigidity of the conformation for solutions to the EDM and PSD completion problems are presented.