Source author record

Matthew P. Johnson

Matthew P. Johnson appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Discrete Mathematics Computer Science and Game Theory Data Structures and Algorithms Networking and Internet Architecture Social and Information Networks Computational Geometry math.CO physics.soc-ph

Catalog footprint

What is connected

6works

8topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2016arXiv

Selfish Knapsack

We consider a selfish variant of the knapsack problem. In our version, the items are owned by agents, and each agent can misrepresent the set of items she owns---either by avoiding reporting some of them (understating), or by reporting additional ones that do not exist (overstating). Each agent's objective is to maximize, within the items chosen for inclusion in the knapsack, the total valuation of her own chosen items. The knapsack problem, in this context, seeks to minimize the worst-case approximation ratio for social welfare at equilibrium. We show that a randomized greedy mechanism has attractive strategic properties: in general, it has a correlated price of anarchy of $2$ (subject to a mild assumption). For overstating-only agents, it becomes strategyproof; we also provide a matching lower bound of $2$ on the (worst-case) approximation ratio attainable by randomized strategyproof mechanisms, and show that no deterministic strategyproof mechanism can provide any constant approximation ratio. We also deal with more specialized environments. For the case of $2$ understating-only agents, we provide a randomized strategyproof $\frac{5+4\sqrt{2}}{7} \approx 1.522$-approximate mechanism, and a lower bound of $\frac{5\sqrt{5}-9}{2} \approx 1.09$. When all agents but one are honest, we provide a deterministic strategyproof $\frac{1+\sqrt{5}}{2} \approx 1.618$-approximate mechanism with a matching lower bound. Finally, we consider a model where agents can misreport their items' properties rather than existence. Specifically, each agent owns a single item, whose value-to-size ratio is publicly known, but whose actual value and size are not. We show that an adaptation of the greedy mechanism is strategyproof and $2$-approximate, and provide a matching lower bound; we also show that no deterministic strategyproof mechanism can provide a constant approximation ratio.

preprint2013arXiv

Computing Traversal Times on Dynamic Markovian Paths

In source routing, a complete path is chosen for a packet to travel from source to destination. While computing the time to traverse such a path may be straightforward in a fixed, static graph, doing so becomes much more challenging in dynamic graphs, in which the state of an edge in one time slot (i.e., its presence or absence) is random, and may depend on its state in the previous time step. The traversal time is due to both time spent waiting for edges to appear and time spent crossing them once they become available. We compute the expected traversal time (ETT) for a dynamic path in a number of special cases of stochastic edge dynamics models, and for three edge failure models, culminating in a surprisingly challenging yet realistic setting in which the initial configuration of edge states for the entire path is known. We show that the ETT for this "initial configuration" setting can be computed in quadratic time, by an algorithm based on probability generating functions. We also give several linear-time upper and lower bounds on the ETT.

preprint2012arXiv

Funding Games: the Truth but not the Whole Truth

We introduce the Funding Game, in which $m$ identical resources are to be allocated among $n$ selfish agents. Each agent requests a number of resources $x_i$ and reports a valuation $\tilde{v}_i(x_i)$, which verifiably {\em lower}-bounds $i$'s true value for receiving $x_i$ items. The pairs $(x_i, \tilde{v}_i(x_i))$ can be thought of as size-value pairs defining a knapsack problem with capacity $m$. A publicly-known algorithm is used to solve this knapsack problem, deciding which requests to satisfy in order to maximize the social welfare. We show that a simple mechanism based on the knapsack {\it highest ratio greedy} algorithm provides a Bayesian Price of Anarchy of 2, and for the complete information version of the game we give an algorithm that computes a Nash equilibrium strategy profile in $O(n^2 \log^2 m)$ time. Our primary algorithmic result shows that an extension of the mechanism to $k$ rounds has a Price of Anarchy of $1 + \frac{1}{k}$, yielding a graceful tradeoff between communication complexity and the social welfare.

preprint2011arXiv

Computing the obstacle number of a plane graph

An obstacle representation of a plane graph G is V(G) together with a set of opaque polygonal obstacles such that G is the visibility graph on V(G) determined by the obstacles. We investigate the problem of computing an obstacle representation of a plane graph (ORPG) with a minimum number of obstacles. We call this minimum size the obstacle number of G. First, we show that ORPG is NP-hard by reduction from planar vertex cover, resolving a question posed by [8]. Second, we give a reduction from ORPG to maximum degree 3 planar vertex cover. Since this reduction preserves solution values, it follows that ORPG is fixed parameter tractable (FPT) and admits a polynomial-time approximation scheme (PTAS).

preprint2011arXiv

Evader Interdiction and Collateral Damage

In network interdiction problems, evaders (e.g., hostile agents or data packets) may be moving through a network towards targets and we wish to choose locations for sensors in order to intercept the evaders before they reach their destinations. The evaders might follow deterministic routes or Markov chains, or they may be reactive}, i.e., able to change their routes in order to avoid sensors placed to detect them. The challenge in such problems is to choose sensor locations economically, balancing security gains with costs, including the inconvenience sensors inflict upon innocent travelers. We study the objectives of 1) maximizing the number of evaders captured when limited by a budget on sensing cost and 2) capturing all evaders as cheaply as possible. We give optimal sensor placement algorithms for several classes of special graphs and hardness and approximation results for general graphs, including for deterministic or Markov chain-based and reactive or oblivious evaders. In a similar-sounding but fundamentally different problem setting posed by Rubinstein and Glazer where both evaders and innocent travelers are reactive, we again give optimal algorithms for special cases and hardness and approximation results on general graphs.

preprint2010arXiv

Modeling and Analysis of Time-Varying Graphs

We live in a world increasingly dominated by networks -- communications, social, information, biological etc. A central attribute of many of these networks is that they are dynamic, that is, they exhibit structural changes over time. While the practice of dynamic networks has proliferated, we lag behind in the fundamental, mathematical understanding of network dynamism. Existing research on time-varying graphs ranges from preliminary algorithmic studies (e.g., Ferreira's work on evolving graphs) to analysis of specific properties such as flooding time in dynamic random graphs. A popular model for studying dynamic graphs is a sequence of graphs arranged by increasing snapshots of time. In this paper, we study the fundamental property of reachability in a time-varying graph over time and characterize the latency with respect to two metrics, namely store-or-advance latency and cut-through latency. Instead of expected value analysis, we concentrate on characterizing the exact probability distribution of routing latency along a randomly intermittent path in two popular dynamic random graph models. Using this analysis, we characterize the loss of accuracy (in a probabilistic setting) between multiple temporal graph models, ranging from one that preserves all the temporal ordering information for the purpose of computing temporal graph properties to one that collapses various snapshots into one graph (an operation called smashing), with multiple intermediate variants. We also show how some other traditional graph theoretic properties can be extended to the temporal domain. Finally, we propose algorithms for controlling the progress of a packet in single-copy adaptive routing schemes in various dynamic random graphs.