8 Search Results for "Ye, Deshi"

Document
DOI: 10.4230/LIPIcs.CPM.2026.27
Exploring the Gap Between LCS and LCStr

Authors: Shay Golan, Matan Kraus, Ely Porat, and B. Riva Shalom

Published in: LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Abstract
The Longest Common Subsequence (LCS) problem and the Longest Common Substring (LCStr) problem are classical string problems with broad theoretical and practical significance. The former has a quadratic conditional lower bound [FOCS, 2015], while the latter admits a linear-time solution. In this paper, we study a natural variation of these problems, the Longest Common Subsequence-Substring (LCSS) problem. The LCSS problem seeks the longest string that is simultaneously a subsequence of one input string and a substring of the other. This variant bridges LCS and LCStr, raising intriguing algorithmic questions: Does the complexity of computing LCSS interpolate between the linear time of LCStr and the quadratic time of LCS? What about approximability? We also examine a natural extension of LCSS to multiple strings, parameterizing the balance between subsequence and substring requirements. Our results reveal several insights. First, under the SETH conjecture, the inherent complexity of LCSS is quadratic, similar to LCS. In contrast, we provide a linear-time approximation for LCSS. Finally, for the multi-string variant, unlike both problems, we design a quadratic-time algorithm, uncovering deeper structural properties of the problem. By studying the complexity of the LCSS problem, we aim to gain some understanding of what influences whether a variant of the LCS problem behaves more like the standard LCS or like LCStr. Our findings suggest that hybrid constraints can create computational "sweet spots," where problems become more tractable than their pure counterparts. This opens a broader research direction in constraint-mediated algorithm design. Beyond LCSS itself, our work highlights unexpected connections between subsequence and substring constraints, advancing the theoretical understanding of string problems and laying the foundation for new algorithmic techniques and complexity-theoretic insights in the rich space between classical string comparison paradigms.
Cite as

