Found 11 Possible Name Variants:

Document

**Published in:** LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

We consider the problem of online dynamic power management that provides hard real-time guarantees for multi-processor systems. In this problem, a set of jobs, each associated with an arrival time, a deadline, and an execution time, arrives to the system in an online fashion. The objective is to compute a non-migrative preemptive schedule of the jobs and a sequence of power on/off operations of the processors so as to minimize the total energy consumption while ensuring that all the deadlines of the jobs are met. We assume that we can use as many processors as necessary. In this paper we examine the complexity of this problem and provide online strategies that lead to practical energy-efficient solutions for real-time multi-processor systems.
First, we consider the case for which we know in advance that the set of jobs can be scheduled feasibly on a single processor. We show that, even in this case, the competitive factor of any online algorithm is at least 2.06. On the other hand, we give a 4-competitive online algorithm that uses at most two processors. For jobs with unit execution times, the competitive factor of this algorithm improves to 3.59.
Second, we relax our assumption by considering as input multiple streams of jobs, each of which can be scheduled feasibly on a single processor. We present a trade-off between the energy-efficiency of the schedule and the number of processors to be used. More specifically, for k given job streams and h processors with h>k, we give a scheduling strategy such that the energy usage is at most 4.k/(h-k) times that used by any schedule which schedules each of the k streams on a separate processor. Finally, we drop the assumptions on the input set of jobs. We show that the competitive factor of any online algorithm is at least 2.28, even for the case of unit job execution times for which we further derive an O(1)-competitive algorithm.

Jian-Jia Chen, Mong-Jen Kao, D.T. Lee, Ignaz Rutter, and Dorothea Wagner. Online Dynamic Power Management with Hard Real-Time Guarantees. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 226-238, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2014.226, author = {Chen, Jian-Jia and Kao, Mong-Jen and Lee, D.T. and Rutter, Ignaz and Wagner, Dorothea}, title = {{Online Dynamic Power Management with Hard Real-Time Guarantees}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {226--238}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.226}, URN = {urn:nbn:de:0030-drops-44607}, doi = {10.4230/LIPIcs.STACS.2014.226}, annote = {Keywords: Energy-Efficient Scheduling, Online Dynamic Power Management} }

Document

**Published in:** LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

We consider the partial vertex cover problem with hard capacity constraints (Partial VC-HC) on hypergraphs. In this problem we are given a hypergraph G=(V,E) with a maximum edge size f and a covering requirement R. Each edge is associated with a demand, and each vertex is associated with a capacity and an (integral) available multiplicity. The objective is to compute a minimum vertex multiset such that at least R units of demand from the edges are covered by the capacities of the vertices in the multiset and the multiplicity of each vertex does not exceed its available multiplicity.
In this paper we present an f-approximation for this problem, improving over a previous result of (2f+2)(1+epsilon) by Cheung et al to the tight extent possible. Our new ingredient of this work is a generalized analysis on the extreme points of the natural LP, developed from previous works, and a strengthened LP lower-bound obtained for the optimal solutions.

