Problems combining facility location with connectivity requirements are fundamental in network design. In this thesis, we investigate the Connected Facility Location (CFL) problem through the non-trivial special case of Single-Sink Rent-or Buy (SRoB) problem. We develop two approaches for this problem, and illustrate the limitations and promises of both. Our first approach is based on a natural linear program for SRoB. Till date, no algorithm based on this linear program is known. We sketch an algorithm which performs well in many instances of the problem, but runs into trouble for certain pathological cases, which we illustrate. Our second approach borrows ideas from the dual fitting algorithm for metric uncapacitated facility location by Jain et al. (called JMS algorithm), and combines it with the Goemans-Williamson moat growing procedure. This approach aims to neutralize the slack in the Goemans-Williamson argument with the one associated with the JMS procedure, and thus holds a lot of promise for achieving an overall 2-approximation for CFL. Apart from these two approaches, we investigate the scope for improvement in the 4.55- approximation algorithm due to Swamy and Kumar, which gives the current best primal-dual based performance guarantee for SRoB. We illustrate a very simple instance where the algorithm produces a 3-approximation, thus giving a lower bound on the performance guarantee for that algorithm
Approximation Algorithms in Network Design
Could market mechanisms be employed to tackle or relieve Internet congestion? We look at three market mechanisms: consumer-side congestion pricing, content-side paid prioritization, and bilateral risk sharing agree- ments. While the former two have been heavily studied in economic literature, the risk sharing approach towards congestion is a novel addition of this thesis. We treat the uncertainty in broadband congestion levels as an economic risk that consumers and Internet businesses are forced to bear. The thesis investigates the possibility of introducing congestion-based financial instruments, similar to derivatives in a stock market, that efficiently allocate risk borne out of congestion.
Congestion Based Financial Instruments for the Internet Economy
Artificial Intelligence began as a field probing some of the most fundamental questions of science - the nature of intelligence and the design of intelligent artifacts. But it has grown into a discipline that is deeply entwined with commerce and society. Today’s AI technology, such as expert systems and intelligent assistants, raise difficult questions of risk, trust and accountability. In this paper, we present these concerns, examining them in the context of historical developments that have shaped the nature and direction of AI research. We also suggest the exploration and further development of two paradigms - human intelligence-machine cooperation and a sociological view of intelligence - which will help address these concerns.
Man and Machine: Questions of Risk, Trust and Accountability in Today’s AI Technology. Preprint at Arxiv
A vector space over a field \(\mathbb{F}\) is a set \(V\) together with two binary operations, called vector addition and scalar multiplication. It is standard practice to think of a Euclidean space \(\mathbb{R}^n\) as an \(n\)-dimensional real coordinate space i.e. the space of all \(n\)-tuples of real numbers \(R^n\), with vector operations defined using real addition and multiplication coordinate-wise. A natural question which arises is if it is possible to redefine vector operations on the space in such a way that it acquires some other dimension, say \(k\) (over the same field, i.e., \(\mathbb{R}\)). In this paper, we answer the question in the affirmative, for all \(k\in\mathbb{N}\). We achieve the required dimension by ‘dragging’ the structure of a standard \(k\)-dimensional Euclidean space \(\mathbb{R}^k\) on the \(n\)-tuple of real numbers \(R^n\). At the heart of the argument is Cantor’s counterintuitive result that \(\mathbb{R}\) is numerically equivalent to \(\mathbb{R}^n\) for all \(n\in\mathbb{N}\), which can be proved through an elegant construction. Finally, we generalize the result to all finite dimensional vector spaces.
Redimensioning of Euclidean Spaces. Preprint at Arxiv
Is our instinct for altruism fatal to the assumptions of strict rationality in mainstream economics? Or is the utility function in expected utility theory flexible enough to accomodate altruistic preferences? Rationality in expected utility theory (specifically Von Neumann-Morgenstern rationality) requires the satisfaction of four axioms: completeness, transitivity, continuity, independence. These are quite reasonable requirements of rational behavior. We argue, however, that the human altruistic instinct can lead to violations of transitivity and independence axioms, and propose experiments to demonstrate it. We also explain these departures from VNM rationality in light of the recent literature on behavioral economics. Lastly, we hypothesize that the psychological value of money depends on ownership, and propose further experiments to test it.