Decomposition of Multiple Coverings into More Parts

We prove that for every centrally symmetric convex polygon Q, there exists a constant α such that any locally finite α k-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Tóth. The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.     

A real delivery problem dealt with Monte Carlo Techniques

In this paper we use Monte Carlo Techniques to deal with a real world delivery problem of a food company in Valencia (Spain). The problem is modeled as a set of 11 instances of the well known Vehicle Routing Problem, VRP, with additional time constraints. Given that VRP is a NP-hard problem, a heuristic algorithm, based on Monte Carlo techniques, is implemented. The solution proposed by this heuristic algorithm reaches distance and money savings of about 20% and 5% respectively. This work has been partially supported by thePlan de Incentivo a la Investigación/98 of the Universidad Politécnica de Valencia, under the project “Técnicas Monte Carlo aplicadas a Problemas de Rutas de Vehículos”.     

Generating,scheduling and rostering of shift crew-duties: Applications at the Hong Kong International Airport

In the context of manpower planning, goal programming (GP) is extremely useful for generating shift duties of fixed length. A fixed-length duty consists of a fixed number of contiguous hours of work in a day, with a meal/rest break somewhere preferably around the middle of these working hours. It is such properties that enable the straightforward, yet flexible GP modeling. We propose GP models for an integrated problem of crew duties assignment, for baggage services section staff at the Hong Kong International Airport. The problem is solved via decomposition into its duties generating phase—a GP planner, followed by its GP scheduling and rostering phase. The results can be adopted as a good crew schedule in the sense that it is both feasible, satisfying various work conditions, and “optimal” in minimizing idle shifts.     

Dynamic journeying under uncertainty

We introduce a journey planning problem in multi-modal transportation networks under uncertainty. The goal is to find a journey, possibly involving transfers between different transport services, from a given origin to a given destination within a specified time horizon. Due to uncertainty in travel times, the arrival times of transport services at public transport stops are modeled as random variables. If a transfer between two services is rendered unsuccessful, the commuter has to reconsider the remaining path to the destination. The problem is modeled as a Markov decision process in which states are defined as paths in the transport network. The main contribution is a backward induction method that generates an optimal policy for traversing the public transport network in terms of maximizing the probability of reaching the destination in time. By assuming history independence and independence of successful transfers between services we obtain approximate methods for the same problem. Analysis and numerical experiments suggest that while solving the path dependent model requires the enumeration of all paths from the origin to the destination, the proposed approximations may be useful for practical purposes due to their computational simplicity. In addition to on-time arrival probability, we show how travel and overdue costs can be taken into account, making the model applicable to freight transportation problems.     

Combinatorial geometry of belt bodies

In this paper we consider a new class of convex bodies which was introduced in [11]. This is the class of belt bodies, and it is a natural generalization of the class of zonoids (see the surveys [18, 28, 24]). While the class of zonoids is not dense in the family of all centrally symmetric, convex bodies, the class of belt bodies is dense in the set of all convex bodies. Nevertheless, we shall extend solutions of combinatorial problems for zonoids (cf. [2, 12]) to the class of belt bodies. Therefore, we first introduce the set of belt bodies by using zonoids as starting point. (To make the paper self-contained, a few parts of the approach from [11] are given repeatedly.) Second, complete solutions of three well-known (and generally unsolved) problems from the combinatorial geometry of convex bodies are given for the class of belt bodies. The first of these, connected with the names of I. Gohberg and H. Hadwiger, is the problem of covering a convex body with smaller homothetic copies, or the equivalent illumination problem. The second is the Szökefalvi-Nagy problem, which asks for the determination of the convex bodies whose families of translates have a given Helly dimension. The third problem concerns special fixing systems, a notion which is due to L. Fejes Tóth. These solutions consist of improved and more general approaches to recently solved problems (as in the case of the Helly-dimensional classification of belt bodies) or new results (as those concerning minimal fixing systems, providing also an answer to a problem of B. Grünbaum which is not only restricted to belt bodies).     

Motives of some Fano varieties

We study the Fano varieties of projective k-planes lying in hypersurfaces and investigate the associated motives. The first author is partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada. The second author is partially supported by TüBİTAK-BDP funds and Bilkent University research development funds.     

On The Parameterized Intractability Of Motif Search Problems*

