Imagen de Portada

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Li, Shi
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

$k$-Clustering via Iterative Randomized Rounding
por: Byrka, Jarosław, et al.
Publicado: (2026)

Faster Minimization of Total Weighted Completion Time on Parallel Machines
por: Hermelin, Danny, et al.
Publicado: (2025)

3.415-Approximation for Coflow Scheduling via Iterated Rounding
por: Rohwedder, Lars, et al.
Publicado: (2025)

An EPTAS for Cardinality Constrained Multiple Knapsack via Iterative Randomized Rounding
por: Doron-Arad, Ilan, et al.
Publicado: (2023)

Randomized Rounding over Dynamic Programs
por: Bamas, Etienne, et al.
Publicado: (2025)

Approximating Multiple-Depot Capacitated Vehicle Routing via LP Rounding
por: Friggstad, Zachary, et al.
Publicado: (2025)

Improved Algorithms for Unrelated Crowd Worker Scheduling in Mobile Social Networks
por: Chen, Chi-Yeh
Publicado: (2026)

On Approximation of Robust Max-Cut and Related Problems using Randomized Rounding Algorithms
por: Shi, Haoyan, et al.
Publicado: (2024)

On Tight FPT Time Approximation Algorithms for k-Clustering Problems
por: Dai, Han, et al.
Publicado: (2025)

Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
por: Brakensiek, Joshua, et al.
Publicado: (2026)

Greedy Completion for Weighted $(α,β)$-Spanners
por: Tzalik, Elad
Publicado: (2026)

DNA Probe Computing System for Solving NP-Complete Problems
por: Xu, Jin, et al.
Publicado: (2025)

Entrywise Low-Rank Approximation and Matrix $p \rightarrow q$ Norms via Global Correlation Rounding
por: Anderson, Prashanti, et al.
Publicado: (2026)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
por: Zhao, Jingyang, et al.
Publicado: (2023)

Improved Combinatorial Approximations for Weighted Correlation Clustering
por: Ostovari, Mojtaba, et al.
Publicado: (2023)

Fast Tensor Completion via Approximate Richardson Iteration
por: Ghadiri, Mehrdad, et al.
Publicado: (2025)

Robust Scheduling on Uniform Machines -- New Results Using a Relaxed Approximation Guarantee
por: Brinkop, Hauke, et al.
Publicado: (2025)

Constant-Stretch Rounding on the Hypersimplex
por: Anari, Nima, et al.
Publicado: (2026)

Polylogarithmic Approximation for Robust s-t Path
por: Li, Shi, et al.
Publicado: (2023)

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
por: Zheng, Da Wei, et al.
Publicado: (2023)

An Improved Approximation Algorithm for Maximum Weight 3-Path Packing
por: Zhao, Jingyang, et al.
Publicado: (2025)

Improved Approximation Algorithms for Chromatic and Pseudometric-Weighted Correlation Clustering
por: Fan, Chenglin, et al.
Publicado: (2025)

Matroid-Based TSP Rounding for Half-Integral Solutions
por: Gupta, Anupam, et al.
Publicado: (2021)

Sorting and Selection in Rounds with Adversarial Comparisons
por: Trevisan, Chris
Publicado: (2023)

Cut-Query Algorithms with Few Rounds
por: Kenneth-Mordoch, Yotam, et al.
Publicado: (2025)

Logarithmic Approximations for Fair k-Set Selection
por: Li, Shi, et al.
Publicado: (2025)

Improved FPT Approximation Scheme and Approximate Kernel for Biclique-Free Max k-Weight SAT: Greedy Strikes Back
por: Manurangsi, Pasin
Publicado: (2024)

Min-CSPs on Complete Instances II: Polylogarithmic Approximation for Min-NAE-3-SAT
por: Anand, Aditya, et al.
Publicado: (2025)

Complexity and Approximation Algorithms for Fixed Charge Transportation Problems
por: Chen, Yong, et al.
Publicado: (2025)

Approximations for the Weighted Reversal, Transposition, and Indel Distance Problem with Intergenic Region Information
por: Siqueira, Gabriel, et al.
Publicado: (2025)

Total Completion Time Scheduling Under Scenarios
por: Bosman, Thomas, et al.
Publicado: (2024)

A Note on Rounding Matchings in General Graphs
por: Dudeja, Aditi
Publicado: (2024)

Proportionally Fair Matching via Randomized Rounding
por: Duppala, Sharmila, et al.
Publicado: (2024)

Online Rounding Schemes for $ k $-Rental Problems
por: Nekouyan, Hossein, et al.
Publicado: (2025)

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

Optimal Rounding for Two-Stage Bipartite Matching
por: Pollner, Tristan, et al.
Publicado: (2025)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
por: Henzinger, Monika, et al.
Publicado: (2024)

Simultaneously Approximating All Norms for Massively Parallel Correlation Clustering
por: Cao, Nairen, et al.
Publicado: (2024)

A Simple Proof that Ricochet Robots is PSPACE-Complete
por: Balanza-Martinez, Jose, et al.
Publicado: (2024)

Approximating Partition in Near-Linear Time
por: Chen, Lin, et al.
Publicado: (2024)