BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Joseph

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

ResearcherUnclaimed source record
Data Structures and AlgorithmsComputer Science and Game Theory

Catalog footprint

What is connected

8works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

8 published item(s)

preprint2022arXiv

Competitive Algorithms for Block-Aware Caching

We study the block-aware caching problem, a generalization of classic caching in which fetching (or evicting) pages from the same block incurs the same cost as fetching (or evicting) just one page from the block. Given a cache of size $k$, and a sequence of requests from $n$ pages partitioned into given blocks of size $β\leq k$, the goal is to minimize the total cost of fetching to (or evicting from) cache. We show the following results: $\bullet$ For the eviction cost model, we show an $O(\log k)$-approximate offline algorithm, a $k$-competitive deterministic online algorithm, and an $O(\log^2 k)$-competitive randomized online algorithm. $\bullet$ For the fetching cost model, we show an integrality gap of $Ω(β)$ for the natural LP relaxation of the problem, and an $Ω(β+ \log k)$ lower bound for randomized online algorithms. The strategy of ignoring the block-structure and running a classical paging algorithm trivially achieves an $O(β)$ approximation and an $O(β\log k)$ competitive ratio respectively for the offline and online-randomized setting. $\bullet$ For both fetching and eviction models, we show improved bounds for the $(h,k)$-bicriteria version of the problem. In particular, when $k=2h$, we match the performance of classical caching algorithms up to constant factors. Our results establish a separation between the tractability of the fetching and eviction cost models, which is interesting since fetching/evictions costs are the same up to an additive term for classic caching. Previous work only studied online deterministic algorithms for the fetching cost model when $k > h$. Our insight is to relax the block-aware caching problem to a submodular covering LP. The main technical challenge is to maintain a competitive fractional solution, and to round it with bounded loss, as the constraints of this LP are revealed online.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Timing Matters: Online Dynamics in Broadcast Games

A central question in algorithmic game theory is to measure the inefficiency (ratio of costs) of Nash equilibria (NE) with respect to socially optimal solutions. The two established metrics used for this purpose are price of anarchy (POA) and price of stability (POS), which respectively provide upper and lower bounds on this ratio. A deficiency of these metrics, however, is that they are purely existential and shed no light on which of the equilibrium states are reachable in an actual game, i.e., via natural game dynamics. This is particularly striking if these metrics differ significantly, such as in network design games where the exponential gap between the best and worst NE states originally prompted the notion of POS in game theory (Anshelevich et al., FOCS 2002). In this paper, we make progress toward bridging this gap by studying network design games under natural game dynamics. First we show that in a completely decentralized setting, where agents arrive, depart, and make improving moves in an arbitrary order, the inefficiency of NE attained can be polynomially large. This implies that the game designer must have some control over the interleaving of these events in order to force the game to attain efficient NE. We complement our negative result by showing that if the game designer is allowed to execute a sequence of improving moves to create an equilibrium state after every batch of agent arrivals or departures, then the resulting equilibrium states attained by the game are exponentially more efficient, i.e., the ratio of costs compared to the optimum is only logarithmic. Overall, our two results establish that in network games, the efficiency of equilibrium states is dictated by whether agents are allowed to join or leave the game in arbitrary states, an observation that might be useful in analyzing the dynamics of other classes of games with divergent POS and POA bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Near-Optimum Online Ad Allocation for Targeted Advertising

Motivated by Internet targeted advertising, we address several ad allocation problems. Prior work has established these problems admit no randomized online algorithm better than $(1-\frac{1}{e})$-competitive (\cite{karp1990optimal,mehta2007adwords}), yet simple heuristics have been observed to perform much better in practice. We explain this phenomenon by studying a generalization of the bounded-degree inputs considered by Buchbinder et al.~\cite{buchbinder2007online}, graphs which we call $(k,d)-bounded$. In such graphs the maximal degree on the online side is at most $d$ and the minimal degree on the offline side is at least $k$. We prove that for such graphs, these problems' natural greedy algorithms attain competitive ratio $1-\frac{d-1}{k+d-1}$, tending to \emph{one} as $d/k$ tends to zero. We prove this bound is tight for these algorithms. Next, we develop deterministic primal-dual algorithms for the above problems achieving competitive ratio $1-(1-\frac{1}{d})^k>1-\frac{1}{e^{k/d}}$, or \emph{exponentially} better loss as a function of $k/d$, and strictly better than $1-\frac{1}{e}$ whenever $k\geq d$. We complement our lower bounds with matching upper bounds for the vertex-weighted problem. Finally, we use our deterministic algorithms to prove by dual-fitting that simple randomized algorithms achieve the same bounds in expectation. Our algorithms and analysis differ from previous ad allocation algorithms, which largely scale bids based on the spent fraction of their bidder's budget, whereas we scale bids according to the number of times the bidder could have spent as much as her current bid. Our algorithms differ from previous online primal-dual algorithms, as they do not maintain dual feasibility, but only primal-to-dual ratio, and only attain dual feasibility upon termination. We believe our techniques could find applications to other well-behaved online packing problems.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Truthful Online Scheduling with Commitments

