Equivalence of piecewise-linear approximation and Lagrangian relaxation for network revenue management

The network revenue management (RM) problem arises in airline, hotel, media,and other industries where the sale products use multiple resources. It can be formulatedas a stochastic dynamic program but the dynamic program is computationallyintractable because of an exponentially large state space, and a number of heuristicshave been proposed to approximate it. Notable amongst these -both for their revenueperformance, as well as their theoretically sound basis- are approximate dynamic programmingmethods that approximate the value function by basis functions (both affinefunctions as well as piecewise-linear functions have been proposed for network RM)and decomposition methods that relax the constraints of the dynamic program to solvesimpler dynamic programs (such as the Lagrangian relaxation methods). In this paperwe show that these two seemingly distinct approaches coincide for the network RMdynamic program, i.e., the piecewise-linear approximation method and the Lagrangianrelaxation method are one and the same.

Asymptotic equivalence between the unconditional maximum likelihood and the square-law nonlinearity symbol timing estimation

This paper provides a systematic approach to theproblem of nondata aided symbol-timing estimation for linearmodulations. The study is performed under the unconditionalmaximum likelihood framework where the carrier-frequencyerror is included as a nuisance parameter in the mathematicalderivation. The second-order moments of the received signal arefound to be the sufficient statistics for the problem at hand and theyallow the provision of a robust performance in the presence of acarrier-frequency error uncertainty. We particularly focus on theexploitation of the cyclostationary property of linear modulations.This enables us to derive simple and closed-form symbol-timingestimators which are found to be based on the well-known squaretiming recovery method by Oerder and Meyr. Finally, we generalizethe OM method to the case of linear modulations withoffset formats. In this case, the square-law nonlinearity is foundto provide not only the symbol-timing but also the carrier-phaseerror.

The orthogonal subcategory problem in homotopy theory

It is known that, in a locally presentable category, localization exists with respect to every set of morphisms, while the statement that localization with respect to every (possibly proper) class of morphisms exists in locally presentable categories is equivalent to a large-cardinal axiom from set theory. One proves similarly, on one hand, that homotopy localization exists with respect to sets of maps in every cofibrantly generated, left proper, simplicial model category M whose underlying category is locally presentable. On the other hand, as we show in this article, the existence of localization with respect to possibly proper classes of maps in a model category M satisfying the above assumptions is implied by a large-cardinal axiom called Vopënka's principle, although we do not know if the reverse implication holds. We also show that, under the same assumptions on M, every endofunctor of M that is idempotent up to homotopy is equivalent to localization with respect to some class S of maps, and if Vopënka's principle holds then S can be chosen to be a set. There are examples showing that the latter need not be true if M is not cofibrantly generated. The above assumptions on M are satisfied by simplicial sets and symmetric spectra over simplicial sets, among many other model categories.

Periodic orbits of the planar collision restricted 3-body problem

Using the continuation method we prove that the circular and the elliptic symmetric periodic orbits of the planar rotating Kepler problem can be continued into periodic orbits of the planar collision restricted 3–body problem. Additionally, we also continue to this restricted problem the so called “comets orbits”.

Polynomial-time complexity for instances of the endomorphism problem in free groups

We say the endomorphism problem is solvable for an element W in a free group F if it can be decided effectively whether, given U in F, there is an endomorphism Φ of F sending W to U. This work analyzes an approach due to C. Edmunds and improved by C. Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when W is a two- generator word. We show that when W is a two-generator word this algorithm solves the problem in time polynomial in the length of U. This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side.

Periodic orbits near a heteroclinic loop formed by one dimensional orbit and a 2-dimensional manifold: application to the charged collinear 3-body problem

The paper is devoted to the study of a type of differential systems which appear usually in the study of some Hamiltonian systems with 2 degrees of freedom. We prove the existence of infinitely many periodic orbits on each negative energy level. All these periodic orbits pass near the total collision. Finally we apply these results to study the existence of periodic orbits in the charged collinear 3–body problem.

Bribe-proof rules in the division problem

The division problem consists of allocating an amount of a perfectly divisible good among a group of n agents with single-peaked preferences. A rule maps preference profiles into n shares of the amount to be allocated. A rule is bribe-proof if no group of agents can compensate another agent to misrepresent his preference and, after an appropriate redistribution of their shares, each obtain a strictly preferred share. We characterize all bribe-proof rules as the class of efficient, strategy-proof, and weak replacement monotonic rules. In addition, we identify the functional form of all bribe-proof and tops-only rules.

A maximal domain of preferences for tops-only rules in the division problem