We show that Closest Substring, one of the most important problems in the field of consensus string analysis, is W[1]-hard when parameterized by the number k of input strings (and remains so, even over a binary alphabet). This is done by giving a “strongly structure-preserving” reduction from the graph problem Clique to Closest Substring. This problem is therefore unlikely to be solvable in time O(f(k)•n^c) for any function f of k and constant c independent of k, i.e., the combinatorial explosion seemingly inherent to this NP-hard problem cannot be restricted to parameter k. The problem can therefore be expected to be intractable, in any practical sense, for k ≥ 3. Our result supports the intuition that Closest Substring is computationally much harder than the special case of Closest String, althoughb othp roblems are NP-complete. We also prove W[1]-hardness for other parameterizations in the case of unbounded alphabet size. Our W[1]-hardness result for Closest Substring generalizes to Consensus Patterns, a problem arising in computational biology. * An extended abstract of this paper was presented at the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002), Springer-Verlag, LNCS 2285, pages 262–273, held in Juan-Les-Pins, France, March 14–16, 2002. † Work was supported by the Deutsche Forschungsgemeinschaft (DFG), research project “OPAL” (optimal solutions for hard problems in computational biology), NI 369/2. ‡ Work was done while the author was with Wilhelm-Schickard-Institut für Informatik, Universit?t Tübingen. Work was partially supported by the Deutsche Forschungsgemeinschaft (DFG), Emmy Noether research group “PIAF” (fixed-parameter algorithms), NI 369/4.     

Optimale Quantisierung

Zusammenfassung. Optimale Quantisierungen oder – damit ?quivalent – minimale Summen von Momenten spielen in mehreren Zweigen der Mathematik und ihrer Anwendungen eine Rolle. Ausgehend von der Fejes Tóth'schen Ungleichung für Summen von Momenten in der euklidischen Ebene und einem zugeh?rigen Stabilit?tssatz, werden gewisse Erweiterungen auf normierte R?ume und riemannsche Mannigfaltigkeiten h?herer Dimension besprochen. Die Ergebnisse werden dann auf Probleme aus folgenden Bereichen angewendet: (i) Datenübertragung, (ii) Wahrscheinlichkeitstheorie, (iii) numerische Integration, (iv) Approximation konvexer K?rper und (v) isoperimetrische Probleme. Eingegangen am 29. Mai 2002 / Angenommen am 8. Juli 2002     

The maximal (C,α,β) operator on Hp(T×T)

