Fiberings with Fiber RP(k)

Let k be non–negative integer. The unoriented bordism classes, which can be represented as [RP(ξ ^k )] where ξ ^k is a k–plane bundle, form an ideal of the unoriented bordism ring MO_*. A group of generators of this ideal expressed by a base of MO_* and a necessary and sufficient condition for a bordism class to belong to this ideal are given. This work is supported by HNSF (Grant No: 103144) and NNSF of China (10371029)     

A new upper bound on the cyclic chromatic number

A cyclic coloring of a plane graph is a vertex coloring such that vertices incident with the same face have distinct colors. The minimum number of colors in a cyclic coloring of a graph is its cyclic chromatic number χ^c. Let Δ^* be the maximum face degree of a graph. There exist plane graphs with χ^c = ?3/2 Δ^*?. Ore and Plummer [ 5 ] proved that χ^c ≤ 2, Δ^*, which bound was improved to ?9/5, Δ^*? by Borodin, Sanders, and Zhao [ 1 ], and to ?5/3,Δ^*? by Sanders and Zhao [ 7 ]. We introduce a new parameter k^*, which is the maximum number of vertices that two faces of a graph can have in common, and prove that χ^c ≤ max {Δ^* + 3,k^* + 2, Δ^* + 14, 3, k^* + 6, 18}, and if Δ^* ≥ 4 and k^* ≥ 4, then χ^c ≤ Δ^* + 3,k^* + 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Diffusion approximation forGI/G/1 controlled queues

A queueing model is considered in which a controller can increase the service rate. There is a holding cost represented by functionh and the service cost proportional to the increased rate with coefficientl. The objective is to minimize the total expected discounted cost.Whenh andl are small and the system operates in heavy traffic, the control problem can be approximated by a singular stochastic control problem for the Brownian motion, namely, the so-called reflected follower problem. The optimal policy in this problem is characterized by a single numberz ^* so that the optimal process is a reflected diffusion in [0,z ^*]. To obtainz ^* one needs to solve a free boundary problem for the second order ordinary differential equation. For the original problem the policy which increases to the maximum the service rate when the normalized queue-length exceedsz ^* is approximately optimal.     

Waiting time approximation in single-class queueing systems with multiple types of interruptions: modeling congestion at waterways entrances

We consider a single-server queue subject to multiple types of operation-independent interruptions motivated by operations and vessel queueing at entrances of waterways. A case in point is the Strait of Istanbul. We are using waiting-time arguments and service completion time analysis to obtain the expected waiting time of a customer (vessel) in the aforementioned queue with single-class of customers and k non-simultaneous and possibly simultaneous service interruptions. In the analysis, we have used arguments and assumptions from the Strait of Istanbul that are also valid for narrow waterways at large.     

Approximation algorithms for projective clustering

We consider the following two instances of the projective clustering problem: Given a set S of n points in and an integer k>0, cover S by k slabs (respectively d-cylinders) so that the maximum width of a slab (respectively the maximum diameter of a d-cylinder) is minimized. Let w^* be the smallest value so that S can be covered by k slabs (respectively d-cylinders), each of width (respectively diameter) at most w^*. This paper contains three main results: (i) For d=2, we present a randomized algorithm that computes O(klogk) strips of width at most w^* that cover S. Its expected running time is O(nk²log⁴n) if k²logkn; for larger values of k, the expected running time is O(n^2/3k^8/3log^14/3n). (ii) For d=3, a cover of S by O(klogk) slabs of width at most w^* can be computed in expected time O(n^3/2k^9/4polylog(n)). (iii) We compute a cover of by O(dklogk) d-cylinders of diameter at most 8w^* in expected time O(dnk³log⁴n). We also present a few extensions of this result.     

On locally graded groups with an Engel condition on infinite subsets

A group G is said to be in E_k^*E_k^* (k a positive integer), if every infinite subset of G contains a pair of elements that generate a k-Engel group.¶It is shown that a finitely generated locally graded group G in E_k^*E_k^* is a finite-by- (k-Engel) group, in particular a finite extension of a k-Engel group.     

Speeding up the Dreyfus–Wagner algorithm for minimum Steiner trees

The Dreyfus–Wagner algorithm is a well-known dynamic programming method for computing minimum Steiner trees in general weighted graphs in time O ^*(3 ^k ), where k is the number of terminal nodes to be connected. We improve its running time to O ^*(2.684 ^k ) by showing that the optimum Steiner tree T can be partitioned into T = T ₁∪ T ₂ ∪ T ₃ in a certain way such that each T _i is a minimum Steiner tree in a suitable contracted graph G _i with less than terminals. In the rectilinear case, there exists a variant of the dynamic programming method that runs in O ^*(2.386 ^k ). In this case, our splitting technique yields an improvement to O ^*(2.335 ^k ).     