Shay Golan, Matan Kraus, Ely Porat, and B. Riva Shalom. Exploring the Gap Between LCS and LCStr. In 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 369, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{golan_et_al:LIPIcs.CPM.2026.27,
  author =	{Golan, Shay and Kraus, Matan and Porat, Ely and Shalom, B. Riva},
  title =	{{Exploring the Gap Between LCS and LCStr}},
  booktitle =	{37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-420-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{369},
  editor =	{Bille, Philip and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.27},
  URN =		{urn:nbn:de:0030-drops-259535},
  doi =		{10.4230/LIPIcs.CPM.2026.27},
  annote =	{Keywords: Longest Common Subsequence, Longest Common Substring, Conditional Lower Bound}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.52
Online Packing of Orthogonal Polygons

Authors: Tim Gerlach, Benjamin Hennies, and Linda Kleist

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
While rectangular and box-shaped objects dominate the classic discourse of theoretic investigations, a fascinating frontier lies in packing more complex shapes. Given recent insights that convex polygons do not allow for constant competitive online algorithms for diverse variants under translation, we study orthogonal polygons, in particular of small complexity. For translational packings of orthogonal 6-gons, we show that the competitive ratio of any online algorithm that aims to pack the items into a minimal number of unit bins is in Ω(n/(log n)), where n denotes the number of objects. In contrast, we show that constant competitive algorithms exist when the orthogonal 6-gons are symmetric or small. For (orthogonally convex) orthogonal 8-gons, we show that the trivial n-competitive algorithm, which places each item in its own bin, is best-possible, i.e., every online algorithm has an asymptotic competitive ratio of at least n. This implies that for general orthogonal polygons, the trivial algorithm is best possible. Interestingly, for packing degenerate orthogonal polygons (with thickness 0), called skeletons, the change in complexity is even more drastic. While constant competitive algorithms for 6-skeletons exist, no online algorithm for 8-skeletons achieves a competitive ratio better than n. For other packing variants of orthogonal 6-gons under translation, our insights imply the following consequences. The asymptotic competitive ratio of any online algorithm is in Ω(n/(log n)) for strip packing, and there exist online algorithms with competitive ratios in O(1) for perimeter packing, or in O(√n) for minimizing the area of the bounding box. Moreover, the critical packing density is positive (if every object individually fits into the interior of a unit bin).
Cite as

Tim Gerlach, Benjamin Hennies, and Linda Kleist. Online Packing of Orthogonal Polygons. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 52:1-52:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gerlach_et_al:LIPIcs.SoCG.2026.52,
  author =	{Gerlach, Tim and Hennies, Benjamin and Kleist, Linda},
  title =	{{Online Packing of Orthogonal Polygons}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{52:1--52:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.52},
  URN =		{urn:nbn:de:0030-drops-258589},
  doi =		{10.4230/LIPIcs.SoCG.2026.52},
  annote =	{Keywords: Packing, orthogonal polygon, algorithm, offline, online, competitive ratio, bin packing, strip packing, perimeter packing, critical density, 6-gon, 8-gon, L-shape, Z-shape, skeleton}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.15
New Algorithm for Combinatorial n-Folds and Applications

Authors: Klaus Jansen, Kai Kahler, Lis Pirotton, and Malte Tutas

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Block-structured integer linear programs (ILPs) play an important role in various application fields. We address n-fold ILPs where the matrix 𝒜 has a specific structure, i.e., where the blocks in the lower part of 𝒜 consist only of the row vectors (1,… ,1). In this paper, we propose an approach tailored to exactly these combinatorial n-folds. We utilize a divide and conquer approach to separate the original problem such that the right-hand side iteratively decreases in size. We show that this decrease in size can be calculated such that we only need to consider a bounded amount of possible right-hand sides. This, in turn, lets us efficiently combine solutions of the smaller right-hand sides to solve the original problem. We can decide the feasibility of, and also optimally solve, such problems in time (n r Δ)^O(r) log(‖b‖_∞), where n is the number of blocks, r the number of rows in the upper blocks and Δ = ‖A‖_∞. We complement the algorithm by discussing applications of the n-fold ILPs with the specific structure we require. We consider the problems of (i) scheduling on uniform machines, (ii) closest string and (iii) (graph) imbalance. Regarding (i), our algorithm results in running times of p_max^O(d)|I|^O(1), matching a lower bound derived via ETH. For (ii) we achieve running times matching the current state-of-the-art in the general case. In contrast to the state-of-the-art, our result can leverage a bounded number of column-types to yield an improved running time. For (iii), we improve the parameter dependency on the size of the vertex cover.
Cite as

Klaus Jansen, Kai Kahler, Lis Pirotton, and Malte Tutas. New Algorithm for Combinatorial n-Folds and Applications. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2025.15,
  author =	{Jansen, Klaus and Kahler, Kai and Pirotton, Lis and Tutas, Malte},
  title =	{{New Algorithm for Combinatorial n-Folds and Applications}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.15},
  URN =		{urn:nbn:de:0030-drops-251472},
  doi =		{10.4230/LIPIcs.IPEC.2025.15},
  annote =	{Keywords: integer linear programming, n-fold, parameterized complexity, scheduling, uniform machines}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2025.7
Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints

Authors: Christina Büsing, Maurice Draeger, and Corinna Mathwieser

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We study the parameterized complexity of scheduling unit-time jobs on parallel, identical machines under generalized precedence constraints for minimization of the makespan and the sum of completion times (P|gen-prec, p_j = 1|γ, γ ∈ {C_max,∑_jC_j}). In our setting, each job is equipped with a Boolean formula (precedence constraint) over the set of jobs. A schedule satisfies a job’s precedence constraint if setting earlier jobs to true satisfies the formula. Our definition generalizes several common types of precedence constraints: classical and-constraints if every formula is a conjunction, or-constraints if every formula is a disjunction, and and/or-constraints if every formula is in conjunctive normal form. We prove fixed-parameter tractability when parameterizing by the number of predecessors. For parameterization by the number of successors, however, the complexity depends on the structure of the precedence constraints. If every constraint is a conjunction or a disjunction, we prove the problem to be fixed-parameter tractable. For constraints in disjunctive normal form, we prove W[1]-hardness. We show that the and/or-constrained problem is NP-hard, even for a single successor. Moreover, we prove NP-hardness on two machines if every constraint is a conjunction or a disjunction. This result not only proves para-NP-hardness for parameterization by the number of machines but also complements the polynomial-time solvability on two machines if every constraint is a conjunction [Coffman and Graham, 1972] or if every constraint is a disjunction [Johannes, 2005].
Cite as

Christina Büsing, Maurice Draeger, and Corinna Mathwieser. Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{busing_et_al:LIPIcs.IPEC.2025.7,
  author =	{B\"{u}sing, Christina and Draeger, Maurice and Mathwieser, Corinna},
  title =	{{Parameterized Complexity of Scheduling Unit-Time Jobs with Generalized Precedence Constraints}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.7},
  URN =		{urn:nbn:de:0030-drops-251390},
  doi =		{10.4230/LIPIcs.IPEC.2025.7},
  annote =	{Keywords: scheduling, precedence constraints, fixed-parameter tractability, complexity}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.IPEC.2025.1
A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk)

Authors: Martin Koutecký

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
Integer Programming (IP) is a fundamental but computationally hard problem. Still, certain efficiently solvable subclasses have been identified over time, most notably totally unimodular IPs in the 1950s, and fixed-dimension IPs in the 1980s. Starting around the year 2000, a stream of research has identified block-structured IPs as yet another tractable subclass. In this paper, we give a brief and incomplete review of this history, with a focus on several of the author’s contributions.
Cite as

Martin Koutecký. A Brief History of Parameterized Algorithms for Block-Structured Integer Programs (Invited Talk). In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{koutecky:LIPIcs.IPEC.2025.1,
  author =	{Kouteck\'{y}, Martin},
  title =	{{A Brief History of Parameterized Algorithms for Block-Structured Integer Programs}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.1},
  URN =		{urn:nbn:de:0030-drops-251338},
  doi =		{10.4230/LIPIcs.IPEC.2025.1},
  annote =	{Keywords: Integer Programming, Parameterized Algorithm, Graver Basis, Treedepth, n-fold, tree-fold, 2-stage stochastic, multistage stochastic, Mixed-Integer Programming}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.87
When to Give up on a Parallel Implementation

Authors: Nathan S. Sheffield and Alek Westover

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
In the Serial Parallel Decision Problem (SPDP), introduced by Kuszmaul and Westover [SPAA'24], an algorithm receives a series of tasks online, and must choose for each between a serial implementation and a parallelizable (but less efficient) implementation. Kuszmaul and Westover describe three decision models: (1) Instantly-committing schedulers must decide on arrival, irrevocably, which implementation of the task to run. (2) Eventually-committing schedulers can delay their decision beyond a task’s arrival time, but cannot revoke their decision once made. (3) Never-committing schedulers are always free to abandon their progress on the task and start over using a different implementation. Kuszmaul and Westover gave a simple instantly-committing scheduler whose total completion time is 3-competitive with the offline optimal schedule, and proved two lower bounds: no eventually-committing scheduler can have competitive ratio better than ϕ ≈ 1.618 in general, and no instantly-committing scheduler can have competitive ratio better than 2 in general. They conjectured that the three decision models should admit different competitive ratios, but left upper bounds below 3 in any model as an open problem. In this paper, we show that the powers of instantly, eventually, and never committing schedulers are distinct, at least in the "massively parallel regime". The massively parallel regime of the SPDP is the special case where the number of available processors is asymptotically larger than the number of tasks to process, meaning that the work associated with running a task in serial is negligible compared to its runtime. In this regime, we show (1) The optimal competitive ratio for instantly-committing schedulers is 2, (2) The optimal competitive ratio for eventually-committing schedulers lies in [1.618, 1.678], (3) The optimal competitive ratio for never-committing schedulers lies in [1.366, 1.500]. We additionally show that our instantly-committing scheduler is also 2-competitive outside of the massively parallel regime, giving proof-of-concept that results in the massively parallel regime can be translated to hold with fewer processors.
Cite as

Nathan S. Sheffield and Alek Westover. When to Give up on a Parallel Implementation. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 87:1-87:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{sheffield_et_al:LIPIcs.ITCS.2025.87,
  author =	{Sheffield, Nathan S. and Westover, Alek},
  title =	{{When to Give up on a Parallel Implementation}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{87:1--87:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.87},
  URN =		{urn:nbn:de:0030-drops-227154},
  doi =		{10.4230/LIPIcs.ITCS.2025.87},
  annote =	{Keywords: Scheduling, Multi-Processor, Online-Algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.22
Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix

Authors: Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We study approximation and parameterized algorithms for R||C_max, focusing on the problem when the rank of the matrix formed by job processing times is small. Bhaskara et al. initiated the study of approximation algorithms with respect to the rank, showing that R||C_max admits a QPTAS (Quasi-polynomial time approximation scheme) when the rank is 2, and becomes APX-hard when the rank is 4. We continue this line of research. We prove that R||C_max is APX-hard even if the rank is 3, resolving an open problem. We then show that R||C_max is FPT parameterized by the rank and the largest job processing time p_max. This generalizes the parameterized results on P||C_max and R||C_max with few different types of machines. We also provide nearly tight lower bounds under Exponential Time Hypothesis which suggests that the running time of the FPT algorithm is unlikely to be improved significantly.
Cite as

Lin Chen, Dániel Marx, Deshi Ye, and Guochuan Zhang. Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2017.22,
  author =	{Chen, Lin and Marx, D\'{a}niel and Ye, Deshi and Zhang, Guochuan},
  title =	{{Parameterized and Approximation Results for Scheduling with a Low Rank Processing Time Matrix}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{22:1--22:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.22},
  URN =		{urn:nbn:de:0030-drops-70110},
  doi =		{10.4230/LIPIcs.STACS.2017.22},
  annote =	{Keywords: APX-hardness, Parameterized algorithm, Scheduling, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.5
Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources

Authors: Lin Chen, Deshi Ye, and Guochuan Zhang

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract
We consider the problem of scheduling with renewable speed-up resources. Given m identical machines, n jobs and c different discrete resources, the task is to schedule each job non-preemptively onto one of the machines so as to minimize the makespan. In our problem, a job has its original processing time, which could be reduced by utilizing one of the resources. As resources are different, the amount of the time reduced for each job is different depending on the resource it uses. Once a resource is being used by one job, it can not be used simultaneously by any other job until this job is finished, hence the scheduler should take into account the job-to-machine assignment together with the resource-to-job assignment. We observe that, the classical unrelated machine scheduling problem is actually a special case of our problem when m=c, i.e., the number of resources equals the number of machines. Extending the techniques for the unrelated machine scheduling, we give a 2-approximation algorithm when both m and c are part of the input. We then consider two special cases for the problem, with m or c being a constant, and derive PTASes (Polynomial Time Approximation Schemes) respectively. We also establish the relationship between the two parameters m and c, through which we are able to transform the PTAS for the case when m is constant to the case when c is a constant. The relationship between the two parameters reveals the structure within the problem, and may be of independent interest.
Cite as

Lin Chen, Deshi Ye, and Guochuan Zhang. Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX-RANDOM.2016.5,
  author =	{Chen, Lin and Ye, Deshi and Zhang, Guochuan},
  title =	{{Approximation Algorithms for Parallel Machine Scheduling with Speed-up Resources}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.5},
  URN =		{urn:nbn:de:0030-drops-66283},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.5},
  annote =	{Keywords: approximation algorithms, scheduling, linear programming}
}
  • Refine by Type
  • 8 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 4 2025
  • 1 2017
  • 1 2016

  • Refine by Author
  • 2 Chen, Lin
  • 2 Ye, Deshi
  • 2 Zhang, Guochuan
  • 1 Büsing, Christina
  • 1 Draeger, Maurice
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Computational geometry
  • 1 Theory of computation → Convex optimization
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Online algorithms
  • Show More...

  • Refine by Keyword
  • 3 scheduling
  • 2 Scheduling
  • 2 n-fold
  • 1 2-stage stochastic
  • 1 6-gon
  • 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