Three dimensional Sklyanin algebras and Gröbner bases

We consider Sklyanin algebras $S$ with 3 generators, which are quadratic algebras over a field $\K$ with $3$ generators $x,y,z$ given by $3$ relations $pxy+qyx+rzz=0$, $pyz+qzy+rxx=0$ and $pzx+qxz+ryy=0$, where $p,q,r\in\K$. this class of algebras has enjoyed much attention. In particular, using tools from algebraic geometry, Feigin, Odesskii \cite{odf}, and Artin, Tate and Van Den Bergh, showed that if at least two of the parameters $p$, $q$ and $r$ are non-zero and at least two of three numbers $p^3$, $q^3$ and $r^3$ are distinct, then $S$ is Artin--Schelter regular. More specifically, $S$ is Koszul and has the same Hilbert series as the algebra of commutative polynomials in 3 indeterminates (PHS). It has became commonly accepted that it is impossible to achieve the same objective by purely algebraic and combinatorial means like the Groebner basis technique. The main purpose of this paper is to trace the combinatorial meaning of the properties of Sklyanin algebras, such as Koszulity, PBW, PHS, Calabi-Yau, and to give a new constructive proof of the above facts due to Artin, Tate and Van Den Bergh. Further, we study a wider class of Sklyanin algebras, namely
the situation when all parameters of relations could be different. We call them generalized Sklyanin algebras. We classify up to isomorphism all generalized Sklyanin algebras with the same Hilbert series as commutative polynomials on
3 variables. We show that generalized Sklyanin algebras in general position have a Golod–Shafarevich Hilbert series (with exception of the case of field with two elements).

Multi-stage scheduling problems with precedence constraints

Abstract not available

On f-vectors of polytopes and matroids

Thesis (Ph.D.)--University of Washington, 2016-08

Dual stimulation of antigen presenting cells using carbon nanotube-based vaccine delivery system for cancer immunotherapy

Although anti−cancer immuno−based combinatorial therapeutic approaches have shown promising results, efficient tumour eradication demands further intensification of anti−tumour immune response. With the emerging field of nanovaccinology, multi−walled carbon nanotubes (MWNTs) have manifested prominent potentials as tumour antigen nanocarriers. Nevertheless, the utilization of MWNTs in co−delivering antigen along with different types of immunoadjuvants to antigen presenting cells (APCs) has not been investigated yet. We hypothesized that harnessing MWNT for concurrent delivery of cytosine−phosphate−guanine oligodeoxynucleotide (CpG) and anti-CD40 Ig (αCD40), as immunoadjuvants, along with the model antigen ovalbumin (OVA) could potentiate immune response induced against OVA−expressing tumour cells. We initially investigated the effective method to co−deliver OVA and CpG using MWNT to the APC. Covalent conjugation of OVA and CpG prior to loading onto MWNTs markedly augmented the CpG−mediated adjuvanticity, as demonstrated by the significantly increased OVA−specific T cell responses in vitro and in C57BL/6 mice. αCD40 was then included as a second immunoadjuvant to further intensify the immune response. Immune response elicited in vitro and in vivo by OVA, CpG and αCD40 was significantly potentiated by their co−incorporation onto the MWNTs. Furthermore, MWNT remarkably improved the ability of co−loaded OVA, CpG and αCD40 in inhibiting the growth of OVA−expressing B16F10 melanoma cells in subcutaneous or lung pseudo−metastatic tumour models. Therefore, this study suggests that the utilization of MWNTs for the co−delivery of tumour−derived antigen, CpG and αCD40 could be a competent approach for efficient tumours eradication.

Asymmetric polygons with maximum area

We say that a polygon inscribed in the circle is asymmetric if it contains no two antipodal points being the endpoints of a diameter. Given n diameters of a circle and a positive integer k < n, this paper addresses the problem of computing a maximum area asymmetric k-gon having as vertices k < n endpoints of the given diameters. The study of this type of polygons is motivated by ethnomusiciological applications.

A signaling visualization toolkit to support rational design of combination therapies and biomarker discovery: SiViT

Targeted cancer therapy aims to disrupt aberrant cellular signalling pathways. Biomarkers are surrogates of pathway state, but there is limited success in translating candidate biomarkers to clinical practice due to the intrinsic complexity of pathway networks. Systems biology approaches afford better understanding of complex, dynamical interactions in signalling pathways targeted by anticancer drugs. However, adoption of dynamical modelling by clinicians and biologists is impeded by model inaccessibility. Drawing on computer games technology, we present a novel visualisation toolkit, SiViT, that converts systems biology models of cancer cell signalling into interactive simulations that can be used without specialist computational expertise. SiViT allows clinicians and biologists to directly introduce for example loss of function mutations and specific inhibitors. SiViT animates the effects of these introductions on pathway dynamics, suggesting further experiments and assessing candidate biomarker effectiveness. In a systems biology model of Her2 signalling we experimentally validated predictions using SiViT, revealing the dynamics of biomarkers of drug resistance and highlighting the role of pathway crosstalk. No model is ever complete: the iteration of real data and simulation facilitates continued evolution of more accurate, useful models. SiViT will make accessible libraries of models to support preclinical research, combinatorial strategy design and biomarker discovery.