The division problem consists of allocating an amount M of a perfectly divisible good among a group of n agents. Sprumont (1991) showed that if agents have single-peaked preferences over their shares, the uniform rule is the unique strategy-proof, efficient, and anonymous rule. Ching and Serizawa (1998) extended this result by showing that the set of single-plateaued preferences is the largest domain, for all possible values of M, admitting a rule (the extended uniform rule) satisfying strategy-proofness, efficiency and symmetry. We identify, for each M and n, a maximal domain of preferences under which the extended uniform rule also satisfies the properties of strategy-proofness, efficiency, continuity, and "tops-onlyness". These domains (called weakly single-plateaued) are strictly larger than the set of single-plateaued preferences. However, their intersection, when M varies from zero to infinity, coincides with the set of single-plateaued preferences.

On Boas-Type Problem

R.P. Boas has found necessary and sufficient conditions of belonging of function to Lipschitz class. From his findings it turned out, that the conditions on sine and cosine coefficients for belonging of function to Lip α(0 & α & 1) are the same, but for Lip 1 are different. Later his results were generalized by many authors in the viewpoint of generalization of condition on the majorant of modulus of continuity. The aim of this paper is to obtain Boas-type theorems for generalized Lipschitz classes. To define generalized Lipschitz classes we use the concept of modulus of smoothness of fractional order.

Normal forms for rational difference equations with applications to the global periodicity problem

We propose a classification and derive the associated normal forms for rational difference equations with complex coefficients. As an application, we study the global periodicity problem for second order rational difference equations with complex coefficients. We find new necessary conditions as well as some new examples of globally periodic equations.

The word problem distinguishes counter languages

Counter automata are more powerful versions of finite state automata where addition and subtraction operations are permitted on a set of n integer registers, called counters. We show that the word problem of Zn is accepted by a nondeterministic m-counter automaton if and only if m &= n.

On the complexity of the Whitehead minimization problem

The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem – to decide whether a word is an element of some basis of the free group – and the free factor problem can also be solved in polynomial time.

Addressing the net balances problem as a prerequisite for EU budget reform: a proposal

Conflict among member states regarding the distribution of net financial burdens has been allowed to contaminate the entire design of the EU budget with very negative consequences in terms of equity, efficiency and transparency. To get around this problem and pave the way for a substantive budget reform, we propose to decouple distributional negotiations from the rest of the budget process by linking member state net balances in a rigid manner to relative prosperity. This would be achieved through the introduction of a system of compensating horizontal transfers that would take to its logical conclusion the Commission's proposal for a generalized compensation mechanism. We discuss the impact of the proposed scheme on member states? incentives and illustrate its financial implications using revenue and expenditure projections for 2013 that are based on the current Financial Perspectives and Own Resources Decision.

On locally finite transitive two-ended digraphs

Projecte de recerca elaborat a partir d’una estada al Department de Matemàtica Aplicada de la Montanuniversität Leoben, Àustria, entre agost i desembre del 2006. L’ objectiu ha estat fer recerca sobre digrafs infinits amb dos finals, connexos i localment finits, i, en particular, en digrafs amb dos finals i altament arc-transitius. Malnic, Marusic et al. van introduir un nou tipus de relació d’equivalència en els vèrtexs d’un dígraf, anomenades relacions d’assolibilitat, que generalitzen i tenen el seu origen en un problema posat per Cameron et al., on les classes de la relació d’equivalència eren vèrtexs que pertanyien a un camí alternat del dígraf . Malnic et al. en el mencionat article van establir connexions ben estretes entre aquestes relacions d’assolibilitat i l'estructura de finals i creixement dels digrafs localment finits i transitius. En aquest treball, s’ha caracteritzat per complet aquestes relacions d’assolibitat en el cas de dígrafs localment finits i transitius amb exactament dos finals, en termes de la descomposició en números primers del número de línies que genera el digraf amb dos finals. A més, es nega la Conjectura 1 sostinguda per Seifter que afirmava que un digraf connex localment finit amb més d’un final era necessàriament o be 0-, 1- o altament arc-transitiu. Seifer havia donat una solució parcial a la conjectura pel cas de digrafs regulars amb grau primer que tinguin un conjunt de tall connex. En aquest treball, es descriu una família infinita de dígrafs regulars de grau dos, amb dos finals, exactament 2-arc transitius i no 3-arc transitius. Així, es nega la Conjectura de Seifter en el cas general, fins i tot per grau primer. Tot i així, la solució parcial donada per Seifter en el seu article és en cert sentit la millor possible i l'existència un conjunt de tall connex essencial.