Finding optimal satisficing strategies for and-or trees

Many tasks require evaluating a specified Boolean expression φ over a set of probabilistic tests whose costs and success probabilities are each known. A strategy specifies when to perform which test, towards determining the overall outcome of φ. We are interested in finding the strategy with the minimum expected cost.As this task is typically NP-hard—for example, when tests can occur many times within φ, or when there are probabilistic correlations between the test outcomes—we consider those cases in which the tests are probabilistically independent and each appears only once in φ. In such cases, φ can be written as an and-or tree, where each internal node corresponds to either the “and” or “or” of its children, and each leaf node is a probabilistic test. In this paper we investigate “probabilistic and-or tree resolution” (PAOTR), namely the problem of finding optimal strategies for and-or trees.We first consider a depth-first approach: evaluate each penultimate rooted subtree in isolation, replace each such subtree with a single “mega-test”, and recurse on the resulting reduced tree. We show that the strategies produced by this approach are optimal for and-or trees with depth at most two but can be arbitrarily sub-optimal for deeper trees.Each depth-first strategy can be described by giving the linear relative order in which tests are to be executed, with the understanding that any test whose outcome becomes irrelevant is skipped. The class of linear strategies is strictly larger than depth-first strategies. We show that even the best linear strategy can also be arbitrarily sub-optimal.We next prove that an optimal strategy honors a natural partial order among tests with a common parent node (“leaf-sibling tests”), and use this to produce a dynamic programming algorithm that finds the optimal strategy in time O(d²d(r+1)), where r is the maximum number of leaf-siblings and d is the number of leaf-parents; hence, for trees with a bounded number of internal nodes, this run-time is polynomial in the tree size. We also present another special class of and-or trees for which this task takes polynomial time.We close by presenting a number of other plausible approaches to PAOTR, together with counterexamples to show their limitations.     

Determining the directional contact range of two convex polyhedra

The directional contact range of two convex polyhedra is the range of positions that one of the polyhedra may locate in along a given straight line so that the two polyhedra are in collision. Using the contact range, one can quickly classify the positions along a line for a polyhedron as “safe” for free of collision with another polyhedron, or “unsafe” otherwise. This kind of contact detection between two objects is important in CAD, computer graphics and robotics applications. In this paper we propose a robust and efficient computation scheme to determine the directional contact range of two polyhedra. We consider the problem in its dual equivalence by studying the Minkowski difference of the two polyhedra under a duality transformation. The algorithm requires the construction of only a subset of the faces of the Minkowski difference, and resolves the directional range efficiently. It also computes the contact configurations when the boundaries of the polyhedra are in contact.     

3D noisy discrete objects: Segmentation and application to smoothing

We propose in this paper a segmentation process that can deal with noisy discrete objects. A flexible approach considering arithmetic discrete planes with a variable width is used to avoid the over-segmentation that might happen when classical segmentation algorithms based on regular discrete planes are used to decompose the surface of the object. A method to choose a seed and different segmentation strategies according to the shape of the surface is also proposed, as well as an application to smooth the border of convex noisy discrete objects.     

Simultaneous performance achievement via compensator blending

In this paper we consider the problem of designing a state-feedback controller that simultaneously achieves different optimality criteria defined on different input-output pairs. Precisely, if r “optimal” target transfer functions are given (as the result of local “optimal” controllers), it is shown that (under mild assumptions) there exists a unique controller capable of replicating these transfer functions in the closed-loop system, so simultaneously achieving the performances inherited by the chosen local transfer functions. An explicit and constructive procedure (we refer to such procedure as “compensator blending”) is provided. The possibility of designing a stable blending compensator or the generalization to dynamic local controllers or time varying systems are also discussed. We finally consider the dual version of the problem, precisely, we show how to achieve simultaneous optimality by filter blending.     

Volume discounting coordinates a supply chain effectively when demand is sensitive to both price and sales effort

In this paper, we use a simple and parsimonious model to investigate the performance of volume discounting schemes (hereafter “[VD]”) in a supply chain where the market demand is sensitive to both retail price “p” and sales effort “e” — hereafter called a “(p,e)-channel.” The problem is analyzed as a manufacturer-leading Stackelberg game. We first present, for the deterministic-system-parameter situation, contract-designing procedures under two contract formats; namely, a “regular” version of [VD] (hereafter “[RVD]”) and a “continuous” version of [VD] (hereafter “[CVD]”). Our solutions show that [RVD] cannot perfectly coordinate this (p,e)-sensitive channel; moreover, very often [RVD] leads to a lower channel efficiency than the simple price-only contract. In contrast, we show that [CVD] leads to perfect channel coordination — a significant result since most contract formats have been shown in the literature to be unable to coordinate a (p,e)-channel. Next, we consider the more realistic situations in which the manufacturer is uncertain about one of the system parameters — specifically, either the market size “a” or the effort cost “η”. Our results show that, if Manu is uncertain about a, [RVD] becomes useless but the manufacturer can still use [CVD] to benefit himself. When the manufacturer is uncertain about η, [CVD] remains useful (as expected); however, surprisingly, [RVD] can outperform [CVD] when both the mean value and the uncertainty of η are sufficient high. These results underline the necessity of evaluating a contract format under various forms of system-parameter uncertainties — often at the expense of analytical tractability.     