Existence of T*(3, 4,v)‐codes

A word of length k over an alphabet Q of size v is a vector of length k with coordinates taken from Q. Let Q^*₄ be the set of all words of length 4 over Q. A T^*(3, 4, v)‐code over Q is a subset C^*? Q^*₄ such that every word of length 3 over Q occurs as a subword in exactly one word of C^*. Levenshtein has proved that a T^*(3, 4, vv)‐code exists for all even v. In this paper, the notion of a generalized candelabra t‐system is introduced and used to show that a T^*(3, 4, v)‐code exists for all odd v. Combining this with Levenshtein's result, the existence problem for a T^*(3,4, v)‐code is solved completely. © 2004 Wiley Periodicals, Inc. J Combin Designs 13: 42–53, 2005.     

A large neighborhood search heuristic for the longest common subsequence problem

Given a set S={S ¹,…,S ^k } of finite strings, the k-Longest Common Subsequence Problem (k-LCSP) seeks a string L ^* of maximum length such that L ^* is a subsequence of each S ⁱ for i=1,…,k. This paper presents a large neighborhood search technique that provides quality solutions to large k-LCSP instances. This heuristic runs in linear time in both the length of the sequences and the number of sequences. Some computational results are provided.     

Integer Optimization on Convex Semialgebraic Sets

Let Y be a convex set in \Re ^k defined by polynomial inequalities and equations of degree at most d ≥ 2 with integer coefficients of binary length at most l . We show that if the set of optimal solutions of the integer programming problem min is not empty, then the problem has an optimal solution of binary length ld ^O(k4) . For fixed k , our bound implies a polynomial-time algorithm for computing an optimal integral solution y ^* . In particular, we extend Lenstra's theorem on the polynomial-time solvability of linear integer programming in fixed dimension to semidefinite integer programming. Received August 3, 1998, and in revised form March 22, 1999.     

A Combinatorial Construction for Perfect Deletion-Correcting Codes

