Maximum <Emphasis Type="Italic">k</Emphasis>-Splittable <Emphasis Type="Italic">s</Emphasis>,<Emphasis Type="Italic">t</Emphasis>-Flows

Given a graph with a source and a sink node, the NP-hard maximum k-splittable s,t-flow (M k SF) problem is to find a flow of maximum value from s to t with a flow decomposition using at most k paths. The multicommodity variant of this problem is a natural generalization of disjoint paths and unsplittable flow problems. Constructing a k-splittable flow requires two interdepending decisions. One has to decide on k paths (routing) and on the flow values for the paths (packing). We give efficient algorithms for computing exact and approximate solutions by decoupling the two decisions into a first packing step and a second routing step. Usually the routing is considered before the packing. Our main contributions are as follows: (i) We show that for constant k a polynomial number of packing alternatives containing at least one packing used by an optimal M k SF solution can be constructed in polynomial time. If k is part of the input, we obtain a slightly weaker result. In this case we can guarantee that, for any fixed ε>0, the computed set of alternatives contains a packing used by a (1−ε)-approximate solution. The latter result is based on the observation that (1−ε)-approximate flows only require constantly many different flow values. We believe that this observation is of interest in its own right. (ii) Based on (i), we prove that, for constant k, the M k SF problem can be solved in polynomial time on graphs of bounded treewidth. If k is part of the input, this problem is still NP-hard and we present a polynomial time approximation scheme for it.     

Prioritized assertional-based removed sets revision of <Emphasis Type="Italic">DL</Emphasis>-<Emphasis Type="Italic">Lite</Emphasis> belief bases

In real world applications, information is often provided by multiple sources having different priority levels reflecting for instance their reliability. This paper investigates ”Prioritized Removed Sets Revision” (PRSR) for revising stratified DL-Lite knowledge bases when a new sure piece of information, called the input, is added. The strategy of revision is based on inconsistency minimization and consists in determining smallest subsets of assertions (prioritized removed sets) that should be dropped from the current stratified knowledge base in order to restore consistency and accept the input. We consider different forms of input: A membership assertion, a positive or a negative inclusion axiom. To characterize our revision approach, we first rephrase Hansson’s postulates for belief bases revision within a DL-Lite setting, we then give logical properties of PRSR operators. In some situations, the revision process leads to several possible revised knowledge bases where defining a selection function is required to keep results within DL-Lite fragment. The last part of the paper shows how to use the notion of hitting set in order to compute the PRSR outcome. We also study the complexity of PRSR operators, and show that, in some cases, the computational complexity of the result can be performed in polynomial time.     

Robust polynomial classifier using <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-<Emphasis Type="Italic">norm</Emphasis> minimization

In this paper we present a robust polynomial classifier based on L ¹-norm minimization. We do so by reformulating the classifier training process as a linear programming problem. Due to the inherent insensitivity of the L ¹-norm to influential observations, class models obtained via L ¹-norm minimization are much more robust than their counterparts obtained by the classical least squares minimization (L ²-norm). For validation purposes, we apply this method to two recognition problems: character recognition and sign language recognition. Both are examined under different signal to noise ratio (SNR) values of the test data. Results show that L ¹-norm minimization provides superior recognition rates over L ²-norm minimization when the training data contains influential observations especially if the test dataset is noisy.     

EP<Emphasis Type="Italic">n</Emphasis>P: An Accurate <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis>) Solution to the P<Emphasis Type="Italic">n</Emphasis>P Problem

We propose a non-iterative solution to the PnP problem—the estimation of the pose of a calibrated camera from n 3D-to-2D point correspondences—whose computational complexity grows linearly with n. This is in contrast to state-of-the-art methods that are O(n ⁵) or even O(n ⁸), without being more accurate. Our method is applicable for all n≥4 and handles properly both planar and non-planar configurations. Our central idea is to express the n 3D points as a weighted sum of four virtual control points. The problem then reduces to estimating the coordinates of these control points in the camera referential, which can be done in O(n) time by expressing these coordinates as weighted sum of the eigenvectors of a 12×12 matrix and solving a small constant number of quadratic equations to pick the right weights. Furthermore, if maximal precision is required, the output of the closed-form solution can be used to initialize a Gauss-Newton scheme, which improves accuracy with negligible amount of additional time. The advantages of our method are demonstrated by thorough testing on both synthetic and real-data.     