We study online mechanisms for preemptive scheduling with deadlines, with the goal of maximizing the total value of completed jobs. This problem is fundamental to deadline-aware cloud scheduling, but there are strong lower bounds even for the algorithmic problem without incentive constraints. However, these lower bounds can be circumvented under the natural assumption of deadline slackness, i.e., that there is a guaranteed lower bound $s > 1$ on the ratio between a job's size and the time window in which it can be executed. In this paper, we construct a truthful scheduling mechanism with a constant competitive ratio, given slackness $s > 1$. Furthermore, we show that if $s$ is large enough then we can construct a mechanism that also satisfies a commitment property: it can be determined whether or not a job will finish, and the requisite payment if so, well in advance of each job's deadline. This is notable because, in practice, users with strict deadlines may find it unacceptable to discover only very close to their deadline that their job has been rejected.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Online Packing and Covering Framework with Convex Objectives

We consider online fractional covering problems with a convex objective, where the covering constraints arrive over time. Formally, we want to solve $\min\,\{f(x) \mid Ax\ge \mathbf{1},\, x\ge 0\},$ where the objective function $f:\mathbb{R}^n\rightarrow \mathbb{R}$ is convex, and the constraint matrix $A_{m\times n}$ is non-negative. The rows of $A$ arrive online over time, and we wish to maintain a feasible solution $x$ at all times while only increasing coordinates of $x$. We also consider "dual" packing problems of the form $\max\,\{c^\intercal y - g(μ) \mid A^\intercal y \le μ,\, y\ge 0\}$, where $g$ is a convex function. In the online setting, variables $y$ and columns of $A^\intercal$ arrive over time, and we wish to maintain a non-decreasing solution $(y,μ)$. We provide an online primal-dual framework for both classes of problems with competitive ratio depending on certain "monotonicity" and "smoothness" parameters of $f$; our results match or improve on guarantees for some special classes of functions $f$ considered previously. Using this fractional solver with problem-dependent randomized rounding procedures, we obtain competitive algorithms for the following problems: online covering LPs minimizing $\ell_p$-norms of arbitrary packing constraints, set cover with multiple cost functions, capacity constrained facility location, capacitated multicast problem, set cover with set requests, and profit maximization with non-separable production costs. Some of these results are new and others provide a unified view of previous results, with matching or slightly worse competitive ratios.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints

Consider the following online version of the submodular maximization problem under a matroid constraint: We are given a set of elements over which a matroid is defined. The goal is to incrementally choose a subset that remains independent in the matroid over time. At each time, a new weighted rank function of a different matroid (one per time) over the same elements is presented; the algorithm can add a few elements to the incrementally constructed set, and reaps a reward equal to the value of the new weighted rank function on the current set. The goal of the algorithm as it builds this independent set online is to maximize the sum of these (weighted rank) rewards. As in regular online analysis, we compare the rewards of our online algorithm to that of an offline optimum, namely a single independent set of the matroid that maximizes the sum of the weighted rank rewards that arrive over time. This problem is a natural extension of two well-studied streams of earlier work: the first is on online set cover algorithms (in particular for the max coverage version) while the second is on approximately maximizing submodular functions under a matroid constraint. In this paper, we present the first randomized online algorithms for this problem with poly-logarithmic competitive ratio. To do this, we employ the LP formulation of a scaled reward version of the problem. Then we extend a weighted-majority type update rule along with uncrossing properties of tight sets in the matroid polytope to find an approximately optimal fractional LP solution. We use the fractional solution values as probabilities for a online randomized rounding algorithm. To show that our rounding produces a sufficiently large reward independent set, we prove and use new covering properties for randomly rounded fractional solutions in the matroid polytope that may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Polylogarithmic-Competitive Algorithm for the k-Server Problem

We give the first polylogarithmic-competitive randomized online algorithm for the $k$-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of O(log^3 n log^2 k log log n) for any metric space on n points. Our algorithm improves upon the deterministic (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou [J.ACM'95] whenever n is sub-exponential in k.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Min-Max Graph Partitioning and Small Set Expansion

We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are where the k parts need to be of equal-size, and where they must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an $O(\sqrt{\log n\log k})$-approximation algorithm. This improves over an $O(\log^2 n)$ approximation for the second version, and roughly $O(k\log n)$ approximation for the first version that follows from other previous work. We also give an improved O(1)-approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the Small-Set Expansion problem. In this problem, we are given a graph G and the goal is to find a non-empty set $S\subseteq V$ of size $|S| \leq ρn$ with minimum edge-expansion. We give an $O(\sqrt{\log{n}\log{(1/ρ)}})$ bicriteria approximation algorithm for the general case of Small-Set Expansion, and O(1) approximation algorithm for graphs that exclude any fixed minor.

0 citations0 reviewsNo code linkedOpen access