Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Meital Levy

dblp:89/5744 · DBLP profile ↗
← Back
9ranked-venue papers
0as first author
0since 2021 · last 2008
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 9

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
5 papers
Algorithmic game theory and mechanism design · 48% Computational geometry · 28% Approximation and online algorithms · 24%

Topics — the 8 heaviest of 10, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Approximation and online algorithms
online algorithms
0.232007
Online Conflict-Free Coloring for Intervals · SIAM J. Comput. 2007
Online conflict-free coloring for intervals · SODA 2005
Online Interval Coloring and Variants · ICALP 2005
Computational geometry › combinatorial geometry › geometric set systems
conflict-free coloring
0.122007
Online Conflict-Free Coloring for Intervals · SIAM J. Comput. 2007
Online conflict-free coloring for intervals · SODA 2005
Algorithmic game theory and mechanism design
price of anarchy
0.112007
Strong Price of Anarchy for Machine Load Balancing · ICALP 2007
Algorithmic game theory and mechanism design › price of anarchy
strong price of anarchy
0.112007
Strong Price of Anarchy for Machine Load Balancing · ICALP 2007
Algorithmic game theory and mechanism design › network games
network design game
0.112006
On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations · ICALP (1) 2006
Algorithmic game theory and mechanism design › price of anarchy
price of stability
0.112006
On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations · ICALP (1) 2006
Algorithmic game theory and mechanism design › cooperative game theory
cost sharing
0.012006
On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations · ICALP (1) 2006
Computational geometry › intersection graphs
interval graphs
0.012005
Online conflict-free coloring for intervals · SODA 2005

Methods — techniques the papers use, named apart from their topics

randomized algorithm · 0.1deterministic algorithm · 0.1
YearPublicationVenuePosition
2008 Caching Content under Digital Rights Management
Leah Epstein, Amos Fiat, Meital Levy
WAOA3
2008 Online interval coloring with packing constraints
Leah Epstein, Meital Levy
Theor. Comput. Sci.2
2007 Strong Price of Anarchy for Machine Load Balancing
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky
ICALP3
2007 Online Conflict-Free Coloring for Intervals
abstract
We consider an online version of the conflict‐free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict‐free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.
Ke Chen 0006, Amos Fiat, Haim Kaplan, Meital Levy, Jirí Matousek 0001, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner 0001, Emo Welzl
SIAM J. Comput.4
2006 On the Price of Stability for Designing Undirected Networks with Fair Cost Allocations
Amos Fiat, Haim Kaplan, Meital Levy, Svetlana Olonetsky, Ronen Shabo
ICALP (1)3
2006 An improved algorithm for online coloring of intervals with bandwidth
Yossi Azar, Amos Fiat, Meital Levy, N. S. Narayanaswamy
Theor. Comput. Sci.3
2005 Online Interval Coloring and Variants
Leah Epstein, Meital Levy
ICALP2
2005 Online Interval Coloring with Packing Constraints
Leah Epstein, Meital Levy
MFCS2
2005 Online conflict-free coloring for intervals
Amos Fiat, Meital Levy, Jirí Matousek 0001, Elchanan Mossel, János Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner 0001, Emo Welzl
SODA2