Author name cluster

Amir Epstein

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.

6 papers

2 author rows

NeurIPS Conference 2023 Conference Paper

Derandomized novelty detection with FDR control via conformal e-values

Meshi Bashari
Amir Epstein
Yaniv Romano
Matteo Sesia

Conformal inference provides a general distribution-free method to rigorously calibrate the output of any machine learning algorithm for novelty detection. While this approach has many strengths, it has the limitation of being randomized, in the sense that it may lead to different results when analyzing twice the same data and this can hinder the interpretation of any findings. We propose to make conformal inferences more stable by leveraging suitable conformal e-values instead of p-values to quantify statistical significance. This solution allows the evidence gathered from multiple analyses of the same data to be aggregated effectively while provably controlling the false discovery rate. Further, we show that the proposed method can reduce randomness without much loss of power compared to standard conformal inference, partly thanks to an innovative way of weighting conformal e-values based on additional side information carefully extracted from the same data. Simulations with synthetic and real data confirm this solution can be effective at eliminating random noise in the inferences obtained with state-of-the-art alternative techniques, sometimes also leading to higher power.

PDF Details

SODA Conference 2016 Conference Paper

Make-to-Order Integrated Scheduling and Distribution

Yossi Azar
Amir Epstein
Lukasz Jez
Adi Vardi

Production and distribution are fundamental operational functions in supply chains. The main challenge is to design algorithms that optimize operational performance by jointly scheduling production and delivery of customer orders. In this paper we study a model of scheduling customer orders on multiple identical machines and their distribution to customers afterwards. The goal is to minimize the total time from release to distribution plus total distribution cost to the customers. We design the first poly-logarithmic competitive algorithm for the problem, improving upon previous algorithms with linear competitive ratios. Our model generalizes two fundamental problems: scheduling of jobs on multiple identical machines (where the goal function is to minimize the total flow time) as well as the TCP Acknowledgment problem.

Details

STOC Conference 2006 Conference Paper

A quasi-PTAS for unsplittable flow on line graphs

Nikhil Bansal 0001
Amit Chakrabarti
Amir Epstein
Baruch Schieber

We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2 polylog(n) ). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs.Earlier results on this problem included a polynomial time (2+ε)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a super-constant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.

Details

TCS Journal 2006 Journal Article

Load balancing of temporary tasks in the ℓ p norm

Yossi Azar
Amir Epstein
Leah Epstein

We consider the on-line load balancing problem where there are m identical machines (servers). Jobs arrive at arbitrary times, where each job has a weight and a duration. A job has to be assigned upon its arrival to exactly one of the machines. The duration of each job becomes known only upon its termination (this is called temporary tasks of unknown durations). Once a job has been assigned to a machine it cannot be reassigned to another machine. The goal is to minimize the maximum over time of the sum (over all machines) of the squares of the loads, instead of the traditional maximum load. Minimizing the sum of the squares is equivalent to minimizing the load vector with respect to the ℓ 2 norm. We show that for the ℓ 2 norm the greedy algorithm performs within at most 1. 493 of the optimum. We show (an asymptotic) lower bound of 1. 33 on the competitive ratio of the greedy algorithm. We also show a lower bound of 1. 20 on the competitive ratio of any algorithm. We extend our techniques and analyze the competitive ratio of the greedy algorithm with respect to the ℓ p norm. We show that the greedy algorithm performs within at most 2 - Ω ( 1 / p ) of the optimum. We also show a lower bound of 2 - O ( ln p / p ) on the competitive ratio of any on-line algorithm.

Details DOI

STOC Conference 2005 Conference Paper

Convex programming for scheduling unrelated parallel machines

Yossi Azar
Amir Epstein

We consider the classical problem of scheduling parallel unrelated machines. Each job is to be processed by exactly one machine. Processing job j on machine i requires time p ij . The goal is to find a schedule that minimizes the l p norm. Previous work showed a 2-approximation algorithm for the problem with respect to the l ∞ norm. For any fixed l p norm the previously known approximation algorithm has a performance of θ(p). We provide a 2-approximation algorithm for any fixed l p norm (p>1). This algorithm uses convex programming relaxation. We also give a √ 2-approximation algorithm for the l 2 norm. This algorithm relies on convex quadratic programming relaxation. To the best of our knowledge, this is the first time that general convex programming techniques (apart from SDPs and CQPs) are used in the area of scheduling. We show for any given l p norm a PTAS for any fixed number of machines. We also consider the multidimensional generalization of the problem in which the jobs are d-dimensional. Here the goal is to minimize the l p norm of the generalized load vector, which is a matrix where the rows represent the machines and the columns represent the jobs dimension. For this problem we give a (d+1)-approximation algorithm for any fixed l p norm (p>1).

Details

STOC Conference 2005 Conference Paper

The Price of Routing Unsplittable Flow

Baruch Awerbuch
Yossi Azar
Amir Epstein

The essence of the routing problem in real networks is that the traffic demand from a source to destination must be satisfied by choosing a single path between source and destination. The splittable version of this problem is when demand can be satisfied by many paths, namely a flow from source to destination. The unsplittable, or discrete version of the problem is more realistic yet is more complex from the algorithmic point of view; in some settings optimizing such unsplittable traffic flow is computationally intractable.In this paper, we assume this more realistic unsplittable model, and investigate the "price of anarchy", or deterioration of network performance measured in total traffic latency under the selfish user behavior. We show that for linear edge latency functions the price of anarchy is exactly $2.618 for weighted demand and exactly $2.5 for unweighted demand. These results are easily extended to (weighted or unweighted) atomic "congestion games", where paths are replaced by general subsets. We also show that for polynomials of degree d edge latency functions the price of anarchy is d δ (d). Our results hold also for mixed strategies.Previous results of Roughgarden and Tardos showed that for linear edge latency functions the price of anarchy is exactly 4/3 under the assumption that each user controls only a negligible fraction of the overall traffic (this result also holds for the splittable case). Note that under the assumption of negligible traffic pure and mixed strategies are equivalent and also splittable and unsplittable models are equivalent.

Details