Author name cluster

Shahar Chen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

FOCS Conference 2016 Conference Paper

Online Algorithms for Covering and Packing Problems with Convex Objectives

Yossi Azar
Niv Buchbinder
T. -H. Hubert Chan
Shahar Chen
Ilan Reuven Cohen
Anupam Gupta 0001
Zhiyi Huang 0002
Ning Kang 0001

We present online algorithms for covering and packing problems with (non-linear) convex objectives. The convex covering problem is defined as: min xϵ R + n f(x) s. t. Ax ≥ 1, where f: R + n → R + is a monotone convex function, and A is an m×n matrix with non-negative entries. In the online version, a new row of the constraint matrix, representing a new covering constraint, is revealed in each step and the algorithm is required to maintain a feasible and monotonically non-decreasing assignment x over time. We also consider a convex packing problem defined as: max yϵR+ m Σ j=1 m yj - g(A T y), where g: R + n →R + is a monotone convex function. In the online version, each variable yj arrives online and the algorithm must decide the value of yj on its arrival. This represents the Fenchel dual of the convex covering program, when g is the convex conjugate of f. We use a primal-dual approach to give online algorithms for these generic problems, and use them to simplify, unify, and improve upon previous results for several applications.

Details

SODA Conference 2014 Conference Paper

Competitive Analysis via Regularization

Niv Buchbinder
Shahar Chen
Joseph Naor

We provide a framework for designing competitive online algorithms using regularization, a widely used technique in online learning, particularly in online convex optimization. An online algorithm that uses regularization serves requests by computing a solution, in each step, to an objective function involving a smooth convex regularization function. Applying the technique of regularization allows us to obtain new results in the domain of competitive analysis. We remark that competitive analysis and online learning are two widely studied frameworks for online decision-making settings. We show that even though there are significant differences in assumptions, goals, and techniques between the two fields, one can still benefit by introducing techniques from one field to the other. In our new framework we exhibit a general O (log m )-competitive deterministic algorithm for generating a fractional solution that satisfies a time-varying set of online covering and precedence constraints, where m is the number of variables. This framework allows to incorporate both service costs (over time) and setup costs into a host of applications. We then provide an O (log m log n )-competitive randomized algorithm for the online set cover problem with service cost, where m is the number of sets and n is the number of elements. This model allows for sets to be both added and deleted over time from a solution.

Details