Cover Image

Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Harris, David G.
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Dependent randomized rounding for clustering and partition systems with knapsack constraints
by: Harris, David G., et al.
Published: (2017)

Improved algorithms for single machine serial-batch scheduling to minimize makespan and maximum cost
by: Li, Shuguang, et al.
Published: (2025)

Online busy time scheduling with flexible jobs
by: Albers, Susanne, et al.
Published: (2024)

Algorithms for matrix multiplication via sampling and opportunistic matrix multiplication
by: Harris, David G.
Published: (2021)

A $(2+\varepsilon)$-approximation algorithm for the general scheduling problem in quasipolynomial time
by: Armbruster, Alexander, et al.
Published: (2025)

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
by: Fischer, David, et al.
Published: (2022)

Speed-robust scheduling revisited
by: Minařík, Josef, et al.
Published: (2024)

Simple and efficient four-cycle counting on sparse graphs
by: Burkhardt, Paul, et al.
Published: (2023)

Improved linearly ordered colorings of hypergraphs via SDP rounding
by: Louis, Anand, et al.
Published: (2024)

Improved parallel derandomization via finite automata with applications
by: Giliberti, Jeff, et al.
Published: (2024)

A simpler QPTAS for scheduling jobs with precedence constraints
by: Das, Syamantak, et al.
Published: (2025)

Stochastic scheduling with Bernoulli-type jobs through policy stratification
by: Antoniadis, Antonios, et al.
Published: (2025)

Simple parallel estimation of the partition ratio for Gibbs distributions
by: Harris, David G., et al.
Published: (2025)

A faster algorithm for Vertex Cover parameterized by solution size
by: Harris, David G., et al.
Published: (2022)

Stochastic Multi-round Submodular Optimization with Budget
by: Auletta, Vincenzo, et al.
Published: (2024)

Enumerating all minimal hitting sets in polynomial total time
by: Wild, Marcel
Published: (2023)

Real Time Proportional Throughput Maximization: How much advance notice should you give your scheduler?
by: Mottu, Nadim A.
Published: (2025)

Pivot based correlation clustering in the presence of good clusters
by: Lolck, David Rasmussen, et al.
Published: (2026)

Online Dependent Rounding Schemes for Bipartite Matchings, with Applications
by: Joseph, et al.
Published: (2023)

A new notion of commutativity for the algorithmic Lovász Local Lemma
by: Harris, David G., et al.
Published: (2020)

A LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties
by: Xiao, Hanyin, et al.
Published: (2025)

Faster negative length shortest paths by bootstrapping hop reducers
by: Huang, Yufan, et al.
Published: (2025)

Stochastic Optimization and Learning for Two-Stage Supplier Problems
by: Brubach, Brian, et al.
Published: (2020)

An online joint replenishment problem combined with single machine scheduling
by: Györgyi, Péter, et al.
Published: (2022)

Finding missing items requires strong forms of randomness
by: Chakrabarti, Amit, et al.
Published: (2023)

Perpetual maintenance of machines with different urgency requirements
by: Gąsieniec, Leszek, et al.
Published: (2022)

A rounding and clustering-based exact algorithm for the p-center problem
by: Ales, Zacharie, et al.
Published: (2024)

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
by: Kobayashi, Yasuaki, et al.
Published: (2023)

Efficient stream-based Max-Min diversification with minimal failure rate
by: Kalogeratos, Argyris, et al.
Published: (2020)

Approximate minimization of interpretations in fuzzy description logics under the Gödel semantics
by: Nguyen, Linh Anh
Published: (2025)

Dependency-Aware Online Caching
by: Dallot, Julien, et al.
Published: (2024)

A probabilistic analysis on general probabilistic scheduling problems
by: Suruga, Daiki
Published: (2024)

Faster single-source shortest paths with negative real weights via proper hop distance
by: Huang, Yufan, et al.
Published: (2024)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

Sequential Testing with Subadditive Costs
by: Harris, Blake, et al.
Published: (2025)

Learning Dependency Models for Subset Repair
by: Li, Haoda, et al.
Published: (2025)

Chromatic correlation clustering via cluster LP
by: Abbasi, Fateme, et al.
Published: (2025)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Data-Dependent LSH for the Earth Mover's Distance
by: Jayaram, Rajesh, et al.
Published: (2024)

Cost Preserving Dependent Rounding for Allocation Problems
by: Rohwedder, Lars, et al.
Published: (2025)