The effect of an information ethics course on the information ethics values of students - A Chinese guanxi culture perspective

The development of information technology has a significant influence on social structure and norms, and also impacts upon human behavior. In order to achieve stability and social harmony, people need to respect various norms, and have their rights protected. Students’ information ethics values are of critical and radical importance in achieving this goal. Using qualitative approach, the present study utilizes Kohlberg’s CMD model to measure improvement in students’ “information ethics values” through “technology mediated learning (TML)” models, and to assess the extent to which it is influenced by gender and Chinese guanxi culture. We find that while e-learning improves female students’ “respect rules,” “privacy,” “accessibility” and “intellectual property” values more than male students, the percentages relating to “intellectual property” for females in the higher stages remain lower than for males. Moreover, these results are interpreted from a Chinese guanxi culture perspective. In light of these results, educators should take account of such improvements when designing effective teaching methods and incentives.     

A refined search tree technique for Dominating Set on planar graphs

We establish a refined search tree technique for the parameterized DOMINATING SET problem on planar graphs. Here, we are given an undirected graph and we ask for a set of at most k vertices such that every other vertex has at least one neighbor in this set. We describe algorithms with running times O(8^kn) and O(8^kk+n³), where n is the number of vertices in the graph, based on bounded search trees. We describe a set of polynomial time data-reduction rules for a more general “annotated” problem on black/white graphs that asks for a set of k vertices (black or white) that dominate all the black vertices. An intricate argument based on the Euler formula then establishes an efficient branching strategy for reduced inputs to this problem. In addition, we give a family examples showing that the bound of the branching theorem is optimal with respect to our reduction rules. Our final search tree algorithm is easy to implement; its analysis, however, is involved.     

Basing cryptographic protocols on tamper-evident seals

In this article, we attempt to formally study two very intuitive physical models: sealed envelopes and locked boxes, often used as illustrations for common cryptographic operations. We relax the security properties usually required from locked boxes [such as in bit-commitment (BC) protocols] and require only that a broken lock or torn envelope be identifiable to the original sender. Unlike the completely impregnable locked box, this functionality may be achievable in real life, where containers having this property are called “tamper-evident seals”. Another physical object with this property is the “scratch-off card”, often used in lottery tickets. We consider three variations of tamper-evident seals, and show that under some conditions they can be used to implement oblivious transfer, BC and coin flipping (CF). We also show a separation between the three models. One of our results is a strongly fair CF protocol with bias bounded by O(1/r) (where r is the number of rounds); this was a stepping stone towards achieving such a protocol in the standard model (in subsequent work).     

On ?∞, robust stability and performance with ?2 and ?∞ perturbations

In this paper we will consider systems with linear time-invariant perturbations. We will analyze robust performance in the ?₂ and ?_∞ settings. The ?₂ setting gives rise to the familiar case of structured singular values, and a stability criterion is given by the “small μ” theorem. We show that although the necessary and sufficient criterion of robust stability for the ?_∞ case (?_∞ stability with structured ?_∞-gain bounded perturbations) is the same “small μ” criterion, a system with ?₂-gain bounded perturbations is never ?_∞ stable.     

Rotation-discriminating template matching based on Fourier coefficients of radial projections with robustness to scaling and partial occlusion

We consider brightness/contrast-invariant and rotation-discriminating template matching that searches an image to analyze A for a query image Q. We propose to use the complex coefficients of the discrete Fourier transform of the radial projections to compute new rotation-invariant local features. These coefficients can be efficiently obtained via FFT. We classify templates in “stable” and “unstable” ones and argue that any local feature-based template matching may fail to find unstable templates. We extract several stable sub-templates of Q and find them in A by comparing the features. The matchings of the sub-templates are combined using the Hough transform. As the features of A are computed only once, the algorithm can find quickly many different sub-templates in A, and it is suitable for finding many query images in A, multi-scale searching and partial occlusion-robust template matching.     

Constructive linear-time temporal logic: Proof systems and Kripke semantics

In this paper we study a version of constructive linear-time temporal logic (LTL) with the “next” temporal operator. The logic is originally due to Davies, who has shown that the proof system of the logic corresponds to a type system for binding-time analysis via the Curry-Howard isomorphism. However, he did not investigate the logic itself in detail; he has proved only that the logic augmented with negation and classical reasoning is equivalent to (the “next” fragment of) the standard formulation of classical linear-time temporal logic. We give natural deduction, sequent calculus and Hilbert-style proof systems for constructive LTL with conjunction, disjunction and falsehood, and show that the sequent calculus enjoys cut elimination. Moreover, we also consider Kripke semantics and prove soundness and completeness. One distinguishing feature of this logic is that distributivity of the “next” operator over disjunction “?(A∨B)⊃?A∨?B” is rejected in view of a type-theoretic interpretation.     