<Emphasis Type="Italic">I-Quest</Emphasis>: an <Emphasis Type="Italic">i</Emphasis>ntelligent <Emphasis Type="Italic">que</Emphasis>ry <Emphasis Type="Italic">st</Emphasis>ructuring based on user browsing feedback for semantic retrieval of video data

In spite of significant improvements in video data retrieval, a system has not yet been developed that can adequately respond to a user’s query. Typically, the user has to refine the query many times and view query results until eventually the expected videos are retrieved from the database. The complexity of video data and questionable query structuring by the user aggravates the retrieval process. Most previous research in this area has focused on retrieval based on low-level features. Managing imprecise queries using semantic (high-level) content is no easier than queries based on low-level features due to the absence of a proper continuous distance function. We provide a method to help users search for clips and videos of interest in video databases. The video clips are classified as interesting and uninteresting based on user browsing. The attribute values of clips are classified by commonality, presence, and frequency within each of the two groups to be used in computing the relevance of each clip to the user’s query. In this paper, we provide an intelligent query structuring system, called I-Quest, to rank clips based on user browsing feedback, where a template generation from the set of interesting and uninteresting sets is impossible or yields poor results.

Corepresentation of a sylow <Emphasis Type="Italic">p</Emphasis>-subgroup of a group <Emphasis Type="Italic">S</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

The corepresentation of a Sylow p-subgroup of a symmetric group in the form of generating relations is investigated, and a Sylow subgroup of a group , i.e., an n-fold wreath product of regular cyclic groups of prime order, that is isomorphic to the group of automorphisms of a spherically homogeneous root tree is also studied. Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 27–41, January–February 2009.     

Intuitionistic (<Emphasis Type="Italic">S</Emphasis>, <Emphasis Type="Italic">T</Emphasis>)-fuzzy hyperquasigroups

The concept of intuitionistic fuzzy subhyperquasigroups in a hyperquasigroup with respect to an s-norm and a t-norm on intuitionistic fuzzy sets is introduced and their properties of such hyperquasigroups are studied. Intuitionistic (S, T)-fuzzy relations on a hyperquasigroup G are discussed. In particular, we investigate connections hyperquasigroups with binary quasigroups.     

3D virtual mosaics: <Emphasis Type="Italic">Opus Palladium</Emphasis> and <Emphasis Type="Italic">mixed</Emphasis> styles

One of the oldest art forms, mosaics are built by careful selection and placement of small pieces called tiles. Although 2D mosaics have attracted attention in computer graphics research, 3D virtual mosaic sculptures are less common. In this work, we present a method to simulate mosaic sculptures using tiles with irregular shapes, a method known by mosaicists as Opus Palladium, or simply “crazy paving,” due to the inherent freedom of mixing the tiles. In order to add expressiveness and emphasize some features, artists distribute the tiles following a high-level design over the shape. We use Voronoi polygons to represent the tiles computed from a distribution of points on the surface of the 3D object. We also address the simulation of mixed mosaics, where both irregular and squared-shape tiles are used on the same object. Previous works on such surface mosaics have used only square-shaped tiles, with fixed or variable size. Special mosaic-like effects are obtained with the help from texture maps, which control the high-level design of the tile distribution.     

Low-density incomplete <Emphasis Type="Italic">LDL</Emphasis><Superscript><Emphasis Type="Italic">T</Emphasis></Superscript> factorizations

A particular class of incomplete factorizations is proposed as preconditioners for the linear system Ax = b where A is a symmetric, large and sparse matrix. The ILDL ^T< (p) factorization (p = 1,2,3, …) determines the density of the lower triangular matrix L selecting the p largest off-diagonal entries of each column during the Gaussian elimination process. This selection may be computationally expensive, but the effectiveness of the preconditioner allows us to choose very low-density factors to reduce both work time and storage requirements. This incomplete factorization can be performed reliably on H-matrices. When A is a positive definite matrix, but not an H-matrix, one can perform an incomplete factorization if positive off-diagonal entries are removed or reduced and diagonally compensated. Numerical results for a variety of problems and comparisons with other incomplete factorizations are presented. Received: August 2002 / Accepted: December 2002 RID="*" ID="*"This work was supported by the Spanish grant BFM 2001-2641.     

