A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems (English)
Free access
- New search for: Kimura, Kei
- Further information on Kimura, Kei:
- https://orcid.org/0000-0002-0560-5127
- New search for: Makino, Kazuhisa
- New search for: Kimura, Kei
- Further information on Kimura, Kei:
- https://orcid.org/0000-0002-0560-5127
- New search for: Makino, Kazuhisa
- New search for: Iwata, Satoru
- Further information on Iwata, Satoru:
- https://orcid.org/0000-0002-6467-1335
- New search for: Kakimura, Naonori
- Further information on Kakimura, Naonori:
- https://orcid.org/0000-0002-3918-3479
In:
LIPIcs, Volume 283, ISAAC 2023
: 34th International Symposium on Algorithms and Computation (ISAAC 2023)
;
283
;
47:1-47:17
;
2023
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution Systems
-
Contributors:Kimura, Kei ( author ) / Makino, Kazuhisa ( author ) / Iwata, Satoru ( editor ) / Kakimura, Naonori ( editor )
-
Published in:LIPIcs, Volume 283, ISAAC 2023 : 34th International Symposium on Algorithms and Computation (ISAAC 2023) ; 283 ; 47:1-47:17Leibniz International Proceedings in Informatics (LIPIcs) ; 283 ; 47:1-47:17
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2023-11-28
-
Size:17 pages , 866094 byte
-
Remarks:LIPIcs, Vol. 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023), pages 47:1-47:17
-
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
-
Group Fairness: From Multiwinner Voting to Participatory Budgeting (Invited Talk)Elkind, Edith et al. | 2023
- 2
-
Faithful Graph Drawing (Invited Talk)Hong, Seok-Hee et al. | 2023
- 3
-
Realizability of Free Spaces of CurvesA. Akitaya, Hugo / Buchin, Maike / Mirzanezhad, Majid / Ryvkin, Leonie / Wenk, Carola et al. | 2023
- 4
-
k-Universality of Regular LanguagesAdamson, Duncan / Fleischmann, Pamela / Huch, Annika / Koß, Tore / Manea, Florin / Nowotka, Dirk et al. | 2023
- 5
-
Unified Almost Linear Kernels for Generalized Covering and Packing Problems on Nowhere Dense ClassesAhn, Jungho / Kim, Jinha / Kwon, O-joung et al. | 2023
- 6
-
Geometric TSP on SetsAlkema, Henk / de Berg, Mark et al. | 2023
- 7
-
Depth-Three Circuits for Inner Product and Majority FunctionsAmano, Kazuyuki et al. | 2023
- 8
-
Recognizing Unit Multiple Intervals Is HardArdévol Martínez, Virginia / Rizzi, Romeo / Sikora, Florian / Vialette, Stéphane et al. | 2023
- 9
-
Non-Clairvoyant Makespan Minimization Scheduling with PredictionsBampis, Evripidis / Kononov, Alexander / Lucarelli, Giorgio / Pascual, Fanny et al. | 2023
- 10
-
Small-Space Algorithms for the Online Language Distance Problem for Palindromes and SquaresBathie, Gabriel / Kociumaka, Tomasz / Starikovskaya, Tatiana et al. | 2023
- 11
-
Sparse Graphs of Twin-Width 2 Have Bounded Tree-WidthBergougnoux, Benjamin / Gajarský, Jakub / Guśpiel, Grzegorz / Hliněný, Petr / Pokrývka, Filip / Sokołowski, Marek et al. | 2023
- 12
-
Substring Complexity in Sublinear SpaceBernardini, Giulia / Fici, Gabriele / Gawrychowski, Paweł / Pissis, Solon P. et al. | 2023
- 13
-
New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related MachinesBerndt, Sebastian / Brinkop, Hauke / Jansen, Klaus / Mnich, Matthias / Stamm, Tobias et al. | 2023
- 14
-
Improved Guarantees for the a Priori TSPBlauth, Jannis / Neuwohner, Meike / Puhlmann, Luise / Vygen, Jens et al. | 2023
- 15
-
An FPT Algorithm for Splitting a Necklace Among Two ThievesBorzechowski, Michaela / Schnider, Patrick / Weber, Simon et al. | 2023
- 16
-
Fast Convolutions for Near-Convex SequencesBrand, Cornelius / Lassota, Alexandra et al. | 2023
- 17
-
Matrix Completion: Approximating the Minimum DiameterChakraborty, Diptarka / Dey, Sanjana et al. | 2023
- 18
-
Distance Queries over Dynamic Interval GraphsChen, Jingbang / He, Meng / Munro, J. Ian / Peng, Richard / Wu, Kaiyu / Zhang, Daniel J. et al. | 2023
- 19
-
FPT Approximation Using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating SetChu, Huairui / Lin, Bingkai et al. | 2023
- 20
-
Improved Approximation for Two-Dimensional Vector Multiple KnapsackCohen, Tomer / Kulik, Ariel / Shachnai, Hadas et al. | 2023
- 21
-
A Compact DAG for Storing and Searching Maximal Common SubsequencesConte, Alessio / Grossi, Roberto / Punzi, Giulia / Uno, Takeaki et al. | 2023
- 22
-
Prefix Sorting DFAs: A Recursive AlgorithmCotumaccio, Nicola et al. | 2023
- 23
-
Clustering in Polygonal Domainsde Berg, Mark / Biabani, Leyla / Monemizadeh, Morteza / Theocharous, Leonidas et al. | 2023
- 24
-
Finding Diverse Minimum s-t Cutsde Berg, Mark / López Martínez, Andrés / Spieksma, Frits et al. | 2023
- 25
-
Efficient Algorithms for Euclidean Steiner Minimal Tree on Near-Convex Terminal SetsDhar, Anubhav / Hait, Soumita / Kolay, Sudeshna et al. | 2023
- 26
-
Rectilinear-Upward Planarity Testing of DigraphsDidimo, Walter / Kaufmann, Michael / Liotta, Giuseppe / Ortali, Giacomo / Patrignani, Maurizio et al. | 2023
- 27
-
A Unified Worst Case for Classical Simplex and Policy Iteration Pivot RulesDisser, Yann / Mosis, Nils et al. | 2023
- 28
-
Exact Matching: Correct Parity and FPT Parameterized by Independence NumberEl Maalouly, Nicolas / Steiner, Raphael / Wulf, Lasse et al. | 2023
- 29
-
Approximation Guarantees for Shortest Superstrings: Simpler and BetterEnglert, Matthias / Matsakis, Nicolaos / Veselý, Pavel et al. | 2023
- 30
-
Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth GraphsEppstein, David / Frishberg, Daniel et al. | 2023
- 31
-
Matching Cuts in Graphs of High Girth and H-Free GraphsFeghali, Carl / Lucke, Felicia / Paulusma, Daniël / Ries, Bernard et al. | 2023
- 32
-
Computing Paths of Large Rank in Planar Frameworks DeterministicallyFomin, Fedor V. / Golovach, Petr A. / Korhonen, Tuukka / Stamoulis, Giannos et al. | 2023
- 33
-
Pattern-Avoiding Binary Trees - Generation, Counting, and BijectionsGregor, Petr / Mütze, Torsten / Namrata et al. | 2023
- 34
-
Computing a Subtrajectory Cluster from c-Packed TrajectoriesGudmundsson, Joachim / Huang, Zijin / van Renssen, André / Wong, Sampson et al. | 2023
- 35
-
Shortest Beer Path Queries in Digraphs with Bounded TreewidthGudmundsson, Joachim / Sha, Yuan et al. | 2023
- 36
-
Coloring and Recognizing Mixed Interval GraphsGutowski, Grzegorz / Junosza-Szaniawski, Konstanty / Klesen, Felix / Rzążewski, Paweł / Wolff, Alexander / Zink, Johannes et al. | 2023
- 37
-
Shortest Beer Path Queries Based on Graph DecompositionHanaka, Tesshu / Ono, Hirotaka / Sadakane, Kunihiko / Sugiyama, Kosuke et al. | 2023
- 38
-
Temporal Separators with DeadlinesHarutyunyan, Hovhannes A. / Koupayi, Kamran / Pankratov, Denis et al. | 2023
- 39
-
Regularization of Low Error PCPs and an Application to MCSPHirahara, Shuichi / Moshkovitz, Dana et al. | 2023
- 40
-
Structural Parameterizations of b-ColoringJaffke, Lars / Lima, Paloma T. / Sharma, Roohani et al. | 2023
- 41
-
Clustering What Matters in Constrained Settings: Improved Outlier to Outlier-Free ReductionsJaiswal, Ragesh / Kumar, Amit et al. | 2023
- 42
-
Single-Exponential FPT Algorithms for Enumerating Secluded ℱ-Free Subgraphs and Deleting to Scattered Graph ClassesJansen, Bart M. P. / de Kroon, Jari J. H. / Włodarczyk, Michał et al. | 2023
- 43
-
Is the Algorithmic Kadison-Singer Problem Hard?Jourdan, Ben / Macgregor, Peter / Sun, He et al. | 2023
- 44
-
Succinct Planar Encoding with Minor OperationsKammer, Frank / Meintrup, Johannes et al. | 2023
- 45
-
Improved Approximation Algorithm for Capacitated Facility Location with Uniform Facility CostKao, Mong-Jen et al. | 2023
- 46
-
The st-Planar Edge Completion Problem Is Fixed-Parameter TractableKhazaliya, Liana / Kindermann, Philipp / Liotta, Giuseppe / Montecchiani, Fabrizio / Simonov, Kirill et al. | 2023
- 47
-
A Combinatorial Certifying Algorithm for Linear Programming Problems with Gainfree Leontief Substitution SystemsKimura, Kei / Makino, Kazuhisa et al. | 2023
- 48
-
Reconfiguration of the Union of ArborescencesKobayashi, Yusuke / Mahara, Ryoga / Schwarcz, Tamás et al. | 2023
- 49
-
An Approximation Algorithm for Two-Edge-Connected Subgraph Problem via Triangle-Free Two-Edge-CoverKobayashi, Yusuke / Noguchi, Takashi et al. | 2023
- 50
-
On Min-Max Graph Balancing with Strict Negative Correlation ConstraintsKuo, Ting-Yu / Chen, Yu-Han / Frosini, Andrea / Hsieh, Sun-Yuan / Tsai, Shi-Chun / Kao, Mong-Jen et al. | 2023
- 51
-
On the Line-Separable Unit-Disk Coverage and Related ProblemsLiu, Gang / Wang, Haitao et al. | 2023
- 52
-
Improved Smoothed Analysis of 2-Opt for the Euclidean TSPManthey, Bodo / van Rhijn, Jesse et al. | 2023
- 53
-
On the Complexity of the Eigenvalue Deletion ProblemMisra, Neeldhara / Mittal, Harshil / Saurabh, Saket / Thakkar, Dhara et al. | 2023
- 54
-
Connected Vertex Cover on AT-Free GraphsMukherjee, Joydeep / Saha, Tamojit et al. | 2023
- 55
-
On the Fine-Grained Query Complexity of Symmetric FunctionsPodder, Supartha / Yao, Penghui / Ye, Zekun et al. | 2023
- 56
-
Testing Properties of Distributions in the Streaming ModelRoy, Sampriti / Vasudev, Yadu et al. | 2023
- 57
-
A Strongly Polynomial-Time Algorithm for Weighted General Factors with Three Feasible DegreesShao, Shuai / Živný, Stanislav et al. | 2023