State sum models for quantum gravity

This paper reviews the construction of quantum field theory on a 4-dimensional spacetime by combinatorial methods, and discusses the recent developments in the direction of a combinatorial construction of quantum gravity.

A Lorentzian Signature Model for Quantum General Relativity

We give a relativistic spin network model for quantum gravity based on the Lorentz group and its q-deformation, the Quantum Lorentz Algebra. We propose a combinatorial model for the path integral given by an integral over suitable representations of this algebra. This generalises the state sum models for the case of the four-dimensional rotation group previously studied in gr-qc/9709028. As a technical tool, formulae for the evaluation of relativistic spin networks for the Lorentz group are developed, with some simple examples which show that the evaluation is finite in interesting cases. We conjecture that the `10J' symbol needed in our model has a finite value.

Dynamic Resource Allocation in Wireless Heterogeneous Networks

Deployment of low power basestations within cellular networks can potentially increase both capacity and coverage. However, such deployments require efficient resource allocation schemes for managing interference from the low power and macro basestations that are located within each other’s transmission range. In this dissertation, we propose novel and efficient dynamic resource allocation algorithms in the frequency, time and space domains. We show that the proposed algorithms perform better than the current state-of-art resource management algorithms. In the first part of the dissertation, we propose an interference management solution in the frequency domain. We introduce a distributed frequency allocation scheme that shares frequencies between macro and low power pico basestations, and guarantees a minimum average throughput to users. The scheme seeks to minimize the total number of frequencies needed to honor the minimum throughput requirements. We evaluate our scheme using detailed simulations and show that it performs on par with the centralized optimum allocation. Moreover, our proposed scheme outperforms a static frequency reuse scheme and the centralized optimal partitioning between the macro and picos. In the second part of the dissertation, we propose a time domain solution to the interference problem. We consider the problem of maximizing the alpha-fairness utility over heterogeneous wireless networks (HetNets) by jointly optimizing user association, wherein each user is associated to any one transmission point (TP) in the network, and activation fractions of all TPs. Activation fraction of a TP is the fraction of the frame duration for which it is active, and together these fractions influence the interference seen in the network. To address this joint optimization problem which we show is NP-hard, we propose an alternating optimization based approach wherein the activation fractions and the user association are optimized in an alternating manner. The subproblem of determining the optimal activation fractions is solved using a provably convergent auxiliary function method. On the other hand, the subproblem of determining the user association is solved via a simple combinatorial algorithm. Meaningful performance guarantees are derived in either case. Simulation results over a practical HetNet topology reveal the superior performance of the proposed algorithms and underscore the significant benefits of the joint optimization. In the final part of the dissertation, we propose a space domain solution to the interference problem. We consider the problem of maximizing system utility by optimizing over the set of user and TP pairs in each subframe, where each user can be served by multiple TPs. To address this optimization problem which is NP-hard, we propose a solution scheme based on difference of submodular function optimization approach. We evaluate our scheme using detailed simulations and show that it performs on par with a much more computationally demanding difference of convex function optimization scheme. Moreover, the proposed scheme performs within a reasonable percentage of the optimal solution. We further demonstrate the advantage of the proposed scheme by studying its performance with variation in different network topology parameters.

On homotopy spheres of low dimension

Let M be a smooth compact manifold homotopy equivalent to the 4-sphere S^4. Then M x R^1 is homeomorphism co S^4 x R^1.

On embedding 4-manifolds in R^7

A compact, connected, combinatorial 4-maifold is embeddable in R^7 if its twisted normal Stiefel-Whitney class in dimension 3 is trivial.

Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-ε)-approximations for CLIQUE require LPs of size 2^nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

Sanojen jaksot ja reunattomat tekijät. Ehrenfeuchtin—Silbergerin ongelma.

Ehrenfeuchtin–Silbergerin ongelma kysyy, kuinka pitkä sana voi olla sen pisimpien reunattomien tekijöiden pituuden suhteen, ennen kuin sillä on sen lyhimmän jakson pituinen reunaton tekijä. Ongelman ratkaisu on sanan pisimpien reunattomien tekijöiden pituudesta riippuva raja, jolle kaikilla ainakin tämän pituisilla sanoilla on välttämättä lyhimmän jakson pituinen reunaton tekijä. Tutkielmassa esitellään tämän ongelman paras tunnettu ratkaisu. Lisäksi tarkastellaan muita ongelmaan läheisesti liittyviä tuloksia. Päälauseena todistetaan paras tunnettu raja pisimpien reunattomien tekijöiden suhteen. Todistus on peräisin Štěpán Holubin ja Dirk Nowotkan artikkelista The Ehrenfeucht–Silberger problem (Journal of Combinatorial Theory, Series A) sekä tämän artikkelin alustavasta versiosta ICALP 2009 -konferenssin proceedings-julkaisussa. Esitetty ratkaisu näytetään vakiotermiä vaille optimaaliseksi vertaamalla sitä parhaaseen tunnettuun esimerkkiin äärettömästä sanajoukosta, jonka jokaisen sanan pisimmät reunattomat tekijät ovat lyhyempiä kuin lyhin jakso ja jonka jokaisen sanan pituus pisimpien reunattomien tekijöiden pituuden suhteen on suurin tunnettu. Johdatteluna esitellään perustuloksia sanan jaksoista ja reunattomista tekijöistä sekä esitellään eräitä muita ehtoja sille, milloin sanalla on sen lyhimmän jakson pituinen reunaton tekijä. Toisaalta tarkastellaan myös ongelmaa, joka kysyy vastaavaa rajaa lyhimmän jakson suhteen. Uutena tuloksena parannetaan parasta aiemmin tunnettua rajaa yhtä pienemmäksi, jolloin saatu raja on optimaalinen. Lisäksi todistetaan, mitä muotoa ovat kaikki sanat, joilla ei ole lyhimmän jaksonsa pituista reunatonta tekijää ja jotka ovat lyhimmän jaksonsa suhteen mahdollisimman pitkiä. Lisäksi tarkastellaan kriittistä tekijöihinjakoa, joka liittää sanan lyhimmän jakson sen paikallisiin jaksoihin. Kriittisen tekijöihinjaon lauseesta esitetään eräs todistus. Tämän lisäksi todistetaan päälauseen todistuksessa tarvittava lemma, joka liittyy sanan konjugaatin tekijöihinjaon kriittisyyteen.

'Explicit Learning: an Effort towards Human Scheduling Algorithms'

Abstract Scheduling problems are generally NP-hard combinatorial problems, and a lot of research has been done to solve these problems heuristically. However, most of the previous approaches are problem-specific and research into the development of a general scheduling algorithm is still in its infancy. Mimicking the natural evolutionary process of the survival of the fittest, Genetic Algorithms (GAs) have attracted much attention in solving difficult scheduling problems in recent years. Some obstacles exist when using GAs: there is no canonical mechanism to deal with constraints, which are commonly met in most real-world scheduling problems, and small changes to a solution are difficult. To overcome both difficulties, indirect approaches have been presented (in [1] and [2]) for nurse scheduling and driver scheduling, where GAs are used by mapping the solution space, and separate decoding routines then build solutions to the original problem. In our previous indirect GAs, learning is implicit and is restricted to the efficient adjustment of weights for a set of rules that are used to construct schedules. The major limitation of those approaches is that they learn in a non-human way: like most existing construction algorithms, once the best weight combination is found, the rules used in the construction process are fixed at each iteration. However, normally a long sequence of moves is needed to construct a schedule and using fixed rules at each move is thus unreasonable and not coherent with human learning processes. When a human scheduler is working, he normally builds a schedule step by step following a set of rules. After much practice, the scheduler gradually masters the knowledge of which solution parts go well with others. He can identify good parts and is aware of the solution quality even if the scheduling process is not completed yet, thus having the ability to finish a schedule by using flexible, rather than fixed, rules. In this research we intend to design more human-like scheduling algorithms, by using ideas derived from Bayesian Optimization Algorithms (BOA) and Learning Classifier Systems (LCS) to implement explicit learning from past solutions. BOA can be applied to learn to identify good partial solutions and to complete them by building a Bayesian network of the joint distribution of solutions [3]. A Bayesian network is a directed acyclic graph with each node corresponding to one variable, and each variable corresponding to individual rule by which a schedule will be constructed step by step. The conditional probabilities are computed according to an initial set of promising solutions. Subsequently, each new instance for each node is generated by using the corresponding conditional probabilities, until values for all nodes have been generated. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the Bayesian network is updated again using the current set of good rule strings. The algorithm thereby tries to explicitly identify and mix promising building blocks. It should be noted that for most scheduling problems the structure of the network model is known and all the variables are fully observed. In this case, the goal of learning is to find the rule values that maximize the likelihood of the training data. Thus learning can amount to 'counting' in the case of multinomial distributions. In the LCS approach, each rule has its strength showing its current usefulness in the system, and this strength is constantly assessed [4]. To implement sophisticated learning based on previous solutions, an improved LCS-based algorithm is designed, which consists of the following three steps. The initialization step is to assign each rule at each stage a constant initial strength. Then rules are selected by using the Roulette Wheel strategy. The next step is to reinforce the strengths of the rules used in the previous solution, keeping the strength of unused rules unchanged. The selection step is to select fitter rules for the next generation. It is envisaged that the LCS part of the algorithm will be used as a hill climber to the BOA algorithm. This is exciting and ambitious research, which might provide the stepping-stone for a new class of scheduling algorithms. Data sets from nurse scheduling and mall problems will be used as test-beds. It is envisaged that once the concept has been proven successful, it will be implemented into general scheduling algorithms. It is also hoped that this research will give some preliminary answers about how to include human-like learning into scheduling algorithms and may therefore be of interest to researchers and practitioners in areas of scheduling and evolutionary computation. References 1. Aickelin, U. and Dowsland, K. (2003) 'Indirect Genetic Algorithm for a Nurse Scheduling Problem', Computer & Operational Research (in print). 2. Li, J. and Kwan, R.S.K. (2003), 'Fuzzy Genetic Algorithm for Driver Scheduling', European Journal of Operational Research 147(2): 334-344. 3. Pelikan, M., Goldberg, D. and Cantu-Paz, E. (1999) 'BOA: The Bayesian Optimization Algorithm', IlliGAL Report No 99003, University of Illinois. 4. Wilson, S. (1994) 'ZCS: A Zeroth-level Classifier System', Evolutionary Computation 2(1), pp 1-18.

'Bayesian Optimisation for Nurse Scheduling'

A Bayesian optimisation algorithm for a nurse scheduling problem is presented, which involves choosing a suitable scheduling rule from a set for each nurse's assignment. When a human scheduler works, he normally builds a schedule systematically following a set of rules. After much practice, the scheduler gradually masters the knowledge of which solution parts go well with others. He can identify good parts and is aware of the solution quality even if the scheduling process is not yet completed, thus having the ability to finish a schedule by using flexible, rather than fixed, rules. In this paper, we design a more human-like scheduling algorithm, by using a Bayesian optimisation algorithm to implement explicit learning from past solutions. A nurse scheduling problem from a UK hospital is used for testing. Unlike our previous work that used Genetic Algorithms to implement implicit learning [1], the learning in the proposed algorithm is explicit, i.e. we identify and mix building blocks directly. The Bayesian optimisation algorithm is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, new rule strings have been obtained. Sets of rule strings are generated in this way, some of which will replace previous strings based on fitness. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. For clarity, consider the following toy example of scheduling five nurses with two rules (1: random allocation, 2: allocate nurse to low-cost shifts). In the beginning of the search, the probabilities of choosing rule 1 or 2 for each nurse is equal, i.e. 50%. After a few iterations, due to the selection pressure and reinforcement learning, we experience two solution pathways: Because pure low-cost or random allocation produces low quality solutions, either rule 1 is used for the first 2-3 nurses and rule 2 on remainder or vice versa. In essence, Bayesian network learns 'use rule 2 after 2-3x using rule 1' or vice versa. It should be noted that for our and most other scheduling problems, the structure of the network model is known and all variables are fully observed. In this case, the goal of learning is to find the rule values that maximize the likelihood of the training data. Thus, learning can amount to 'counting' in the case of multinomial distributions. For our problem, we use our rules: Random, Cheapest Cost, Best Cover and Balance of Cost and Cover. In more detail, the steps of our Bayesian optimisation algorithm for nurse scheduling are: 1. Set t = 0, and generate an initial population P(0) at random; 2. Use roulette-wheel selection to choose a set of promising rule strings S(t) from P(t); 3. Compute conditional probabilities of each node according to this set of promising solutions; 4. Assign each nurse using roulette-wheel selection based on the rules' conditional probabilities. A set of new rule strings O(t) will be generated in this way; 5. Create a new population P(t+1) by replacing some rule strings from P(t) with O(t), and set t = t+1; 6. If the termination conditions are not met (we use 2000 generations), go to step 2. Computational results from 52 real data instances demonstrate the success of this approach. They also suggest that the learning mechanism in the proposed approach might be suitable for other scheduling problems. Another direction for further research is to see if there is a good constructing sequence for individual data instances, given a fixed nurse scheduling order. If so, the good patterns could be recognized and then extracted as new domain knowledge. Thus, by using this extracted knowledge, we can assign specific rules to the corresponding nurses beforehand, and only schedule the remaining nurses with all available rules, making it possible to reduce the solution space. Acknowledgements The work was funded by the UK Government's major funding agency, Engineering and Physical Sciences Research Council (EPSRC), under grand GR/R92899/01. References [1] Aickelin U, "An Indirect Genetic Algorithm for Set Covering Problems", Journal of the Operational Research Society, 53(10): 1118-1126,