3 Search Results for "Stalfa, David"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2023.98
Scheduling Under Non-Uniform Job and Machine Delays

Authors: Rajmohan Rajaraman, David Stalfa, and Sheng Yang

Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)

Abstract
We study the problem of scheduling precedence-constrained jobs on heterogenous machines in the presence of non-uniform job and machine communication delays. We are given a set of n unit size precedence-ordered jobs, and a set of m related machines each with size m_i (machine i can execute at most m_i jobs at any time). Each machine i has an associated in-delay ρ^{in}_i and out-delay ρ^{out}_i. Each job v also has an associated in-delay ρ^{in}_v and out-delay ρ^{out}_v. In a schedule, job v may be executed on machine i at time t if each predecessor u of v is completed on i before time t or on any machine j before time t - (ρ^{in}_i + ρ^{out}_j + ρ^{out}_u + ρ^{in}_v). The objective is to construct a schedule that minimizes makespan, which is the maximum completion time over all jobs. We consider schedules which allow duplication of jobs as well as schedules which do not. When duplication is allowed, we provide an asymptotic polylog(n)-approximation algorithm. This approximation is further improved in the setting with uniform machine speeds and sizes. Our best approximation for non-uniform delays is provided for the setting with uniform speeds, uniform sizes, and no job delays. For schedules with no duplication, we obtain an asymptotic polylog(n)-approximation for the above model, and a true polylog(n)-approximation for symmetric machine and job delays. These results represent the first polylogarithmic approximation algorithms for scheduling with non-uniform communication delays. Finally, we consider a more general model, where the delay can be an arbitrary function of the job and the machine executing it: job v can be executed on machine i at time t if all of v’s predecessors are executed on i by time t-1 or on any machine by time t - ρ_{v,i}. We present an approximation-preserving reduction from the Unique Machines Precedence-constrained Scheduling (umps) problem, first defined in [Sami Davies et al., 2022], to this job-machine delay model. The reduction entails logarithmic hardness for this delay setting, as well as polynomial hardness if the conjectured hardness of umps holds. This set of results is among the first steps toward cataloging the rich landscape of problems in non-uniform delay scheduling.
Cite as

Rajmohan Rajaraman, David Stalfa, and Sheng Yang. Scheduling Under Non-Uniform Job and Machine Delays. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 98:1-98:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rajaraman_et_al:LIPIcs.ICALP.2023.98,
  author =	{Rajaraman, Rajmohan and Stalfa, David and Yang, Sheng},
  title =	{{Scheduling Under Non-Uniform Job and Machine Delays}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{98:1--98:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.98},
  URN =		{urn:nbn:de:0030-drops-181502},
  doi =		{10.4230/LIPIcs.ICALP.2023.98},
  annote =	{Keywords: Scheduling, Approximation Algorithms, Precedence Constraints, Communication Delay, Non-Uniform Delays}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.33
Finding Closed Quasigeodesics on Convex Polyhedra

Authors: Erik D. Demaine, Adam C. Hesterberg, and Jason S. Ku

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
A closed quasigeodesic is a closed loop on the surface of a polyhedron with at most 180° of surface on both sides at all points; such loops can be locally unfolded straight. In 1949, Pogorelov proved that every convex polyhedron has at least three (non-self-intersecting) closed quasigeodesics, but the proof relies on a nonconstructive topological argument. We present the first finite algorithm to find a closed quasigeodesic on a given convex polyhedron, which is the first positive progress on a 1990 open problem by O'Rourke and Wyman. The algorithm’s running time is pseudopolynomial, namely O(n²/ε² L/𝓁 b) time, where ε is the minimum curvature of a vertex, L is the length of the longest edge, 𝓁 is the smallest distance within a face between a vertex and a nonincident edge (minimum feature size of any face), and b is the maximum number of bits of an integer in a constant-size radical expression of a real number representing the polyhedron. We take special care in the model of computation and needed precision, showing that we can achieve the stated running time on a pointer machine supporting constant-time w-bit arithmetic operations where w = Ω(lg b).
Cite as

Erik D. Demaine, Adam C. Hesterberg, and Jason S. Ku. Finding Closed Quasigeodesics on Convex Polyhedra. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.SoCG.2020.33,
  author =	{Demaine, Erik D. and Hesterberg, Adam C. and Ku, Jason S.},
  title =	{{Finding Closed Quasigeodesics on Convex Polyhedra}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{33:1--33:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.33},
  URN =		{urn:nbn:de:0030-drops-121912},
  doi =		{10.4230/LIPIcs.SoCG.2020.33},
  annote =	{Keywords: polyhedra, geodesic, pseudopolynomial, geometric precision}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.77
Maximum Area Axis-Aligned Square Packings

Authors: Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. Tóth

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
Given a point set S={s_1,... , s_n} in the unit square U=[0,1]^2, an anchored square packing is a set of n interior-disjoint empty squares in U such that s_i is a corner of the ith square. The reach R(S) of S is the set of points that may be covered by such a packing, that is, the union of all empty squares anchored at points in S. It is shown that area(R(S))>= 1/2 for every finite set S subset U, and this bound is the best possible. The region R(S) can be computed in O(n log n) time. Finally, we prove that finding a maximum area anchored square packing is NP-complete. This is the first hardness proof for a geometric packing problem where the size of geometric objects in the packing is unrestricted.
Cite as

Hugo A. Akitaya, Matthew D. Jones, David Stalfa, and Csaba D. Tóth. Maximum Area Axis-Aligned Square Packings. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 77:1-77:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{akitaya_et_al:LIPIcs.MFCS.2018.77,
  author =	{Akitaya, Hugo A. and Jones, Matthew D. and Stalfa, David and T\'{o}th, Csaba D.},
  title =	{{Maximum Area Axis-Aligned Square Packings}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{77:1--77:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.77},
  URN =		{urn:nbn:de:0030-drops-96594},
  doi =		{10.4230/LIPIcs.MFCS.2018.77},
  annote =	{Keywords: square packing, geometric optimization}
}
  • Refine by Author
  • 2 Stalfa, David
  • 1 Akitaya, Hugo A.
  • 1 Demaine, Erik D.
  • 1 Hesterberg, Adam C.
  • 1 Jones, Matthew D.
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Scheduling algorithms

  • Refine by Keyword
  • 1 Approximation Algorithms
  • 1 Communication Delay
  • 1 Non-Uniform Delays
  • 1 Precedence Constraints
  • 1 Scheduling
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2018
  • 1 2020
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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