An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding (English)
Free access
- New search for: Doron-Arad, Ilan
- New search for: Kulik, Ariel
- New search for: Shachnai, Hadas
- New search for: Doron-Arad, Ilan
- New search for: Kulik, Ariel
- New search for: Shachnai, Hadas
- New search for: Megow, Nicole
- Further information on Megow, Nicole:
- https://orcid.org/0000-0002-3531-7644
- New search for: Smith, Adam
- Further information on Smith, Adam:
- https://orcid.org/0000-0001-9393-1127
In:
LIPIcs, Volume 275, APPROX/RANDOM 2023
: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
;
275
;
22:1-22:16
;
2023
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP Rounding
-
Contributors:Doron-Arad, Ilan ( author ) / Kulik, Ariel ( author ) / Shachnai, Hadas ( author ) / Megow, Nicole ( editor ) / Smith, Adam ( editor )
-
Published in:LIPIcs, Volume 275, APPROX/RANDOM 2023 : Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) ; 275 ; 22:1-22:16Leibniz International Proceedings in Informatics (LIPIcs) ; 275 ; 22:1-22:16
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2023-09-04
-
Size:16 pages , 977470 byte
-
Remarks:LIPIcs, Vol. 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), pages 22:1-22:16
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Conference paper
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Licence:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
On Complexity of 1-Center in Various MetricsAbboud, Amir / Bateni, MohammadHossein / Cohen-Addad, Vincent / Karthik C. S. / Seddighin, Saeed et al. | 2023
- 2
-
Probabilistic Metric Embedding via Metric LabelingMunagala, Kamesh / Sankar, Govind S. / Taylor, Erin et al. | 2023
- 3
-
Approximating Submodular k-Partition via Principal Partition SequenceChandrasekaran, Karthekeyan / Wang, Weihang et al. | 2023
- 4
-
Experimental Design for Any p-NormLau, Lap Chi / Wang, Robert / Zhou, Hong et al. | 2023
- 5
-
Approximation Algorithms for Maximum Weighted Throughput on Unrelated MachinesKarakostas, George / Kolliopoulos, Stavros G. et al. | 2023
- 6
-
Facility Location in the Sublinear Geometric ModelMonemizadeh, Morteza et al. | 2023
- 7
-
Bicriteria Approximation Algorithms for Priority Matroid MedianBajpai, Tanvi / Chekuri, Chandra et al. | 2023
- 8
-
Approximation Algorithms for Directed Weighted SpannersGrigorescu, Elena / Kumar, Nithish / Lin, Young-San et al. | 2023
- 9
-
Approximation Algorithms and Lower Bounds for Graph BurningLieskovský, Matej / Sgall, Jiří / Feldmann, Andreas Emil et al. | 2023
- 10
-
The (Im)possibility of Simple Search-To-Decision Reductions for Approximation ProblemsGolovnev, Alexander / Guo, Siyao / Peters, Spencer / Stephens-Davidowitz, Noah et al. | 2023
- 11
-
Approximating Red-Blue Set Cover and Minimum Monotone Satisfying AssignmentChlamtáč, Eden / Makarychev, Yury / Vakilian, Ali et al. | 2023
- 12
-
Efficient Algorithms and Hardness Results for the Weighted k-Server ProblemGupta, Anupam / Kumar, Amit / Panigrahi, Debmalya et al. | 2023
- 13
-
A Constant-Factor Approximation for Quasi-Bipartite Directed Steiner Tree on Minor-Free GraphsFriggstad, Zachary / Mousavi, Ramin et al. | 2023
- 14
-
Algorithms for 2-Connected Network Design and Flexible Steiner Trees with a Constant Number of TerminalsBansal, Ishan / Cheriyan, Joe / Grout, Logan / Ibrahimpur, Sharat et al. | 2023
- 15
-
Oblivious Algorithms for the Max-kAND ProblemSinger, Noah G. et al. | 2023
- 16
-
A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star GraphsHöhne, Felix / van Stee, Rob et al. | 2023
- 17
-
Online Matching with Set and Concave DelaysDeryckere, Lindsey / Umboh, Seeun William et al. | 2023
- 18
-
An Approximation Algorithm for the Exact Matching Problem in Bipartite GraphsDürr, Anita / El Maalouly, Nicolas / Wulf, Lasse et al. | 2023
- 19
-
Tighter Approximation for the Uniform Cost-Distance Steiner Tree ProblemFoos, Josefine / Held, Stephan / Spitzley, Yannik Kyle Dustin et al. | 2023
- 20
-
Round and Bipartize for Vertex Cover ApproximationKashaev, Danish / Schäfer, Guido et al. | 2023
- 21
-
On Minimizing Generalized Makespan on Unrelated MachinesAyyadevara, Nikhil / Bansal, Nikhil / Prabhu, Milind et al. | 2023
- 22
-
An AFPTAS for Bin Packing with Partition Matroid via a New Method for LP RoundingDoron-Arad, Ilan / Kulik, Ariel / Shachnai, Hadas et al. | 2023
- 23
-
Submodular Norms with Applications To Online Facility Location and Stochastic ProbingPatton, Kalen / Russo, Matteo / Singla, Sahil et al. | 2023
- 24
-
Independent Sets in Elimination Graphs with a Submodular ObjectiveChekuri, Chandra / Quanrud, Kent et al. | 2023
- 25
-
Improved Diversity Maximization Algorithms for Matching and PseudoforestMahabadi, Sepideh / Narayanan, Shyam et al. | 2023
- 26
-
Approximating Pandora’s Box with CorrelationsChawla, Shuchi / Gergatsouli, Evangelia / McMahan, Jeremy / Tzamos, Christos et al. | 2023
- 27
-
Stable Approximation Algorithms for Dominating Set and Independent Setde Berg, Mark / Sadhukhan, Arpan / Spieksma, Frits et al. | 2023
- 28
-
Scalable Auction Algorithms for Bipartite Maximum Matching ProblemsLiu, Quanquan C. / Ke, Yiduo / Khuller, Samir et al. | 2023
- 29
-
Giant Components in Random Temporal GraphsBecker, Ruben / Casteigts, Arnaud / Crescenzi, Pierluigi / Kodric, Bojana / Renken, Malte / Raskin, Michael / Zamaraev, Viktor et al. | 2023
- 30
-
On Connectivity in Random Graph Models with Limited DependenciesLengler, Johannes / Martinsson, Anders / Petrova, Kalina / Schnider, Patrick / Steiner, Raphael / Weber, Simon / Welzl, Emo et al. | 2023
- 31
-
Synergy Between Circuit Obfuscation and Circuit MinimizationImpagliazzo, Russell / Kabanets, Valentine / Volkovich, Ilya et al. | 2023
- 32
-
Interactive Error Correcting Codes: New Constructions and Impossibility BoundsGupta, Meghal / Zhang, Rachel Yun et al. | 2023
- 33
-
Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary TreesEfthymiou, Charilaos / Hayes, Thomas P. / Štefankovič, Daniel / Vigoda, Eric et al. | 2023
- 34
-
Superpolynomial Lower Bounds for Learning Monotone ClassesBshouty, Nader H. et al. | 2023
- 35
-
An Embarrassingly Parallel Optimal-Space Cardinality Estimation AlgorithmKarayel, Emin et al. | 2023
- 36
-
Sampling and Certifying Symmetric FunctionsFilmus, Yuval / Leigh, Itai / Riazanov, Artur / Sokolov, Dmitry et al. | 2023
- 37
-
Hardness of the (Approximate) Shortest Vector Problem: A Simple Proof via Reed-Solomon CodesBennett, Huck / Peikert, Chris et al. | 2023
- 38
-
Perfect Sampling for Hard Spheres from Strong Spatial MixingAnand, Konrad / Göbel, Andreas / Pappik, Marcus / Perkins, Will et al. | 2023
- 39
-
Subset Sum in Time 2^{n/2} / poly(n)Chen, Xi / Jin, Yaonan / Randolph, Tim / Servedio, Rocco A. et al. | 2023
- 40
-
On Optimization and Counting of Non-Broken Bases of MatroidsAbdolazimi, Dorna / Lindberg, Kasper / Gharan, Shayan Oveis et al. | 2023
- 41
-
Low-Degree Testing over GridsAmireddy, Prashanth / Srinivasan, Srikanth / Sudan, Madhu et al. | 2023
- 42
-
Improved Local Computation Algorithms for Constructing SpannersArviv, Rubi / Chung, Lily / Levi, Reut / Pyne, Edward et al. | 2023
- 43
-
Classical Simulation of One-Query Quantum DistinguishersBogdanov, Andrej / Cheung, Tsun Ming / Dinesh, Krishnamoorthy / Lui, John C. S. et al. | 2023
- 44
-
On the Power of Regular and Permutation Branching ProgramsLee, Chin Ho / Pyne, Edward / Vadhan, Salil et al. | 2023
- 45
-
Private Data Stream Analysis for Universal Symmetric Norm EstimationBraverman, Vladimir / Manning, Joel / Wu, Zhiwei Steven / Zhou, Samson et al. | 2023
- 46
-
Testing Versus Estimation of Graph Properties, RevisitedGishboliner, Lior / Kushnir, Nick / Shapira, Asaf et al. | 2023
- 47
-
Efficient Interactive Proofs for Non-Deterministic Bounded SpaceCook, Joshua / Rothblum, Ron D. et al. | 2023
- 48
-
On the Complexity of Triangle Counting Using Emptiness QueriesBishnu, Arijit / Ghosh, Arijit / Mishra, Gopinath et al. | 2023
- 49
-
Fine Grained Analysis of High Dimensional Random WalksGotlib, Roy / Kaufman, Tali et al. | 2023
- 50
-
A Deterministic Construction of a Large Distance Code from the Wozencraft EnsembleGuruswami, Venkatesan / Li, Shilun et al. | 2023
- 51
-
NP-Hardness of Almost Coloring Almost 3-Colorable GraphsHecht, Yahli / Minzer, Dor / Safra, Muli et al. | 2023
- 52
-
Extracting Mergers and Projections of PartitionsKopparty, Swastik / N, Vishvajeet et al. | 2023
- 53
-
Rapid Mixing of Global Markov Chains via Spectral Independence: The Unbounded Degree CaseBlanca, Antonio / Zhang, Xusheng et al. | 2023
- 54
-
The Full Rank Condition for Sparse Random MatricesCoja-Oghlan, Amin / Gao, Jane / Hahn-Klimroth, Max / Lee, Joon / Müller, Noela / Rolvien, Maurice et al. | 2023
- 55
-
Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACECook, Joshua / Moshkovitz, Dana et al. | 2023
- 56
-
Robustness for Space-Bounded Statistical Zero KnowledgeAllender, Eric / Gray, Jacob / Mutreja, Saachi / Tirumala, Harsha / Wang, Pengxiang et al. | 2023
- 57
-
On Constructing Spanners from Random Gaussian ProjectionsAssadi, Sepehr / Kapralov, Michael / Yu, Huacheng et al. | 2023
- 58
-
Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural BalanceAshvinkumar, Vikrant / Assadi, Sepehr / Deng, Chengyuan / Gao, Jie / Wang, Chen et al. | 2023
- 59
-
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low SensitivityBlocki, Jeremiah / Grigorescu, Elena / Mukherjee, Tamalika / Zhou, Samson et al. | 2023
- 60
-
Fast Decoding of Explicit Almost Optimal ε-Balanced q-Ary Codes And Fast Approximation of Expanding k-CSPsJeronimo, Fernando Granha et al. | 2023
- 61
-
Directed Poincaré Inequalities and L¹ Monotonicity Testing of Lipschitz FunctionsFerreira Pinto Jr., Renato et al. | 2023
- 62
-
Bias Reduction for Sum EstimationEden, Talya / Houen, Jakob Bæk Tejs / Narayanan, Shyam / Rosenbaum, Will / Tětek, Jakub et al. | 2023
- 63
-
On the Composition of Randomized Query Complexity and Approximate DegreeChakraborty, Sourav / Kayal, Chandrima / Mittal, Rajat / Paraashar, Manaswi / Sanyal, Swagato / Saurabh, Nitin et al. | 2023
- 64
-
Sampling from the Random Cluster Model on Random Regular Graphs at All Temperatures via Glauber DynamicsGalanis, Andreas / Goldberg, Leslie Ann / Smolarova, Paulina et al. | 2023
- 65
-
Range Avoidance for Constant Depth Circuits: Hardness and AlgorithmsGajulapalli, Karthik / Golovnev, Alexander / Nagargoje, Satyajeet / Saraogi, Sidhant et al. | 2023
- 66
-
Testing Connectedness of ImagesBerman, Piotr / Murzabulatov, Meiram / Raskhodnikova, Sofya / Ristache, Dragos et al. | 2023