I—SATCHMORE：An Improvement of A—SATCHMORE

This paper presents an improvement of A-SATCHMORE (SATCHMORE with Availability).A-SATCHMORE incorporates relevancy testing and availability checking into SATCHMO to prune away irrelevant forward chaining.However ,considering every consequent atom of those non-Horn clauses being derivable,A-SATCHMORE may suffer from a potential explosion of the search space when some of such consequent atoms are actually underivable.This paper introduces a solution for this problem and shows its correctness.     

The servicing system <Emphasis Type="Italic">MAP</Emphasis>(<Emphasis Type="Italic">PH</Emphasis>)+<Emphasis Type="Italic">MAP/PH/N/R</Emphasis> as a model of optimizing an <Emphasis Type="Italic">HTTP</Emphasis> server with blockings

We consider a multiline queueing system with joint or single queries. The number of queries in a connection is random and is not known when the connection is established. Queries arriving during each connection are described by the phase type input steam. Accepting a connection in the system is restricted by tokens. Connections arriving when no free tokens are present are refused. Single queries arrive without tokens. If the number of free slots in the system is not enough, the system is blocked.     

On the <Emphasis Type="Italic">k</Emphasis>-accessibility of cores of <Emphasis Type="Italic">TU</Emphasis>-cooperative games

This paper proposes a strengthening of the author’s core-accessibility theorem for balanced TU-cooperative games. The obtained strengthening relaxes the influence of the nontransitivity of classical domination αv on the quality of the sequential improvement of dominated imputations in a game v. More specifically, we establish the k-accessibility of the core C(α _v ) of any balanced TU-cooperative game v for all natural numbers k: for each dominated imputation x, there exists a converging sequence of imputations x₀, x₁,..., such that x₀ = x, lim x _r ∈ C(α _v ) and x_r?m is dominated by any successive imputation x _r with m ∈ [1, k] and r ≥ m. For showing that the TU-property is essential to provide the k-accessibility of the core, we give an example of an NTU-cooperative game G with a ”black hole” representing a nonempty closed subset B ? G(N) of dominated imputations that contains all the α _G -monotonic sequential improvement trajectories originating at any point x ∈ B.     

Extension of <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis> log <Emphasis Type="Italic">n</Emphasis>) Filtering Algorithms for the Unary Resource Constraint to Optional Activities

Scheduling is one of the most successful application areas of constraint programming mainly thanks to special global constraints designed to model resource restrictions. Among these global constraints, edge-finding and not-first/not-last are the most popular filtering algorithms for unary resources. In this paper we introduce new O(n log n) versions of these two filtering algorithms and one more O(n log n) filtering algorithm called detectable precedences. These algorithms use a special data structures Θ-tree and Θ-Λ-tree. These data structures are especially designed for “what-if” reasoning about a set of activities so we also propose to use them for handling so called optional activities, i.e. activities which may or may not appear on the resource. In particular, we propose new O(n log n) variants of filtering algorithms which are able to handle optional activities: overload checking, detectable precedences and not-first/not-last.     

Emergence of anti-<Emphasis Type="Italic">F</Emphasis>(<Emphasis Type="Italic">R</Emphasis>) gravity in type-IV bouncing cosmology as due to <Emphasis Type="Italic">M</Emphasis><Subscript>0</Subscript>-brane

Recently, some authors considered the origin of a type-IV singular bounce in modified gravity and obtained the explicit form of F(R) which can produce this type of cosmology. In this paper, we show that during the contracting branch of type-IV bouncing cosmology, the sign of gravity changes, and antigravity emerges. In our model, M0 branes get together and shape a universe, an anti-universe, and a wormhole which connects them. As time passes, this wormhole is dissolved in the universes, F(R) gravity emerges, and the universe expands. When the brane universes become close to each other, the squared energy of their system becomes negative, and some tachyonic states are produced. To remove these states, universes are assumed to be compact, the sign of compacted gravity changes, and anti-F(R) gravity arises, which causes getting away of the universes from each other. In this theory, a Type-IV singularity occurs at t = t _s , which is the time of producing tachyons between expansion and contraction branches.     

Symmetric Masks for In-fill Pixel Interpolation on Discrete <Emphasis Type="Italic">p</Emphasis>:<Emphasis Type="Italic">q</Emphasis> Lattices