Jia-Yau Shiau, Mong-Jen Kao, Ching-Chi Lin, and D. T. Lee. Tight Approximation for Partial Vertex Cover with Hard Capacities. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 64:1-64:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{shiau_et_al:LIPIcs.ISAAC.2017.64, author = {Shiau, Jia-Yau and Kao, Mong-Jen and Lin, Ching-Chi and Lee, D. T.}, title = {{Tight Approximation for Partial Vertex Cover with Hard Capacities}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {64:1--64:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.64}, URN = {urn:nbn:de:0030-drops-82694}, doi = {10.4230/LIPIcs.ISAAC.2017.64}, annote = {Keywords: Approximation Algorithm, Capacitated Vertex Cover, Hard Capacities} }

Document

**Published in:** LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

We consider capacitated vertex cover with hard capacity constraints (VC-HC) on hypergraphs. In this problem we are given a hypergraph G = (V, E) with a maximum edge size f. Each edge is associated with a demand and each vertex is associated with a weight (cost), a capacity, and an available multiplicity. The objective is to find a minimum-weight vertex multiset such that the demands of the edges can be covered by the capacities of the vertices and the multiplicity of each vertex does not exceed its available multiplicity.
In this paper we present an O(f) bi-approximation for VC-HC that gives a trade-off on the number of augmented multiplicity and the cost of the resulting cover. In particular, we show that, by augmenting the available multiplicity by a factor of k geq 2, a cover with a cost ratio of (1+ frac{1}{k - 1})(f - 1) to the optimal cover for the original instance can be obtained. This improves over a previous result, which has a cost ratio of f^2 via augmenting the available multiplicity by a factor of f.

Mong-Jen Kao, Hai-Lun Tu, and D. T. Lee. O(f) Bi-Approximation for Capacitated Covering with Hard Capacities. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 40:1-40:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kao_et_al:LIPIcs.ISAAC.2016.40, author = {Kao, Mong-Jen and Tu, Hai-Lun and Lee, D. T.}, title = {{O(f) Bi-Approximation for Capacitated Covering with Hard Capacities}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {40:1--40:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.40}, URN = {urn:nbn:de:0030-drops-68102}, doi = {10.4230/LIPIcs.ISAAC.2016.40}, annote = {Keywords: Capacitated Covering, Hard Capacities, Bi-criteria Approximation} }

Document

**Published in:** LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

We study integrality gap (IG) lower bounds on strong LP and SDP relaxations derived by the Sherali-Adams (SA), Lovász-Schrijver-SDP (LS_+), and Sherali-Adams-SDP (SA_+) lift-and-project (L&P) systems for the t-Partial-Vertex-Cover (t-PVC) problem, a variation of the classic Vertex-Cover problem in which only t edges need to be covered. t-PVC admits a 2-approximation using various algorithmic techniques, all relying on a natural LP relaxation. Starting from this LP relaxation, our main results assert that for every epsilon>0, level-Theta(n) LPs or SDPs derived by all known L&P systems that have been used for positive algorithmic results (but the Lasserre hierarchy) have IGs at least (1-epsilon)n/t, where n is the number of vertices of the input graph. Our lower bounds are nearly tight, in that level-n relaxations, even of the weakest systems, have integrality gap 1.
As lift-and-project systems have given the best algorithms known for numerous combinatorial optimization problems, our results show that restricted yet powerful models of computation derived by many L&P systems fail to witness c-approximate solutions to t-PVC for any constant c, and for t=O(n). This is one of the very few known examples of an intractable combinatorial optimization problem for which LP-based algorithms induce a constant approximation ratio, still lift-and-project LP and SDP tightenings of the same LP have unbounded IGs.
As further motivation for our results, we show that the SDP that has given the best algorithm known for t-PVC has integrality gap n/t on instances that can be solved by the level-1 LP relaxation derived by the LS system. This constitutes another rare phenomenon where (even in specific instances) a static LP outperforms an SDP that has been used for the best approximation guarantee for the problem at hand.
Finally, we believe our results are of independent interest as they are among the very few known integrality gap lower bounds for LP and SDP 0-1 relaxations in which not all variables possess the same semantics in the underlying combinatorial optimization problem. Most importantly, one of our main contributions is that we make explicit of a new and simple methodology of constructing solutions to LP relaxations that almost trivially satisfy constraints derived by all SDP L&P systems known to be useful for algorithmic positive results (except the La system). The latter sheds some light as to why La tightenings seem strictly stronger than LS_+ or SA_+ tightenings.

Konstantinos Georgiou and Edward Lee. Lift & Project Systems Performing on the Partial Vertex Cover Polytope. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 199-211, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{georgiou_et_al:LIPIcs.FSTTCS.2014.199, author = {Georgiou, Konstantinos and Lee, Edward}, title = {{Lift \& Project Systems Performing on the Partial Vertex Cover Polytope}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {199--211}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.199}, URN = {urn:nbn:de:0030-drops-48437}, doi = {10.4230/LIPIcs.FSTTCS.2014.199}, annote = {Keywords: Partial vertex cover, combinatorial optimization, linear programming, semidefinite programming, lift and project systems, integrality gaps} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 9481, SYNCHRON 2009

The 16th SYNCHRON workshop has been organized as Dagstuhl seminar 09481
from November 22-27, 2009. Online material of the seminar is available at the
following web page:
http://www.dagstuhl.de/de/programm/kalender/semhp/?semnr=09481

Albert Benveniste, Stephen A. Edwards, Edward Lee, Klaus Schneider, and Reinhard von Hanxleden. 09481 Abstracts Collection – SYNCHRON 2009. In SYNCHRON 2009. Dagstuhl Seminar Proceedings, Volume 9481, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{benveniste_et_al:DagSemProc.09481.1, author = {Benveniste, Albert and Edwards, Stephen A. and Lee, Edward and Schneider, Klaus and von Hanxleden, Reinhard}, title = {{09481 Abstracts Collection – SYNCHRON 2009}}, booktitle = {SYNCHRON 2009}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9481}, editor = {Albert Benveniste and Stephen A. Edwards and Edward Lee and Klaus Schneider and Reinhard von Hanxleden}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09481.1}, URN = {urn:nbn:de:0030-drops-24340}, doi = {10.4230/DagSemProc.09481.1}, annote = {Keywords: Synchronous languages, Safety-critical real-time systems, Model-based design, Discrete and hybrid systems, Combining synchronous and asynchronous models, Formally consistent subsetting of UML, High-level hardware modeling and synthesis, Compilation and code synthesis for embedded systems} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7451, Model-Based Engineering of Embedded Real-Time Systems (2007)

From 04.11. to 09.11.2007, the Dagstuhl Seminar 07451 ``Model-Based Engineering of Embedded Real-Time Systems'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl.
During the seminar, several participants presented their current
research, and ongoing work and open problems were discussed. Abstracts of
the presentations given during the seminar as well as abstracts of
seminar results and ideas are put together in this paper. The first section
describes the seminar topics and goals in general.
Links to extended abstracts or full papers are provided, if available.

Holger Giese, Gabor Karsai, Edward Lee, Bernhard Rumpe, and Bernhard Schätz. 07451 Abstracts Collection – Model-Based Engineering of Embedded Real-Time Systems. In Model-Based Engineering of Embedded Real-Time Systems. Dagstuhl Seminar Proceedings, Volume 7451, pp. 1-14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{giese_et_al:DagSemProc.07451.1, author = {Giese, Holger and Karsai, Gabor and Lee, Edward and Rumpe, Bernhard and Sch\"{a}tz, Bernhard}, title = {{07451 Abstracts Collection – Model-Based Engineering of Embedded Real-Time Systems}}, booktitle = {Model-Based Engineering of Embedded Real-Time Systems}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7451}, editor = {Holger Giese and Gabor Karsai and Edward Lee and Bernhard Rumpe and Bernhard Sch\"{a}tz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07451.1}, URN = {urn:nbn:de:0030-drops-12718}, doi = {10.4230/DagSemProc.07451.1}, annote = {Keywords: Models, model-based, MDD, embedded systems, real-time systems, validation \& verification, tool-support, domain-specific, languages} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 7451, Model-Based Engineering of Embedded Real-Time Systems (2007)

Today, embedded software plays a central role in most advanced technical systems such as airplanes, cell phones, and cars, and has become the main driver for innovation. Development, evolution, configuration and maintenance of embedded and distributed software nowadays often are serious challenges as a drastic increase of the software complexity can be observed in practice. The application of model-based engineering technologies to embedded real-time systems seems to be a good candidate to tackle some of the resulting problems.

Holger Giese, Gabor Karsai, Edward Lee, Bernhard Rumpe, and Bernhard Schätz. 07451 Summary – Model-Based Engineering of Embedded Real-Time Systems. In Model-Based Engineering of Embedded Real-Time Systems. Dagstuhl Seminar Proceedings, Volume 7451, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{giese_et_al:DagSemProc.07451.2, author = {Giese, Holger and Karsai, Gabor and Lee, Edward and Rumpe, Bernhard and Sch\"{a}tz, Bernhard}, title = {{07451 Summary – Model-Based Engineering of Embedded Real-Time Systems}}, booktitle = {Model-Based Engineering of Embedded Real-Time Systems}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7451}, editor = {Holger Giese and Gabor Karsai and Edward Lee and Bernhard Rumpe and Bernhard Sch\"{a}tz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07451.2}, URN = {urn:nbn:de:0030-drops-12720}, doi = {10.4230/DagSemProc.07451.2}, annote = {Keywords: Models, model-based, MDD, embedded systems, real-time systems, validation \& verification, tool-support, domain-specific languages} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10401, Learning, Planning and Sharing Robot Knowledge for Human-Robot Interaction (2011)

The objective of this project is to define a science which allows for the evolution of complex software systems that can fully utilize massively parallel computers of ever-greater capability (initially dual quad cores running fewer higher-level sensors for tractability) and employ this design in human-robot interaction with a final goal of full autonomy of the robot (in this case, an unmanned helicopter). In order to test a new learning approach that can bestow intelligence on a system, based upon human (tutor) – robot (student) interaction, we are working jointly to design an intelligent system architecture, based on the KASER (Knowledge Amplification by Structural Expert Randomization), and plan to implement the methodology on an aerial vehicle (a helicopter), which will execute several maneuvers such as basic hovering, steep approach, confined area approach, and basic altitude flying. The software to perform these maneuvers will be developed using two methods (teach mode with a human-in-the-loop) and classical control. Then, the knowledge amplification system will autonomously generate another set of software, which will then be tested and compared to the execution of the baseline two software codes using the same helicopter flight scenarios. We anticipate that such complex functional real-time software can be most cost-effectively written through the use of a software-writing system embodying knowledge amplification.

Stuart H. Rubin and Gordon K. Lee. Intelligent Guidance of an Unmanned Helicopter. In Learning, Planning and Sharing Robot Knowledge for Human-Robot Interaction. Dagstuhl Seminar Proceedings, Volume 10401, pp. 1-9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{rubin_et_al:DagSemProc.10401.4, author = {Rubin, Stuart H. and Lee, Gordon K.}, title = {{Intelligent Guidance of an Unmanned Helicopter}}, booktitle = {Learning, Planning and Sharing Robot Knowledge for Human-Robot Interaction}, pages = {1--9}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2011}, volume = {10401}, editor = {Rachid Alami and R\"{u}diger Dillmann and Thomas C. Henderson and Alexandra Kirsch}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10401.4}, URN = {urn:nbn:de:0030-drops-29302}, doi = {10.4230/DagSemProc.10401.4}, annote = {Keywords: Evolution, Heuristics, KASER, System of Systems, Unmanned Helicopter} }

Document

**Published in:** OASIcs, Volume 108, Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)

The use of a real-time operating system (RTOS) raises the abstraction level for embedded systems design when compared to traditional bare-metal programming, resulting in simpler and more reusable application code. Modern RTOSes for resource-constrained platforms, like Zephyr and FreeRTOS, also offer threading support, but this kind of shared memory concurrency is a poor fit for expressing the reactive and interactive behaviors that are common in embedded systems. To address this, alternative concurrency models like the actor model or communicating sequential processes have been proposed. While those alternatives enable reactive design patterns, they fail to deliver determinism and do not address timing. This makes it difficult to verify that implemented behavior is as intended and impossible to specify timing constraints in a portable way. This makes it hard to create reusable library components out of common embedded design patterns, forcing developers to keep reinventing the wheel for each application and each platform. In this paper, we introduce the embedded target of Lingua Franca (LF) as a means to move beyond the threaded programming model provided by RTOSes and improve the state of the art in embedded programming. LF is based on the reactor model of computation, which is reactive, deterministic, and timed, providing a means to express concurrency and timing in a platform-independent way. We compare the performance of LF versus threaded C code - both running on Zephyr - in terms of response time, timing precision, throughput, and memory footprint.

Erling Rennemo Jellum, Shaokai Lin, Peter Donovan, Efsane Soyer, Fuzail Shakir, Torleiv Bryne, Milica Orlandic, Marten Lohstroh, and Edward A. Lee. Beyond the Threaded Programming Model on Real-Time Operating Systems. In Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023). Open Access Series in Informatics (OASIcs), Volume 108, pp. 3:1-3:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jellum_et_al:OASIcs.NG-RES.2023.3, author = {Jellum, Erling Rennemo and Lin, Shaokai and Donovan, Peter and Soyer, Efsane and Shakir, Fuzail and Bryne, Torleiv and Orlandic, Milica and Lohstroh, Marten and Lee, Edward A.}, title = {{Beyond the Threaded Programming Model on Real-Time Operating Systems}}, booktitle = {Fourth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2023)}, pages = {3:1--3:13}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-268-6}, ISSN = {2190-6807}, year = {2023}, volume = {108}, editor = {Terraneo, Federico and Cattaneo, Daniele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2023.3}, URN = {urn:nbn:de:0030-drops-177348}, doi = {10.4230/OASIcs.NG-RES.2023.3}, annote = {Keywords: Real time, concurrency, reactors, Lingua Franca, RTOS} }

Document

**Published in:** Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)