The two-dimensional classical Hardy space H_p(T×T) on the bidisc are introduced, and it is shown that the maximal operator of the (C,α,β) means of a distribution is bounded from the space H_p(T×T) to L_p(T²) (1/(α+1), 1/(β+1)<p≤∞), and is of weak type (H ₁ ^# (T×T), L₁(T²)), where the Hardy space H ₁ ^# (T×T) is defined by the hybrid maximal function. As a consequence we obtain that the (C, α, β) means of a function f∈H ₁ ^# (T×T)⊃LlogL(T ²) convergs a. e. to the function in question. Moreover, we prove that the (C, α, β) means are uniformly bounded on the spaces H_p(T×T) whenever 1/(α+1), 1(β+1)<p<∞. Thus, in case f∈H_p(T×T), the (C, α, β) means convergs to f in H_p(T×T) norm whenever (1/(α+1), 1/(β+1)<p<∞). The same results are proved for the conjugate (C, α, β) means, too.     

The maximal (C,α,β) operator on Hp(T×T)

The two-dimensional classical Hardy space H_p(T×T) on the bidisc are introduced, and it is shown that the maximal operator of the (C,α,β) means of a distribution is bounded from the space H_p(T×T) to L_p(T²) (1/(α+1), 1/(β+1)<p≤∞), and is of weak type (H ₁ ^# (T×T), L₁(T²)), where the Hardy space H ₁ ^# (T×T) is defined by the hybrid maximal function. As a consequence we obtain that the (C, α, β) means of a function f∈H ₁ ^# (T×T)⊃LlogL(T ²) convergs a. e. to the function in question. Moreover, we prove that the (C, α, β) means are uniformly bounded on the spaces H_p(T×T) whenever 1/(α+1), 1(β+1)<p<∞. Thus, in case f∈H_p(T×T), the (C, α, β) means convergs to f in H_p(T×T) norm whenever (1/(α+1), 1/(β+1)<p<∞). The same results are proved for the conjugate (C, α, β) means, too. This research was made while the author was visiting the Humboldt University in Berlin supported by the Alexander von Humboldt Foundation.     

A homotopy approach to solving the inverse mean curvature flow

In , n < 7, we treat the quasilinear, degenerate parabolic initial and boundary value problem which is the natural parabolic extension of Huisken and Ilmanen’s weak inverse mean curvature flow (IMCF). We prove long time existence and partial uniqueness of Lipschitz continuous weak solutions u(x,t) and show C ^1,α-regularity for the sets ∂{x| u(x,t) <  z }. Our approach offers a new approximation for weak solutions of the IMCF starting from a class of interesting and easily obtainable initial values; for these, the above sets are shown to converge against corresponding surfaces of the IMCF as t → ∞ globally in Hausdorff distance and locally uniformly with respect to the C ^1,α-norm.Research partially supported by the DFG, SFB 382 at Tübingen University     

An infeasible-interior-point predictor-corrector algorithm for theP *-geometric LCP

AP _*-geometric linear complementarity problem (P _*GP) as a generalization of the monotone geometric linear complementarity problem is introduced. In particular, it contains the monotone standard linear complementarity problem and the horizontal linear complementarity problem. Linear and quadratic programming problems can be expressed in a “natural” way (i.e., without any change of variables) asP _*GP. It is shown that the algorithm of Mizunoet al. [6] can be extended to solve theP _*GP. The extended algorithm is globally convergent and its computational complexity depends on the quality of the starting points. The algorithm is quadratically convergent for problems having a strictly complementary solution. The work of F. A. Potra was supported in part by NSF Grant DMS 9305760     

Kronecker representation and decompositional analysis of closed queueing networks with phase-type service distributions and arbitrary buffer sizes

Two approximative fixed-point iterative methods based on decomposition for closed queueing networks with Coxian service distributions and arbitrary buffer sizes are extended to include phase-type service distributions. The irreducible Markov chain associated with each subnetwork in the respective decompositions is represented hierarchically using Kronecker products. The two methods are implemented in a software tool capable of computing the steady-state probability vector of each subnetwork by a multilevel method at each fixed-point iteration and are compared with other methods for accuracy and efficiency. Numerical results indicate that there is a niche filled by the two approximative methods. The authors thank Jean-Michel Fourneau for pointing out Marie’s method and Brouwer’s fixed-point theorem. The first author gratefully acknowledges grant TüBA-GEBİP from the Turkish Academy of Sciences.     

A (0–1) goal programming model for scheduling the tour of a marketing executive

This paper addresses the problem of scheduling the tour of a marketing executive (ME) of a large electronics manufacturing company in India. In this problem, the ME has to visit a number of customers in a given planning period. The scheduling problem taken up in this study is different from the various personnel scheduling problems addressed in the literature. This type of personnel scheduling problem can be observed in many other situations such as periodical visits of inspection officers, tour of politicians during election campaigns, tour of mobile courts, schedule of mobile stalls in various areas, etc. In this paper the tour scheduling problem of the ME is modeled using (0–1) goal programming (GP). The (0–1) GP model for the data provided by the company for 1 month has 802 constraints and 1167 binary variables. The model is solved using LINDO software package. The model takes less than a minute (on a 1.50 MHz Pentium machine with 128 MB RAM) to get a solution of the non-preemptive version and about 6 days for the preemptive version. The main contribution is in problem definition and development of the mathematical model for scheduling the tour.     

The Contact Process Seen from a Typical Infected Site

This paper studies contact processes on general countable groups. It is shown that any such contact process has a well-defined exponential growth rate, and this quantity is used to study the process. In particular, it is proved that on any nonamenable group, the critical contact process dies out. Research supported by GAČR grant 201/06/1323 and the German Science Foundation. Part of this work was carried out when the author was employed as a postdoc at the University of Tübingen.     

Risk preference modeling with conditional average: an application to portfolio optimization

The paper introduces a new risk measure called Conditional Average (CAVG), which was designed to cover typical attitudes towards risk for any type of distribution. It can be viewed as a generalization of Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR), two commonly used risk measures. The preference structure induced by CAVG has the interpretation in Yaari’s dual theory of choice under risk and relates to Tversky and Kahneman’s cumulative prospect theory. The measure is based on the new stochastic ordering called dual prospect stochastic dominance, which can be considered as a dual stochastic ordering to recently developed prospect stochastic dominance. In general, CAVG translates into a nonconvex quadratic programming problem, but in the case of a finite probability space it can also be expressed as a mixed-integer program. The paper also presents the results of computational studies designed to assess the preference modeling capabilities of the measure. The experimental analysis was performed on the asset allocation problem built on historical values of S&P 500 sub-industry indexes. The research was supported by the grant PBZ-KBN-016/P03/99 from the State Committee for Scientific Research.     

Revisiting the Concentration Problem of Vector Fields within a Spherical Cap: A Commuting Differential Operator Solution

We propose a novel basis of vector functions, the mixed vector spherical harmonics that are closely related to the functions of Sheppard and Török and help us reduce the concentration problem of tangential vector fields within a spherical cap to an equivalent scalar problem. Exploiting an analogy with previous results published by Grünbaum, Longhi and Perlstadt, we construct a differential operator that commutes with the concentration operator of this scalar problem and propose a stable and convenient method to obtain its eigenfunctions. Having obtained the scalar eigenfunctions, the calculation of tangential vector Slepian functions is straightforward.