Computer Science Theses and Dissertations
http://hdl.handle.net/1903/2756
Tue, 28 Feb 2017 14:27:52 GMT2017-02-28T14:27:52ZLARGE SCALE AGENT-BASED MODELING: SIMULATING TWITTER USERS
http://hdl.handle.net/1903/19050
LARGE SCALE AGENT-BASED MODELING: SIMULATING TWITTER USERS
Ariyaratne, Arjuna
This thesis details an attempt to conduct a large-scale Agent-based modeling
simulation where simulating Twitter users are used as an example. In this thesis,
Computational Mechanics is used for developing rules that govern each Agent. This
thesis also details the development of an entirely new simulation software capable of
simulating a large number of Agents by taking advantage of the parallelism offered
by latest computing platforms. Development details of this simulation software,
named elixrABM, is available from the concept phase to the testing phase of the
simulator.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/1903/190502016-01-01T00:00:00ZCombinatorial Algorithms for the Active Time and Busy Time Problems
http://hdl.handle.net/1903/19023
Combinatorial Algorithms for the Active Time and Busy Time Problems
Kumar, Saurabh
In this thesis, we consider the problem of scheduling jobs in such a way that we minimize the energy consumption of the machines they are scheduled on. Job scheduling itself has a long and rich history in computer science both from theoretical and applied perspectives. A multitude of different objectives to optimize have been considered such as weighted completion time, penalties for missed deadlines, etc. However, traditional objective functions such as these do not capture or model the energy consumption of the machines these jobs run on. Energy consumption is an important facet of job scheduling to consider not only because of its relationship with the financial costs of scheduling (such as those related to cooling and the cost of powering the machines) but also due to its impact on the environment. This is especially true in the context of data centers as more and more processing is pushed to the cloud. We study two problems related to these issues - the active time problem and the busy time problem. First, we give a purely combinatorial algorithm for the active time problem which matches its best known approximation ratio (the existing algorithm is based on a rather involved LP rounding scheme). Second, we describe a local search based heuristic for the problem and also consider an experimental evaluation of these algorithms on artificially generated data. Finally, we describe two very simple algorithms which match the current best upper bounds for the busy time problem when all job lengths are equal.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/1903/190232016-01-01T00:00:00ZTemporal Tracking Urban Areas using Google Street View
http://hdl.handle.net/1903/19020
Temporal Tracking Urban Areas using Google Street View
Najafizadeh, Ladan
Tracking the evolution of built environments is a challenging problem in computer vision due to the intrinsic complexity of urban scenes, as well as the dearth of temporal visual information from urban areas. Emerging technologies such as street view cars, provide massive amounts of high quality imagery data of urban environments at street-level (e.g., sidewalks, buildings, and aesthetics of streets). Such datasets are consistent with respect to space and time; hence, they could be a potential source for exploring the temporal changes transpiring in built environments. However, using street view images to detect temporal changes in urban scenes induces new challenges such as variation in illumination, camera pose, and appearance/disappearance of objects.
In this thesis, we leverage Google Street View’s new feature, “time machine”, to track and label the temporal changes of built environments, specifically accessibility features (e.g., existence of curb-ramps, condition of sidewalks). The main contributions of this thesis are: (i) initial proof-of-concept automated method for tracking accessibility features through panorama images across time, (ii) a framework for processing and analyzing time series panoramas at scale, and (iii) a geo-temporal dataset including different types of accessibility features for the task of detection.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/1903/190202016-01-01T00:00:00ZAssignment problems and their application in economics
http://hdl.handle.net/1903/19016
Assignment problems and their application in economics
Abolhassani, Melika
Four assignment problems are introduced in this thesis, and they are approached
based on the context they are presented in. The underlying graphs of
the assignment problems in this thesis are in most cases bipartite graphs with two
sets of vertices corresponding to the agents and the resources. An edge might show
the interest of an agent in a resource or willingness of a manufacturer to produce
the corresponding product of a market, to name a few examples.
The rst problem studied in this thesis is a two-stage stochastic matching
problem in both online and oine versions. In this work, which is presented in
Chapter 2 of this thesis, a coordinator tries to benet by having access to the
statistics of the future price discounts which can be completely unpredictable for
individual customers. In our model, individual risk-averse customers want to book
hotel rooms for their future vacation; however, they are unwilling to leave booking to
the last minute which might result in huge savings for them since they have to take
the risk of all the hotel rooms being sold out. Instead of taking this risk, individual
customers make contracts with a coordinator who can spread the risk over many
such cases and also has more information on the probability distribution of the future
prices. In the rst stage, the coordinator agrees to serve some buyers, and then in
the second stage, once the nal prices have been revealed, he books rooms for them
just as he promised. An agreement between the coordinator and each buyer consists
of a set of acceptable hotels for the customer and a single price. Two models for
this problem are investigated. In the rst model, the details of the agreements are
proposed by the buyer, and we propose a bicriteria-style approximation algorithm
that gives a constant-factor approximation to the objective function by allowing a
bounded fraction of our hotel bookings to overlap. In the second model, the details
of the agreements are proposed by the coordinator, and we show the prices yielding
the optimal prot up to a small additive loss can be found by a polynomial time
algorithm.
In the third chapter of this thesis, two versions of the online matching problem
are analyzed with a similar technique. Online matching problems have been studied
by many researchers recently due to their direct application in online advertisement
systems such as Google Adwords. In the online bipartite matching problem, the
vertices of one side are known in advance; however, the vertices of the other side
arrive one by one, and reveal their adjacent vertices on the oine side only upon
arrival. Each vertex can only be matched to an unmatched vertex once it arrives and
we cannot match or rematch the online vertex in the future. In the online matching
problem with free disposal, we have the option to rematch an already matched oine
vertex only if we eliminate its previous online match from the graph. The goal is to
maximize the expected size of the matching. We propose a randomized algorithm
that achieves a ratio greater than 0:5 if the online nodes have bounded degree. The
other problem studied in the third chapter is the edge-weighted oblivious matching in
which the weights of all the edges in the underlying graph are known but existence
of each edge is only revealed upon probing that edge. The weighted version of
the problem has applications in pay-per-click online advertisements, in which the
revenue for a click on a particular ad is known, but it is unknown whether the user
will actually click on that ad. Using a similar technique, we develop an algorithm
with approximation factor greater than 0:5 for this problem too.
In Chapter 4, a generalized version of the Cournot Competition (a foundational
model in economics) is studied. In the traditional version, rms are competing in
a single market with one heterogeneous good, and their strategy is the quantity
of good they produce. The price of the good is an inverse function of the total
quantity produced in the market, and the cost of production for each rm in each
market increases with the quantity it produces. We study Cournot Competition on
a bipartite network of rms and markets. The edges in this network demonstrate
access of a rm to a market. The price of the good in each market is again an
inverse function of the quantity of the good produced by the rms, and the cost of
production for each rm is a function of its production in dierent markets. Our
goal is to give polynomial time algorithms to nd the quantity produced by rms
in each market at the equilibrium for generalized cost and price functions.
The nal chapter of this thesis is on analyzing a problem faced by online
marketplaces such as Amazon and ebay which deal with huge datasets registering
transaction of merchandises between many buyers and sellers. As the size of datasets
grow, it is important that the algorithms become more selective in the amount of
data they store. Our goal is to develop pricing algorithms for social welfare (or
revenue) maximization that are appropriate for use with the massive datasets in
these networks. We specially focus on the streaming setting, the common model
for big data analysis. Furthermore, we include hardness results (lower bounds)
on the minimum amount of memory needed to calculate the exact prices and also
present algorithms which are more space ecient than the given lower bounds but
approximate the optimum prices for the goods besides the revenue or the social
welfare of the mechanism.
Fri, 01 Jan 2016 00:00:00 GMThttp://hdl.handle.net/1903/190162016-01-01T00:00:00Z