Buchumschlag

Scheduling Problems with Constrained Rejections

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Davies, Sami, Guruswami, Venkatesan, Ren, Xuandi
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2023)

Hardness of Learning Boolean Functions from Label Proportions
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2025)

Certifying Euclidean Sections and Finding Planted Sparse Vectors Beyond the $\sqrt{n}$ Dimension Threshold
von: Guruswami, Venkatesan, et al.
Veröffentlicht: (2024)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2026)

Equivalent Instances for Scheduling and Packing Problems
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Simple approximation algorithms for Polyamorous Scheduling
von: Biktairov, Yuriy, et al.
Veröffentlicht: (2024)

The Days On Days Off Scheduling Problem
von: Nießen, Fabien, et al.
Veröffentlicht: (2024)

Kernelization Bounds for Constrained Coloring
von: Haviv, Ishay
Veröffentlicht: (2026)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2026)

Scalable Neighborhood Local Search for Single-Machine Scheduling with Family Setup Times
von: Balzereit, Kaja, et al.
Veröffentlicht: (2024)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
von: Moka, Sarat, et al.
Veröffentlicht: (2026)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
von: Kontogiannis, Andreas, et al.
Veröffentlicht: (2026)

String Consensus Problems with Swaps and Substitutions
von: Gabory, Estéban, et al.
Veröffentlicht: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Neighborhood-Aware Graph Labeling Problem
von: Shahverdikondori, Mohammad, et al.
Veröffentlicht: (2026)

Generalized Graph Packing Problems Parameterized by Treewidth
von: Esmer, Barış Can, et al.
Veröffentlicht: (2025)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
von: Bilò, Davide, et al.
Veröffentlicht: (2025)

Complexity of Local Search for Euclidean Clustering Problems
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

NP-Hardness and a PTAS for the Pinwheel Problem
von: Kleinberg, Robert, et al.
Veröffentlicht: (2026)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

Computational Complexity of Edge Coverage Problem for Constrained Control Flow Graphs
von: Ruszil, Jakub, et al.
Veröffentlicht: (2026)

No Price Tags? No Problem: Query Strategies for Unpriced Information
von: Nadimpalli, Shivam, et al.
Veröffentlicht: (2025)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
von: Nederlof, Jesper
Veröffentlicht: (2026)

Structural Parameterizations for Two Bounded Degree Problems Revisited
von: Lampis, Michael, et al.
Veröffentlicht: (2023)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
von: Bhaskar, Umang, et al.
Veröffentlicht: (2025)

A Complexity Analysis of the c-Closed Vertex Deletion Problem
von: Lehner, Lisa, et al.
Veröffentlicht: (2025)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
von: Focke, Jacob, et al.
Veröffentlicht: (2023)

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2026)

Fine-Grained Equivalence for Problems Related to Integer Linear Programming
von: Rohwedder, Lars, et al.
Veröffentlicht: (2024)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
von: Shih, Yu-Sheng, et al.
Veröffentlicht: (2026)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
von: Esmer, Barış Can, et al.
Veröffentlicht: (2024)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)

Finding Diverse Solutions in Combinatorial Problems with a Distributive Lattice Structure
von: de Berg, Mark, et al.
Veröffentlicht: (2025)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
von: Kenig, Batya
Veröffentlicht: (2025)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems
von: Ghosh, Mrinalkanti
Veröffentlicht: (2025)

End Cover for Initial Value Problem: Complete Validated Algorithms with Complexity Analysis
von: Zhang, Bingwei, et al.
Veröffentlicht: (2026)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
von: Hu, Bingbing, et al.
Veröffentlicht: (2024)