Unsupervised named-entity extraction from the Web: An experimental study

The KnowItAll system aims to automate the tedious process of extracting large collections of facts (e.g., names of scientists or politicians) from the Web in an unsupervised, domain-independent, and scalable manner. The paper presents an overview of KnowItAll's novel architecture and design principles, emphasizing its distinctive ability to extract information without any hand-labeled training examples. In its first major run, KnowItAll extracted over 50,000 class instances, but suggested a challenge: How can we improve KnowItAll's recall and extraction rate without sacrificing precision?This paper presents three distinct ways to address this challenge and evaluates their performance. Pattern Learning learns domain-specific extraction rules, which enable additional extractions. Subclass Extraction automatically identifies sub-classes in order to boost recall (e.g., “chemist” and “biologist” are identified as sub-classes of “scientist”). List Extraction locates lists of class instances, learns a “wrapper” for each list, and extracts elements of each list. Since each method bootstraps from KnowItAll's domain-independent methods, the methods also obviate hand-labeled training examples. The paper reports on experiments, focused on building lists of named entities, that measure the relative efficacy of each method and demonstrate their synergy. In concert, our methods gave KnowItAll a 4-fold to 8-fold increase in recall at precision of 0.90, and discovered over 10,000 cities missing from the Tipster Gazetteer.     

Constrained stabilization via smooth Lyapunov functions

We consider the problem of stabilizing a dynamic system by means of bounded controls. We show that the largest domain of attraction can be arbitrarily closely approximated by a “smooth” domain of attraction for which we provide an analytic expression. Such an expression allows for the determination of a (non-linear) control law in explicit form.     

Resource-bounded measure on probabilistic classes

We extend Lutz's resource-bounded measure to probabilistic classes, and obtain notions of resource-bounded measure on probabilistic complexity classes such as BPE and BPEXP. Unlike former attempts, our resource bounded measure notions satisfy all three basic measure properties, that is every singleton {L} has measure zero, the whole space has measure one, and “enumerable infinite unions” of measure zero sets have measure zero.     

Complexity reduction in MPC for stochastic max-plus-linear discrete event systems by variability expansion

Model predictive control (MPC) is a popular controller design technique in the process industry. Recently, MPC has been extended to a class of discrete event systems that can be described by a model that is “linear” in the max-plus algebra. In this context both the perturbations-free case and for the case with noise and/or modeling errors in a bounded or stochastic setting have been considered. In each of these cases an optimization problem has to be solved on-line at each event step in order to determine the MPC input. This paper considers a method to reduce the computational complexity of this optimization problem, based on variability expansion. In particular, it is shown that the computational load is reduced if one decreases the level of “randomness” in the system.     

On the tractability of coloring semirandom graphs

As part of the efforts to understand the intricacies of the k-colorability problem, different distributions over k-colorable graphs have been analyzed. While the problem is notoriously hard (not even reasonably approximable) in the worst case, the average case (with respect to such distributions) often turns out to be “easy”. Semi-random models mediate between these two extremes and are more suitable to imitate “real-life” instances than purely random models. In this work we consider semi-random variants of the planted k-colorability distribution. This continues a line of research pursued by Coja-Oghlan, and by Krivelevich and Vilenchik. Our aim is to study a more general semi-random framework than those suggested so far. On the one hand we show that previous algorithmic techniques extend to our more general semi-random setting; on the other hand we give a hardness result, proving that a closely related semi-random model is intractable. Thus we provide some indication about which properties of the input distribution make the k-colorability problem hard.     

Control of discrete time nonlinear systems with a time-varying structure

In this paper, we present a control methodology for a class of discrete time nonlinear systems that depend on a possibly exogenous scheduling variable. This class of systems consists of an interpolation of nonlinear dynamic equations in strict feedback form, and it may represent systems with a time-varying nonlinear structure. Moreover, this class of systems is able to represent some cases of gain scheduling control, Takagi-Sugeno fuzzy systems, as well as input-output realizations of nonlinear systems which are approximated via localized linearizations. We present two control theorems, one using what we call a “global” approach (akin to traditional backstepping), and a “local” approach, our main result, where backstepping is again used but the control law is an interpolation of local control terms. An aircraft wing rock regulation problem with varying angle of attack is used to illustrate and compare the two approaches.     

Compositions of maximal codes

The proposition “For composable thin codes Y and Z, the composition Y°Z is maximal if and only if Y and Z are maximal” put forward by J. Berstel and D. Perrin in their book “Theory of Codes” is well known. Is the proposition also true without the assumption that Y and Z are thin? We give an example showing that the answer is negative. Furthermore, several generalizations of the above proposition are also given.