Source author record

George Rabanca

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Computational Geometry Computer Science and Game Theory Discrete Mathematics

Catalog footprint

Research overview

4works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

The Densest k-Subhypergraph Problem

The Densest $k$ -Subgraph (D $k$ S) problem, and its corresponding minimization problem Smallest $p$ -Edge Subgraph (S $p$ ES), have come to play a central role in approximation algorithms. This is due both to their practical importance, and their usefulness as a tool for solving and establishing approximation bounds for other problems. These two problems are not well understood, and it is widely believed that they do not an admit a subpolynomial approximation ratio (although the best known hardness results do not rule this out). In this paper we generalize both D $k$ S and S $p$ ES from graphs to hypergraphs. We consider the Densest $k$ -Subhypergraph problem (given a hypergraph $(V, E)$ , find a subset $W\subseteq V$ of $k$ vertices so as to maximize the number of hyperedges contained in $W$ ) and define the Minimum $p$ -Union problem (given a hypergraph, choose $p$ of the hyperedges so as to minimize the number of vertices in their union). We focus in particular on the case where all hyperedges have size 3, as this is the simplest non-graph setting. For this case we provide an $O(n^{4(4-\sqrt{3})/13 + ε}) \leq O(n^{0.697831+ε})$ -approximation (for arbitrary constant $ε> 0$ ) for Densest $k$ -Subhypergraph and an $\tilde O(n^{2/5})$ -approximation for Minimum $p$ -Union. We also give an $O(\sqrt{m})$ -approximation for Minimum $p$ -Union in general hypergraphs. Finally, we examine the interesting special case of interval hypergraphs (instances where the vertices are a subset of the natural numbers and the hyperedges are intervals of the line) and prove that both problems admit an exact polynomial time solution on these instances.

preprint2016arXiv

Tight Approximation Bounds for the Seminar Assignment Problem

The seminar assignment problem is a variant of the generalized assignment problem in which items have unit size and the amount of space allowed in each bin is restricted to an arbitrary set of values. The problem has been shown to be NP-complete and to not admit a PTAS. However, the only constant factor approximation algorithm known to date is randomized and it is not guaranteed to always produce a feasible solution. In this paper we show that a natural greedy algorithm outputs a solution with value within a factor of $(1 - e^{-1})$ of the optimal, and that unless $NP\subseteq DTIME(n^{\log\log n})$ , this is the best approximation guarantee achievable by any polynomial time algorithm.

preprint2015arXiv

Covering the Boundary of a Simple Polygon with Geodesic Unit Disks

We consider the problem of covering the boundary of a simple polygon on n vertices using the minimum number of geodesic unit disks. We present an O(n \log^2 n+k) time 2-approximation algorithm for finding the centers of the disks, with k denoting the number centers found by the algorithm.

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.

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.