Edward A. Lee, Giovanni de Micheli, Wofgang Rosenstiel, and Lothar Thiele. Design Automation for Embedded Systems (Dagstuhl Seminar 9617). Dagstuhl Seminar Report 143, pp. 1-25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (1997)

Copy BibTex To Clipboard

@TechReport{lee_et_al:DagSemRep.143, author = {Lee, Edward A. and de Micheli, Giovanni and Rosenstiel, Wofgang and Thiele, Lothar}, title = {{Design Automation for Embedded Systems (Dagstuhl Seminar 9617)}}, pages = {1--25}, ISSN = {1619-0203}, year = {1997}, type = {Dagstuhl Seminar Report}, number = {143}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.143}, URN = {urn:nbn:de:0030-drops-150305}, doi = {10.4230/DagSemRep.143}, }

Document

**Published in:** LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

In recent years the study of probabilistic transition systems has shifted to transition relations over distributions to allow for a smooth adaptation of the standard non-probabilistic apparatus. In this paper we study transition relations over probability distributions in a setting with internal actions. We provide new logics that characterize probabilistic strong, weak and branching bisimulation. Because these semantics may be considered too strong in the probabilistic context, Eisentraut et al. recently proposed weak distribution bisimulation. To show the flexibility of our approach based on the framework of van Glabbeek for the non-deterministic setting, we provide a novel logical characterization for the latter probabilistic equivalence as well.