A 2D p:q lattice contains image intensity entries at pixels located at regular, staggered intervals that are spaced p rows and q columns apart. Zero values appear at all other intermediate grid locations. We consider here the construction, for any given p:q, of convolution masks to smoothly and uniformly interpolate values across all of the intermediate grid positions. The conventional pixel-filling approach is to allocate intensities proportional to the fractional area that each grid pixel occupies inside the boundaries formed by the p:q lines. However, these area-based masks have asymmetric boundaries, flat interior values and may be odd or even in size. Where edges, lines or points are in-filled, area-based p:q masks imprint intensity patterns that recall p:q because the shape of those masks is asymmetric and depends on p:q. We aim to remove these “memory” artefacts by building symmetric p:q masks. We show here that smoother, symmetric versions of such convolution masks exist. The coefficients of the masks constructed here have simple integer values whose distribution is derived purely from symmetry considerations. We have application for these symmetric interpolation masks as part of a precise image rotation algorithm which disguises the rotation angle, as well as to smooth back-projected values when performing discrete tomographic image reconstruction.     

The <Emphasis Type="Italic">MAP</Emphasis> + <Emphasis Type="Italic">MAP/PH</Emphasis>/1/<Emphasis Type="Italic">N</Emphasis> queuing system with single and batch arrivals of customers

The single-server queuing system with finite buffer was considered. The customers may arrive one-by-one or in batches. Arrivals of single customers and their batches obey the Markov input processes. The customers from a batch taken for servicing come one at a time at the exponentially distributed time intervals. The numbers of customers in batches are distributed geometrically. The time of customer servicing has a phase-type distribution. The numbers of batches and single customers that may be simultaneously accepted by the system are controllable parameters. The joint distribution of the number of batches and the number of customers in system, loss probabilities, distribution of the time of batch sojourn, and problems of optimization were analyzed.     

The <Emphasis Type="Italic">POINT</Emphasis> approach to represent <Emphasis Type="Italic">now</Emphasis> in bitemporal databases

Most modern database applications involve a significant amount of time dependent data and a significant portion of this data is now-relative. Now-relative data are a natural and meaningful part of every temporal database as well as being the focus of most queries. Previous studies indicate that the choice of the representation of now significantly influences the efficiency of accessing bitemporal data. In this paper we propose and experimentally evaluate a novel approach to represent now that we termed the POINT approach, in which now-relative facts are represented as points on the transaction-time and/or valid-time line. Furthermore, in the POINT approach we propose a logical query transformation that relies on the above representation and on the geometry features of spatial access methods. Such a logical query transformation enables off-the-shelf spatial indexes to be used. We empirically prove that the POINT approach is efficient on now-relative bitemporal data, outperforming the maximum timestamp approach that has been proven to the best approach to now-relative data in the literature, independently of the indexing methodology (B ⁺- tree vs R ^*- tree) being used. Specifically, if spatial indexing is used, the POINT approach outperforms the maximum timestamp approach to the extent of factor more than 10, both in number of disk accesses and CPU usage.     

On <Emphasis Type="Italic">m</Emphasis>-Near-Resolvable Block Designs and <Emphasis Type="Italic">q</Emphasis>-ary Constant-Weight Codes

We introduce m-near-resolvable block designs. We establish a correspondence between such block designs and a subclass of (optimal equidistant) q-ary constant-weight codes meeting the Johnson bound. We present constructions of m-near-resolvable block designs, in particular based on Steiner systems and super-simple t-designs.     

Notes on wormhole existence in scalar-tensor and <Emphasis Type="Italic">F</Emphasis>(<Emphasis Type="Italic">R</Emphasis>) gravity

Some recent papers have claimed the existence of static, spherically symmetric wormhole solutions to gravitational field equations in the absence of ghost (or phantom) degrees of freedom. We show that in some such cases the solutions in question are actually not of wormhole nature while in cases where a wormhole is obtained, the effective gravitational constant G _eff is negative in some region of space, i.e., the graviton becomes a ghost. In particular, it is confirmed that there are no vacuum wormhole solutions of the Brans-Dicke theory with zero potential and the coupling constant ω > −3/2, except for the case ω = 0; in the latter case, G _eff < 0 in the region beyond the throat. The same is true for wormhole solutions of F(R) gravity: special wormhole solutions are only possible if F(R) contains an extremum at which G _eff changes its sign.