Danny Raz

SODA Conference 2023 Conference Paper

Almost Tight Bounds for Online Facility Location in the Random-Order Model

• Haim Kaplan
• David Naori
• Danny Raz

SODA Conference 2022 Conference Paper

Online Weighted Matching with a Sample

• Haim Kaplan
• David Naori
• Danny Raz

We study the greedy-based online algorithm for edge-weighted matching with (one-sided) vertex arrivals in bipartite graphs, and edge arrivals in general graphs. This algorithm was first studied more than a decade ago by Korula and Pál for the bipartite case in the random-order model. While the weighted bipartite matching problem is solved in the random-order model, this is not the case in recent and exciting online models in which the online player is provided with a sample, and the arrival order is adversarial. The greedy-based algorithm is arguably the most natural and practical algorithm to be applied in these models. Despite its simplicity and appeal, and despite being studied in multiple works, the greedy-based algorithm was not fully understood in any of the studied online models, and its actual performance remained an open question for more than a decade. We provide a thorough analysis of the greedy-based algorithm in several online models. For vertex arrivals in bipartite graphs, we characterize the exact competitive-ratio of this algorithm in the random-order model, for any arrival order of the vertices subsequent to the sampling phase (adversarial and random orders in particular). We use it to derive tight analysis in the recent adversarial-order model with a sample (AOS model) for any sample size, providing the first result in this model beyond the simple secretary problem. Then, we generalize and strengthen the black box method of converting results in the random-order model to single-sample prophet inequalities, and use it to derive the state-of-the-art single-sample prophet inequality for the problem. Finally, we use our new techniques to analyze the greedy-based algorithm for edge arrivals in general graphs and derive results in all the mentioned online models. In this case as well, we improve upon the state-of-the-art single-sample prophet inequality.

SODA Conference 2020 Conference Paper

Competitive Analysis with a Sample and the Secretary Problem

• Haim Kaplan
• David Naori
• Danny Raz

STOC Conference 2001 Conference Paper

Approximating min-sum k -clustering in metric spaces

• Yair Bartal
• Moses Charikar
• Danny Raz

STOC Conference 1997 Conference Paper

Approximating Total Flow Time on Parallel Machines

• Stefano Leonardi 0001
• Danny Raz

FOCS Conference 1997 Conference Paper

Global Optimization Using Local Information with Applications to Flow Control

• Yair Bartal
• John W. Byers
• Danny Raz

Flow control in high speed networks requires distributed routers to make fast decisions based only on local information in allocating bandwidth to connections. While most previous work on this problem focuses on achieving local objective functions, in many cases it may be necessary to achieve global objectives such as maximizing the total flow. This problem illustrates one of the basic aspects of distributed computing: achieving global objectives using local information. Papadimitriou and Yannakakis (1993) initiated the study of such problems in a framework of solving positive linear programs by distributed agents. We take their model further, by allowing the distributed agents to acquire more information over time. We therefore turn attention to the tradeoff between the running time and the quality of the solution to the linear program. We give a distributed algorithm that obtains a (1+/spl epsiv/) approximation to the global optimum solution and runs in a polylogarithmic number of distributed rounds. While comparable in running time, our results exhibit a significant improvement on the logarithmic ratio previously obtained by Awerbuch and Azar (1994). Our algorithm, which draws from techniques developed by Luby and Nisan (1993) is considerably simpler than previous approximation algorithms for positive linear programs, and thus may have practical value in both centralized and distributed settings.

TCS Journal 1997 Journal Article

Length considerations in context-free languages

• Danny Raz

FOCS Conference 1990 Conference Paper

Deciding Properties of Nonregular Programs (Preliminary Version)

• David Harel
• Danny Raz

The problem of deciding the validity of formulas in extensions of propositional dynamic logic (PDL) is considered. The extensions are obtained by adding programs defined by nonregular languages. In the past, a number of very simple languages were shown to render this problem highly undecidable, whereas other very similar-looking languages were shown to retain decidability. Understanding this rather strange phenomenon and generalizing the isolated extensions have remained elusive. The authors provide decision procedures for two wide classes of extensions, thus shedding light on the general problem. The proofs are novel, in that they explicitly consider the machines that accept the languages, in this case special classes of PDAs and stack automata. It is shown that the emptiness problem for stack automata on infinite trees is decidable, a result of independent interest, and the result is combined with the construction of certain tree models for the corresponding formulas. >