By a T ^*(2, k, v)-code we mean a perfect(k-2)-deletion-correcting code of length k over an alphabet ofsize v, which is capable of correcting any combination of up to(k-2) deletions and insertions of letters occured in transmission ofcodewords. In this paper, we provide a combinatorial construction forT ^*(2, k, v-codes. As an application, we show that aT ^*(2, 6, v-code exists for all positive integersv 3 (mod 5), with at most 12 possible exceptions of v. In theprocedure, a result on incomplete directed BIBDs is also established which is ofinterest in its own right.     

On polynomial solvability of some problems of a vector subset choice in a Euclidean space of fixed dimension

The problems under study are connected with the choice of a vector subset from a given finite set of vectors in the Euclidean space ℝ ^k . The sum norm and averaged square of the sumnorm are considered as the target functions (to be maximized). The optimal combinatorial algorithms with time complexity O(k ² n ^2k ) are developed for these problems. Thus, the polynomial solvability of these problems is proved for k fixed.     

Optimal attitude control of a rigid body

Being mainly interested in the control of satellites, we investigate the problem of maneuvering a rigid body from a given initial attitude to a desired final attitude at a specified end time in such a way that a cost functional measuring the overall angular velocity is minimized.This problem is solved by applying a recent technique of Jurdjevic in geometric control theory. Essentially, this technique is just the classical calculus of variations approach to optimal control problems without control constraints, but formulated for control problems on arbitrary manifolds and presented in coordinate-free language. We model the state evolution as a differential equation on the nonlinear state spaceG=SO(3), thereby completely circumventing the inevitable difficulties (singularities and ambiguities) associated with the use of parameters such as Euler angles or quaternions. The angular velocities _k about the body's principal axes are used as (unbounded) control variables. Applying Pontryagin's Maximum Principle, we lift any optimal trajectorytg^*(t) to a trajectory onT ^*G which is then revealed as an integral curve of a certain time-invariant Hamiltonian vector field. Next, the calculus of Poisson brackets is applied to derive a system of differential equations for the optimal angular velocitiest _k ^* (t); once these are known the controlling torques which need to be applied are determined by Euler's equations.In special cases an analytical solution in closed form can be obtained. In general, the unknown initial values _k ^* (t₀) can be found by a shooting procedure which is numerically much less delicate than the straightforward transformation of the optimization problem into a two-point boundary-value problem. In fact, our approach completely avoids the explicit introduction of costate (or adjoint) variables and yields a differential equation for the control variables rather than one for the adjoint variables. This has the consequence that only variables with a clear physical significance (namely angular velocities) are involved for which gooda priori estimates of the initial values are available.     

Lifting orthogonal representations to spin groups and local root numbers

Representations ofD _k ^* k ^* for a quaternion division algebraD _k over a local fieldk are orthogonal representations. In this note we investigate when these orthogonal representations can be lifted to the corresponding spin group. The results are expressed in terms of local root number of the representation.     

Worst-case time bounds for coloring and satisfiability problems

We consider worst case time bounds for certain NP-complete problems. In particular, we consider the (k,2)-satisfiability problem which includes as special cases some canonical problems such as graph coloring and satisfiability. For the (k,2)-satisfiability problem, we present a randomized algorithm that runs in time O^*((k!)^n/k).² This bound is equivalent to O((k/c_k)ⁿ) with c_k increasing to the asymptotic limit e. For k11, we improve upon the O((0.4518k)ⁿ) randomized bound of Eppstein [Proceedings of the 12th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 329–337]. A special case of (k,2)-satisfiability is k-colorability; here we achieve the above time bound for a slightly larger c_k that has the same asymptotic behavior.     

Sojourn time analysis for a cyclic-service tandem queueing model with general decrementing service

A sojourn time analysis is provided for a cyclic-service tandem queue with general decrementing service which operates as follows: starting once a service of queue 1 in the first stage, a single server continues serving messages in queue 1 until either queue 1 becomes empty, or the number of messages decreases to k less than that found upon the server's last arrival at queue 1, whichever occurs first, where 1 ≤ k ≤ ∞. After service completion in queue 1, the server switches over to queue 2 in the second stage and serves all messages in queue 2 until it becomes empty. It is assumed that an arrival stream is Poissonian, message service times at each stage are generally distributed and switch-over times are zero. This paper analyzes joint queue-length distributions and message sojourn time distributions.     

Cohomologie de Hochschild et espaces projectifs tronqués

In this paper, we outline the construction of obstructions tok-formality wherek is a field of arbitrary characteristic. We show that the obstructions to intrinsick-formality of a graded algebraH ^* lie in the Hochschild cohomologyH H ^m,1 (H ^*/k, H ^*). We calculate explicitly the Hochschild cohomology of the algebraH(ℂP ^∞/ℂP ⁿ ;k) and deduce that the stunted complex projective space ℂP ^∞/ℂP ⁿ is intrinsicallyk-formal for any fieldk.

---

---

This article was processed by the author using the LATEX style filecljour1 from Springer-Verlag.     

On the separation of maximally violated mod-k cuts

Separation is of fundamental importance in cutting-plane based techniques for Integer Linear Programming (ILP). In recent decades, a considerable research effort has been devoted to the definition of effective separation procedures for families of well-structured cuts. In this paper we address the separation of Chvátal rank-1 inequalities in the context of general ILP’s of the form min{c ^T x:Ax≤b,x integer}, where A is an m×n integer matrix and b an m-dimensional integer vector. In particular, for any given integer k we study mod-k cuts of the form λ ^T Ax≤⌊λ ^T b⌋ for any λ∈{0,1/k,...,(k−1)/k} ^m such that λ ^T A is integer. Following the line of research recently proposed for mod-2 cuts by Applegate, Bixby, Chvátal and Cook [1] and Fleischer and Tardos [19], we restrict to maximally violated cuts, i.e., to inequalities which are violated by (k−1)/k by the given fractional point. We show that, for any given k, such a separation requires O(mn min{m,n}) time. Applications to both the symmetric and asymmetric TSP are discussed. In particular, for any given k, we propose an O(|V|²|E ^*|)-time exact separation algorithm for mod-k cuts which are maximally violated by a given fractional (symmetric or asymmetric) TSP solution with support graph G ^*=(V,E ^*). This implies that we can identify a maximally violated cut for the symmetric TSP whenever a maximally violated (extended) comb inequality exists. Finally, facet-defining mod-k cuts for the symmetric and asymmetric TSP are studied. Received May 29, 1997 / Revised version received May 10, 1999?Published online November 9, 1999     

Optimal buffer size for a stochastic processing network in heavy traffic

We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b ^*>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b ^*>0. A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.