Mathematics (MA)
https://etd.iisc.ac.in/handle/2005/49
2024-03-28T13:58:44ZAlgorithmic and Hardness Results for Fundamental Fair-Division Problems
https://etd.iisc.ac.in/handle/2005/5205
Algorithmic and Hardness Results for Fundamental Fair-Division Problems
Rathi, Nidhi
The theory of fair division addresses the fundamental problem of dividing a set of resources among the participating agents in a satisfactory or meaningfully fair manner. This thesis examines the key computational challenges that arise in various settings of fair-division problems and complements the existential (and non-constructive) guarantees and various hardness results by way of developing efficient (approximation) algorithms and identifying computationally tractable instances.
• Our work in fair cake division develops several algorithmic results for allocating a divisible resource (i.e., the cake) among a set of agents in a fair/economically efficient manner. While strong existence results and various hardness results exist in this setup, we develop a polynomial-time algorithm for dividing the cake in an approximately fair and efficient manner. Furthermore, we identify an encompassing property of agents’ value densities (over the cake)—the monotone likelihood ratio property (MLRP)—that enables us to prove strong algorithmic results for various notions of fairness and (economic) efficiency.
• Our work in fair rent division develops a fully polynomial-time approximation scheme (FPTAS) for dividing a set of discrete resources (the rooms) and splitting the money (rents) among agents having general utility functions (continuous, monotone decreasing, and piecewise-linear), in a fair manner. Prior to our work, efficient algorithms for finding such solutions were known only for a specific set of utility functions. We com- plement the algorithmic results by proving that the fair rent division problem (under general utilities) lies in the intersection of the complexity classes, PPAD (Polynomial Parity Arguments on Directed graphs) and PLS (Polynomial Local Search).
• Our work respectively addresses fair division of rent, cake (divisible), and discrete (in- divisible) goods in a partial information setting. We show that, for all these settings and under appropriate valuations, a fair (or an approximately fair) division among n agents can be efficiently computed using only the valuations of n 1 agents. The nth (secretive) agent can make an arbitrary selection after the division has been proposed and, irrespective of her choice, the computed division will admit an overall fair allocation.
An Algorithmic Approach To Crystallographic Coxeter Groups
https://etd.iisc.ac.in/handle/2005/1927
An Algorithmic Approach To Crystallographic Coxeter Groups
Malik, Amita
Coxeter group, named after H.S.M. Coxeter, is an abstract group that admits a formal description in terms of mirror symmetries. It turns out that the finite Coxeter groups are precisely the finite Euclidean reflection groups. Coxeter studied these groups and classified all finite ones in 1935, however they were known as reflection groups until J. Tits coined the term Coxeter groups for them in the sixties.
Finite crystallographic Coxeter groups, also known as finite Weyl groups, play a prominent role in many branches of mathematics like combinatorics, Lie theory, number theory, and geometry. The computational aspects of these groups are of great interests and play a very important role in representation theory. Since it’s enough to study only the irreducible class of groups in order to understand any Coxeter group, we discuss irreducible crystallographic Coxeter groups here.
Our goal is to try to deal with some of the fundamental computational problems that arise in working with the structures such as Weyl groups, root system, Weyl characters. For the classical cases, especially type A, many of these problems are not very subtle and have been solved completely. However, these solutions often do not generalize.
In this report, our emphasis is on algorithms which do not really depend on the classifications of root systems. The canonical example, we always keep in mind is E8. In chapter 1, we fix the notations and give some basic results which have been used in this report. In chapter 2, we explain algorithms to various Weyl group problems like membership problem; how to find the length of an element; how to check if two words in a Weyl group represent the same element or not; finding the coset representative for an element for a given parabolic subgroup; and list all the expressions possible for an element. In chapter 3, the main goal is to write an algorithm to compute the weight multiplicities of the irreducible representations using Freudenthal’s formula. For this, we first compute the positive roots and dominant weights for a given root system and then finally find the weight multiplicities. We argue this mathematically using the results given in chapter 1. The crystallographic hypothesis is unnecessary for much of what is discussed in chapter 2. In the last chapter, we give codes of the computer programs written in C++ which implement the algorithms described in the previous chapters in this report.
2013-02-14T00:00:00ZAnalysis of Proportional Navigation Class of Guidance Law against Agile Targets
https://etd.iisc.ac.in/handle/2005/2903
Analysis of Proportional Navigation Class of Guidance Law against Agile Targets
Ghosh, Satadal
Guidance is defined as the determination of a strategy for following a nominal path in the presence of o-nominal conditions, disturbances and uncertainties, and the strategy employed is called a guidance law. Variants of Proportional Navigation (PN), such as True Proportional Navigation (TPN) and Pure Proportional Navigation (PPN), have been studied extensively in the literature on tactical missile guidance. In the absence of target maneuvers, in a linear interceptor guidance problem, TPN was shown to be optimal. However, the standard PN class of guidance laws per se does not show good performance against maneuvering targets, and was found to be eective in intercepting a maneuvering target only from a restrictive set of initial geometries. Also, since these guidance laws were eectively designed for lower speed targets, they show a degraded performance when applied against higher speed targets. However, in the current defense scenario, two classes of agile targets, which are capable of continuous maneuver, and/or of much higher speed than the interceptor, are a reality. This thesis presents analysis of several variants of PN class of guidance laws against these two classes of agile targets.
In the literature, an augmentation of the TPN guidance law, termed as Augmented Proportional Navigation (APN), was shown to be optimal in linearized engagement framework. The present work proposes an augmentation of the PPN guidance law, which is more realistic than TPN for an aerodynamically controlled interceptor, and an-alyzes its capturability in fully nonlinear framework, and develops sauciest conditions on speed ratio, navigation gain and augmentation parameter to ensure that all possible initial engagement geometries are included in the capture zone when applied against a target executing piecewise continuous maneuver. The thesis also obtains the capture zone in the relative velocity space for augmented PPN guidance law.
In the literature, a novel guidance law was proposed for the interception of higher speed targets in planar engagement by using a negative navigation gain instead of the standard positive one, and was termed as Retro-PN. It was shown that even though the Retro-PN guided interceptor takes more time than PN guided one in achieving successful interception, Retro-PN performs significantly better than the classical PN law, in terms of capturability, lateral acceleration demand, and closing velocity, when used against higher speed targets. The thesis analyzes Retro-PN guidance law in 3-D engagement geometries to yield the complete capture zone of interceptors guided by Retro-PN guidance philosophy, and derives necessary and sucient conditions for the capture of higher speed non-maneuvering targets with and without a constraint on finiteness of lateral acceleration.
Terminal impact angle control is crucial for enhancement of warhead eectiveness. In the literature, this problem has been addressed mostly in the context of targets with lower speeds than the interceptor. The thesis analyzes the performance of a composite PN guidance law, that uses standard PPN and the Retro-PN guidance laws based on initial engagement geometry and requirement of impact angle, against higher speed non-maneuvering targets. Then, to expand the set of achievable impact angles, it proposes a modified composite PN guidance scheme, and analyzes the same.
For implementation of many modern guidance laws, a good estimate of time-to-go is essential. This requirement is especially severe in case of impact time constrained en-gagement scenarios. To this end, an ecient and fast time-to-go estimation algorithm for generic 3-D engagement is required. Two time-to-go estimation algorithms are presented and analyzed in this work for the engagement of a PPN or Retro-PN guided interceptor and a higher speed target. The first one is a closed form approximation of time-to-go in terms of range, nominal closing speed and an indicator of heading error, and the second one is a numerical recursive time-to-go estimation algorithm.
To improve the odds of intercepting an intelligent target and destroying it, a salvo attack of two or more interceptors could be considered as a viable option. Moreover, this simultaneous salvo attack can also be further improved in eciency by incorporating the shoot-look-shoot approach in making a decision about launching interceptors. This can be considered as the first step towards a layered defense system, which has been described in the literature as a potentially eective strategy against short range or long range ballistic threat. To this end, the present work proposes two PPN and Retro-PN based guidance strategies for achieving simultaneous salvo attack on a higher speed non-maneuvering target. For the implementation of the same the numerical recursive time-to-go estimation technique proposed in this work is utilized
2017-12-12T00:00:00ZAnalytic and Entire Vectors for Representations of Lie Groups
https://etd.iisc.ac.in/handle/2005/2937
Analytic and Entire Vectors for Representations of Lie Groups
Kumar, Manish
We start with the recollection of basic results about differential manifolds and Lie groups. We also recall some preliminary terminologies in Lie algebra. Then we define the Lie algebra corresponding to a Lie group. In the next section, we define a strongly continuous representation of a Lie group on a Banach space. We further define the smooth, analytic and entire vectors for a given representation. Then, we move on to develop some necessary and sufficient criteria to characterize smooth, analytic and entire vectors. We, in particular, take into account of some specific representations of Lie groups like the regular representation of R, the irreducible representations of Heisenberg groups, the irreducible representations of the group of Affine transformations and finally the representations of non-compact simple Lie groups.
2018-01-01T00:00:00Z