Matias David Lee and Erik P. de Vink. Logical Characterization of Bisimulation for Transition Relations over Probability Distributions with Internal Actions. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 29:1-29:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.MFCS.2016.29, author = {Lee, Matias David and de Vink, Erik P.}, title = {{Logical Characterization of Bisimulation for Transition Relations over Probability Distributions with Internal Actions}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {29:1--29:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.29}, URN = {urn:nbn:de:0030-drops-64441}, doi = {10.4230/LIPIcs.MFCS.2016.29}, annote = {Keywords: probabilistic transition systems, weak bisimulations, logical characterization, transition relation over distributions, modal logics} }

Document

Complete Volume

**Published in:** LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

LIPIcs, Volume 123, ISAAC'18, Complete Volume

Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao. LIPIcs, Volume 123, ISAAC'18, Complete Volume. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Proceedings{hsu_et_al:LIPIcs.ISAAC.2018, title = {{LIPIcs, Volume 123, ISAAC'18, Complete Volume}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2019}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018}, URN = {urn:nbn:de:0030-drops-101600}, doi = {10.4230/LIPIcs.ISAAC.2018}, annote = {Keywords: Mathematics of computing, Theory of computation, Data structures design and analysis, Computing methodologies} }

Document

Front Matter

**Published in:** LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Front Matter, Table of Contents, Preface, Conference Organization

Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao. Front Matter, Table of Contents, Preface, Conference Organization. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 0:i-0:xviii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hsu_et_al:LIPIcs.ISAAC.2018.0, author = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {0:i--0:xviii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.0}, URN = {urn:nbn:de:0030-drops-99488}, doi = {10.4230/LIPIcs.ISAAC.2018.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }

Document

**Published in:** LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

In 1982, Drezner proposed the (1|1)-centroid problem on the plane, in which two players, called the leader and the follower, open facilities to provide service to customers in a competitive manner. The leader opens the first facility, and then the follower opens the second. Each customer will patronize the facility closest to him (ties broken in favor of the leader's one), thereby decides the market share of the two players. The goal is to find the best position for the leader’s facility so that his market share is maximized. The best algorithm for this problem is an O(n^2 log n)-time parametric search approach, which searches over the space of possible market share values.
In the same paper, Drezner also proposed a general version of (1|1)-centroid problem by introducing a minimal distance constraint R, such that the follower's facility is not allowed to be located within a distance R from the leader's. He proposed an O(n^5 log n)-time algorithm for this general version by identifying O(n^4) points as the candidates of the optimal solution and checking the market share for each of them. In this paper, we develop a new parametric search approach searching over the O(n^4) candidate points, and present an O(n^2 log n)-time algorithm for the general version, thereby closing the O(n^3) gap between the two bounds.

Hung-I Yu, Tien-Ching Lin, and Der-Tsai Lee. The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 64:1-64:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yu_et_al:LIPIcs.ISAAC.2016.64, author = {Yu, Hung-I and Lin, Tien-Ching and Lee, Der-Tsai}, title = {{The (1|1)-Centroid Problem on the Plane Concerning Distance Constraints}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {64:1--64:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.64}, URN = {urn:nbn:de:0030-drops-68337}, doi = {10.4230/LIPIcs.ISAAC.2016.64}, annote = {Keywords: competitive facility, Euclidean plane, parametric search} }

Document

**Published in:** LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

We consider the family of Phi-Subset problems, where the input consists of an instance I of size N over a universe U_I of size n and the task is to check whether the universe contains a subset with property Phi (e.g., Phi could be the property of being a feedback vertex set for the input graph of size at most k). Our main tool is a simple randomized algorithm which solves Phi-Subset in time (1+b-(1/c))^n N^(O(1)), provided that there is an algorithm for the Phi-Extension problem with running time b^{n-|X|} c^k N^{O(1)}. Here, the input for Phi-Extension is an instance I of size N over a universe U_I of size n, a subset X \subseteq U_I, and an integer k, and the task is to check whether there is a set Y with X \subseteq Y \subseteq U_I and |Y \ X| <= k with property Phi.
We derandomize this algorithm at the cost of increasing the running time by a subexponential factor in n, and we adapt it to the enumeration setting where we need to enumerate all subsets of the universe with property Phi. This generalizes the results of Fomin et al. [STOC 2016] who proved the case where b=1.
As case studies, we use these results to design faster deterministic algorithms for:
- checking whether a graph has a feedback vertex set of size at most k
- enumerating all minimal feedback vertex sets
- enumerating all minimal vertex covers of size at most k, and
- enumerating all minimal 3-hitting sets.
We obtain these results by deriving new b^{n-|X|} c^k N^{O(1)}-time algorithms for the corresponding Phi-Extension problems (or enumeration variant). In some cases, this is done by adapting the analysis of an existing algorithm, or in other cases by designing a new algorithm. Our analyses are based on Measure and Conquer, but the value to minimize, 1+b-(1/c), is unconventional and requires non-convex optimization.

Serge Gaspers and Edward J. Lee. Exact Algorithms via Multivariate Subroutines. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 69:1-69:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gaspers_et_al:LIPIcs.ICALP.2017.69, author = {Gaspers, Serge and Lee, Edward J.}, title = {{Exact Algorithms via Multivariate Subroutines}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {69:1--69:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.69}, URN = {urn:nbn:de:0030-drops-74251}, doi = {10.4230/LIPIcs.ICALP.2017.69}, annote = {Keywords: enumeration algorithms, exponential time algorithms, feedback vertex set, hitting set} }

Document

**Published in:** LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Filters are small, fast, and approximate set membership data structures. They are often used to filter out expensive accesses to a remote set S for negative queries (that is, filtering out queries x ∉ S). Filters have one-sided errors: on a negative query, a filter may say "present" with a tunable false-positive probability of ε. Correctness is traded for space: filters only use log (1/ε) + O(1) bits per element.
The false-positive guarantees of most filters, however, hold only for a single query. In particular, if x is a false positive, a subsequent query to x is a false positive with probability 1, not ε. With this in mind, recent work has introduced the notion of an adaptive filter. A filter is adaptive if each query is a false positive with probability ε, regardless of answers to previous queries. This requires "fixing" false positives as they occur.
Adaptive filters not only provide strong false positive guarantees in adversarial environments but also improve query performance on practical workloads by eliminating repeated false positives.
Existing work on adaptive filters falls into two categories. On the one hand, there are practical filters, based on the cuckoo filter, that attempt to fix false positives heuristically without meeting the adaptivity guarantee. On the other hand, the broom filter is a very complex adaptive filter that meets the optimal theoretical bounds.
In this paper, we bridge this gap by designing the telescoping adaptive filter (TAF), a practical, provably adaptive filter. We provide theoretical false-positive and space guarantees for our filter, along with empirical results where we compare its performance against state-of-the-art filters. We also implement the broom filter and compare it to the TAF. Our experiments show that theoretical adaptivity can lead to improved false-positive performance on practical inputs, and can be achieved while maintaining throughput that is similar to non-adaptive filters.

David J. Lee, Samuel McCauley, Shikha Singh, and Max Stein. Telescoping Filter: A Practical Adaptive Filter. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 60:1-60:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.ESA.2021.60, author = {Lee, David J. and McCauley, Samuel and Singh, Shikha and Stein, Max}, title = {{Telescoping Filter: A Practical Adaptive Filter}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {60:1--60:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.60}, URN = {urn:nbn:de:0030-drops-146410}, doi = {10.4230/LIPIcs.ESA.2021.60}, annote = {Keywords: Filters, approximate-membership query data structures (AMQs), Bloom filters, quotient filters, cuckoo filters, adaptivity, succinct data structures} }

Document

**Published in:** LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

For an abelian group Γ, a Γ-labelled graph is a graph whose vertices are labelled by elements of Γ. We prove that a certain collection of edge sets of a Γ-labelled graph forms a delta-matroid, which we call a Γ-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet to find a maximum weight feasible set in such a delta-matroid. We present two algorithmic applications on graphs; Maximum Weight Packing of Trees of Order Not Divisible by k and Maximum Weight S-Tree Packing. We also discuss various properties of Γ-graphic delta-matroids.

Donggyu Kim, Duksang Lee, and Sang-il Oum. Γ-Graphic Delta-Matroids and Their Applications. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 70:1-70:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.ISAAC.2021.70, author = {Kim, Donggyu and Lee, Duksang and Oum, Sang-il}, title = {{\Gamma-Graphic Delta-Matroids and Their Applications}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {70:1--70:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.70}, URN = {urn:nbn:de:0030-drops-155038}, doi = {10.4230/LIPIcs.ISAAC.2021.70}, annote = {Keywords: delta-matroid, group-labelled graph, greedy algorithm, tree packing} }

Document

**Published in:** LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

In this paper, we introduce dynamic lifting to a quantum circuit-description language, following the Proto-Quipper language approach. Dynamic lifting allows programs to transfer the result of measuring quantum data - qubits - into classical data - booleans -. We propose a type system and an operational semantics for the language and we state safety properties. Next, we introduce a concrete categorical semantics for the proposed language, basing our approach on a recent model from Rios&Selinger for Proto-Quipper-M. Our approach is to construct on top of a concrete category of circuits with measurements a Kleisli category, capturing as a side effect the action of retrieving classical content out of a quantum memory. We then show a soundness result for this semantics.

Dongho Lee, Valentin Perrelle, Benoît Valiron, and Zhaowei Xu. Concrete Categorical Model of a Quantum Circuit Description Language with Measurement. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 51:1-51:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.FSTTCS.2021.51, author = {Lee, Dongho and Perrelle, Valentin and Valiron, Beno\^{i}t and Xu, Zhaowei}, title = {{Concrete Categorical Model of a Quantum Circuit Description Language with Measurement}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {51:1--51:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.51}, URN = {urn:nbn:de:0030-drops-155627}, doi = {10.4230/LIPIcs.FSTTCS.2021.51}, annote = {Keywords: Categorical semantics, Operational semantics, Quantum circuit description language} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail