3 Search Results for "Hildrum, Kirsten"

Document
DOI: 10.4230/LIPIcs.ESA.2025.76
A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs

Authors: Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, and Agnieszka Tatarczuk

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the List Update problem where the cost of each swap is assumed to be 1. This is in contrast to the "standard" model, in which an algorithm is allowed to swap the requested item with previous items for free. We construct an online algorithm Full-Or-Partial-Move (FPM), whose competitive ratio is at most 3.3904, improving over the previous best known bound of 4.
Cite as

Mateusz Basiak, Marcin Bienkowski, Martin Böhm, Marek Chrobak, Łukasz Jeż, Jiří Sgall, and Agnieszka Tatarczuk. A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{basiak_et_al:LIPIcs.ESA.2025.76,
  author =	{Basiak, Mateusz and Bienkowski, Marcin and B\"{o}hm, Martin and Chrobak, Marek and Je\.{z}, {\L}ukasz and Sgall, Ji\v{r}{\'\i} and Tatarczuk, Agnieszka},
  title =	{{A 3.3904-Competitive Online Algorithm for List Update with Uniform Costs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{76:1--76:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.76},
  URN =		{urn:nbn:de:0030-drops-245442},
  doi =		{10.4230/LIPIcs.ESA.2025.76},
  annote =	{Keywords: List update, work functions, amortized analysis, online algorithms, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.185
Scheduling with Setup Costs and Monotone Penalties

Authors: Rohit Khandekar, Kirsten Hildrum, Deepak Rajan, and Joel Wolf

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We consider single processor preemptive scheduling with job-dependent setup times. In this model, a job-dependent setup time is incurred when a job is started for the first time, and each time it is restarted after preemption. This model is a common generalization of preemptive scheduling, and actually of non-preemptive scheduling as well. The objective is to minimize the sum of any general non-negative, non-decreasing cost functions of the completion times of the jobs -- this generalizes objectives of minimizing weighted flow time, flow-time squared, tardiness or the number of tardy jobs among many others. Our main result is a randomized polynomial time O(1)-speed O(1)-approximation algorithm for this problem. Without speedup, no polynomial time finite multiplicative approximation is possible unless P=NP. We extend the approach of Bansal et al. (FOCS 2007) of rounding a linear programming relaxation which accounts for costs incurred due to the non-preemptive nature of the schedule. A key new idea used in the rounding is that a point in the intersection polytope of two matroids can be decomposed as a convex combination of incidence vectors of sets that are independent in both matroids. In fact, we use this for the intersection of a partition matroid and a laminar matroid, in which case the decomposition can be found efficiently using network flows. Our approach gives a randomized polynomial time offline O(1)-speed O(1)-approximation algorithm for the broadcast scheduling problem with general cost functions as well.
Cite as

Rohit Khandekar, Kirsten Hildrum, Deepak Rajan, and Joel Wolf. Scheduling with Setup Costs and Monotone Penalties. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 185-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{khandekar_et_al:LIPIcs.FSTTCS.2012.185,
  author =	{Khandekar, Rohit and Hildrum, Kirsten and Rajan, Deepak and Wolf, Joel},
  title =	{{Scheduling with Setup Costs and Monotone Penalties}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{185--198},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.185},
  URN =		{urn:nbn:de:0030-drops-38576},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.185},
  annote =	{Keywords: Scheduling, resource augmentation, approximation algorithm, preemption, setup times}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2009.2325
Bounded Size Graph Clustering with Applications to Stream Processing

Authors: Rohit Khandekar, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Jay Sethuraman, and Joel Wolf

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)

Abstract
We introduce a graph clustering problem motivated by a stream processing application. Input to our problem is an undirected graph with vertex and edge weights. A cluster is a subset of the vertices. The {\em size} of a cluster is defined as the total vertex weight in the subset plus the total edge weight at the boundary of the cluster. The bounded size graph clustering problem ($\GC$) is to partition the vertices into clusters of size at most a given budget and minimize the total edge-weight across the clusters. In the {\em multiway cut} version of the problem, we are also given a subset of vertices called {\em terminals}. No cluster is allowed to contain more than one terminal. Our problem differs from most of the previously studied clustering problems in that the number of clusters is not specified. We first show that the feasibility version of the multiway cut $\GC$ problem, i.e., determining if there exists a clustering with bounded-size clusters satisfying the multiway cut constraint, can be solved in polynomial time. Our algorithm is based on the min-cut subroutine and an uncrossing argument. This result is in contrast with the NP-hardness of the min-max multiway cut problem, considered by Svitkina and Tardos (2004), in which the number of clusters must equal the number of terminals. Our results for the feasibility version also generalize to any symmetric submodular function. We next show that the optimization version of $\GC$ is NP-hard by showing an approximation-preserving reduction from the $\frac 13$-balanced cut problem. Our main result is an $O(\log^2 n)$-approximation to the optimization version of the multiway cut $\GC$ problem violating the budget by an $O(\log n)$ factor, where $n$ denotes the number of vertices. Our algorithm is based on a set-cover-like greedy approach which iteratively computes bounded-size clusters to maximize the number of new vertices covered.
Cite as

Rohit Khandekar, Kirsten Hildrum, Sujay Parekh, Deepak Rajan, Jay Sethuraman, and Joel Wolf. Bounded Size Graph Clustering with Applications to Stream Processing. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 275-286, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{khandekar_et_al:LIPIcs.FSTTCS.2009.2325,
  author =	{Khandekar, Rohit and Hildrum, Kirsten and Parekh, Sujay and Rajan, Deepak and Sethuraman, Jay and Wolf, Joel},
  title =	{{Bounded Size Graph Clustering with Applications to Stream Processing}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{275--286},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2325},
  URN =		{urn:nbn:de:0030-drops-23250},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2325},
  annote =	{Keywords: Graph partitioning, uncrossing, Gomory-Hu trees, symmetric submodular functions}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2012
  • 1 2009

  • Refine by Author
  • 2 Hildrum, Kirsten
  • 2 Khandekar, Rohit
  • 2 Rajan, Deepak
  • 2 Wolf, Joel
  • 1 Basiak, Mateusz
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Gomory-Hu trees
  • 1 Graph partitioning
  • 1 List update
  • 1 Scheduling
  • 1 amortized analysis
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact