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

Irina Shapira

dblp:61/4045 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
0since 2021 · last 2006
—ORCID · none

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

Theory of computation · 2

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
2 papers
Mathematical optimization · 46% Approximation and online algorithms · 33% Graph algorithms and graph theory · 21%
Interdisciplinary, comprehensive, and emerging computing
1 paper
Bioinformatics and computational biology · 100%

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

TopicWeightPapersLastEvidence papers
Mathematical optimization › optimization
interval scheduling
0.122006
Scheduling Split Intervals · SIAM J. Comput. 2006
Scheduling split intervals · SODA 2002
Graph algorithms and graph theory
independent set
0.112006
Scheduling Split Intervals · SIAM J. Comput. 2006
Approximation and online algorithms
scheduling approximation
0.112006
Scheduling Split Intervals · SIAM J. Comput. 2006
Approximation and online algorithms
approximation algorithms
0.012002
Scheduling split intervals · SODA 2002
Mathematical optimization
scheduling
0.012002
Scheduling split intervals · SODA 2002
Bioinformatics and computational biology › sequence alignment
genomic sequence alignment
0.012006
Scheduling Split Intervals · SIAM J. Comput. 2006
Bioinformatics and computational biology
sequence alignment
0.012006
Scheduling Split Intervals · SIAM J. Comput. 2006

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

local ratio technique · 0.1fractional relaxation · 0.1approximation scheme · 0.1interval graph algorithms · 0.0
YearPublicationVenuePosition
2006 Scheduling Split Intervals
abstract
We consider the problem of scheduling jobs that are given as groups of nonintersecting segments on the real line. Each job $J_j$ is associated with an interval, $I_j$, which consists of up to t segments, for some $t \geq 1$, and a weight (profit), $w_j$; two jobs are in conflict if their intervals intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g., bandwidth in linear processor arrays), and computational biology/geometry. The objective is to schedule a subset of nonconflicting jobs of maximum total weight. Our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of $t=1$ is an ordinary interval graph). We show that, for $t \geq 2$, this problem is APX-hard, even for highly restricted instances. Our main result is a $2t$-approximation algorithm for general instances. This is based on a novel fractional version of the Local Ratio technique. One implication of this result is the first constant factor approximation for nonoverlapping alignment of genomic sequences. We also derive a bicriteria polynomial time approximation scheme for a restricted subclass of t-interval graphs.
Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira
SIAM J. Comput.5
2002 Scheduling split intervals
Reuven Bar-Yehuda, Magnús M. Halldórsson, Joseph Naor, Hadas Shachnai, Irina Shapira
SODA5