Special cases of the minimum spanning tree problem under explorable edge and vertex uncertainty. (English) Zbl 07819299
MSC:
90C35
Found 126 Documents (Results 1–100)
Fractionally subadditive maximization under an incremental knapsack constraint with applications to incremental flows. (English) Zbl 07809680
Randomized strategies for robust combinatorial optimization with approximate separation. (English) Zbl 07795035
Bounds on piercing and line-piercing numbers in families of convex sets in the plane. (English) Zbl 1530.52003
MSC:
52A10
Finding the edges in optimal Hamiltonian cycles based on frequency quadrilaterals. (English) Zbl 07789580
MSC:
68Qxx
An experimental evaluation of semidefinite programming and spectral algorithms for max cut. (English) Zbl 07887813
MSC:
68Wxx
Constant-competitiveness for random assignment matroid secretary without knowing the matroid. (English) Zbl 1528.91023
Del Pia, Alberto (ed.) et al., Integer programming and combinatorial optimization. 24th international conference, IPCO 2023, Madison, WI, USA, June 21–23, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13904, 423-437 (2023).
Query-based selection of optimal candidates under the Mallows model. (English) Zbl 07755523
MSC:
68Qxx
Round-competitive algorithms for uncertainty problems with parallel queries. (English) Zbl 1506.68182
The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals. (English) Zbl 1541.68440
Cai, Zhiping (ed.) et al., Theoretical computer science. 40th national conference, NCTCS 2022, Changchun, China, July 29–31, 2022. Revised selected papers. Singapore: Springer. Commun. Comput. Inf. Sci. 1693, 77-95 (2022).
Optimal prophet inequality with less than one sample. (English) Zbl 1535.93031
Hansen, Kristoffer Arnsfelt (ed.) et al., Web and internet economics. 18th international conference, WINE 2022, Troy, NY, USA, December 12–15, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13778, 115-131 (2022).
Online max-min fair allocation. (English) Zbl 1520.91208
Kanellopoulos, Panagiotis (ed.) et al., Algorithmic game theory. 15th international symposium, SAGT 2022, Colchester, UK, September 12–15, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13584, 526-543 (2022).
MSC:
91B32
Knapsack secretary through boosting. (English) Zbl 07717058
Chalermsook, Parinya (ed.) et al., Approximation and online algorithms. 20th international workshop, WAOA 2022, Potsdam, Germany, September 8–9, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13538, 61-81 (2022).
The secretary problem with distributions. (English) Zbl 1497.90179
Aardal, Karen (ed.) et al., Integer programming and combinatorial optimization. 23rd international conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13265, 429-439 (2022).
MSC:
90C27
Formal barriers to simple algorithms for the matroid secretary problem. (English) Zbl 1533.68411
Feldman, Michal (ed.) et al., Web and internet economics. 17th international conference, WINE 2021, Potsdam, Germany, December 14–17, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13112, 280-298 (2022).
On computational capabilities of Ising machines based on nonlinear oscillators. (English) Zbl 1492.68051
Prophet inequalities for independent and identically distributed random variables from an unknown distribution. (English) Zbl 1493.62492
On dominating set of some subclasses of string graphs. (English) Zbl 1496.05123
Reviewer: A. Lourdusamy (Palayamkottai)
Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains. (English) Zbl 1497.68516
Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes. (English) Zbl 1535.90060
Packing returning secretaries. (English) Zbl 1535.90127
Efficient two-sided markets with limited information. (English) Zbl 07765261
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 1452-1465 (2021).
MSC:
68Qxx
Revelation gap for pricing from samples. (English) Zbl 07765260
Khuller, Samir (ed.) et al., Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, STOC ’21, virtual, Italy, June 21–25, 2021. New York, NY: Association for Computing Machinery (ACM). 1438-1451 (2021).
MSC:
68Qxx
The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem. (English) Zbl 1512.90204
Cai, Zhiping (ed.) et al., Theoretical computer science. 39th national conference, NCTCS 2021, Yinchuan, China, July 23–25, 2021. Revised selected papers. Singapore: Springer. Commun. Comput. Inf. Sci. 1494, 177-195 (2021).
MSC:
90C27
Fractionally subadditive maximization under an incremental knapsack constraint. (English) Zbl 07603893
Koenemann, Jochen (ed.) et al., Approximation and online algorithms. 19th international workshop, WAOA 2021, Lisbon, Portugal, September 6–10, 2021. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12982, 206-223 (2021).
Robust online algorithms for dynamic choosing problems. (English) Zbl 07495154
De Mol, Liesbeth (ed.) et al., Connecting with computability. 17th conference on computability in Europe, CiE 2021, virtual event, Ghent, Belgium, July 5–9, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12813, 38-49 (2021).
MSC:
68Qxx
Piercing all translates of a set of axis-parallel rectangles. (English) Zbl 07495030
Flocchini, Paola (ed.) et al., Combinatorial algorithms. 32nd international workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12757, 295-309 (2021).
A spectral partitioning algorithm for maximum directed cut problem. (English) Zbl 1480.90217
MSC:
90C27
The BRS-inequality and its applications. (English) Zbl 1475.60043
MSC:
60E15
Online contention resolution schemes with applications to Bayesian selection problems. (English) Zbl 1509.68339
On guillotine separability of squares and rectangles. (English) Zbl 07758349
Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 47, 22 p. (2020).
Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs. (English) Zbl 07758319
Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 17, 21 p. (2020).
A polyhedral study for the buy-at-bulk facility location problem. (English) Zbl 1458.90481
Baïou, Mourad (ed.) et al., Combinatorial optimization. 6th international symposium, ISCO 2020, Montreal, QC, Canada, May 4–6, 2020. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 12176, 42-53 (2020).
On Wegner’s inequality for axis-parallel rectangles. (English) Zbl 1454.51014
Reviewer: Martin Lukarevski (Skopje)
MSC:
51M16
The matroid secretary problem for minor-closed classes and random matroids. (English) Zbl 1431.05033
Online bin covering with limited migration. (English) Zbl 07525455
Bender, Michael A. (ed.) et al., 27th annual European symposium on algorithms, ESA 2019, Munich/Garching, Germany, September 9–11, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 144, Article 18, 14 p. (2019).
MSC:
68Wxx
Special frequency quadrilaterals and an application. (English) Zbl 1456.90139
Sun, Xiaoming (ed.) et al., Theoretical computer science. 37th national conference, NCTCS 2019, Lanzhou, China, August 2–4, 2019. Revised selected papers. Singapore: Springer. Commun. Comput. Inf. Sci. 1069, 16-26 (2019).
Dominating set on overlap graphs of rectangles intersecting a line. (English) Zbl 1534.68149
Du, Ding-Zhu (ed.) et al., Computing and combinatorics. 25th international conference, COCOON 2019, Xi’an, China, July 29–31, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11653, 65-77 (2019).
Prior independent mechanisms via prophet inequalities with limited information. (English) Zbl 1429.91169
Secretary markets with local information. (English) Zbl 1447.91083
MSC:
91B39
Some results about the contractions and the pendant pairs of a submodular system. (English) Zbl 1438.90285
MSC:
90C27
Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames. (English) Zbl 1425.05108
Covering and packing of triangles intersecting a straight line. (English) Zbl 1522.68671
Pal, Sudebkumar Prasant (ed.) et al., Algorithms and discrete applied mathematics. 5th international conference, CALDAM 2019, Kharagpur, India, February 14–16, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11394, 216-230 (2019).
The best-or-worst and the postdoc problems with random number of candidates. (English) Zbl 1461.90115
Generalized laminar matroids. (English) Zbl 1414.05065
Matroid prophet inequalities and applications to multi-dimensional mechanism design. (English) Zbl 1419.91332
LP-based approximation algorithms for facility location in buy-at-bulk network design. (English) Zbl 1418.68242
Packing returning secretaries. (English) Zbl 1535.90126
Hsu, Wen-Lian (ed.) et al., 29th international symposium on algorithms and computation, ISAAC 2018, December 16–19, 2018, Jiaoxi, Yilan, Taiwan. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 123, Article 65, 12 p. (2018).
Approximating dominating set on intersection graphs of rectangles and L-frames. (English) Zbl 1512.68400
Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 37, 15 p. (2018).
Robust randomized matchings. (English) Zbl 1436.91087
A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem. (English) Zbl 1435.68376
Recognition and drawing of stick graphs. (English) Zbl 1435.68229
Biedl, Therese (ed.) et al., Graph drawing and network visualization. 26th international symposium, GD 2018, Barcelona, Spain, September 26–28, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11282, 303-316 (2018).
Randomized contractions for multiobjective minimum cuts. (English) Zbl 1442.68158
Pruhs, Kirk (ed.) et al., 25th European symposium on algorithms, ESA 2017, Vienna, Austria, September 4–6, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 87, Article 6, 13 p. (2017).
Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs. (English) Zbl 1387.90229
Polyhedral results for a class of cardinality constrained submodular minimization problems. (English) Zbl 1387.90167
A spectral partitioning algorithm for maximum directed cut problem. (English) Zbl 1470.68064
Gao, Xiaofeng (ed.) et al., Combinatorial optimization and applications. 11th international conference, COCOA 2017, Shanghai, China, December 16–18, 2017. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 10627, 298-312 (2017).
Decomposition theorems for square-free 2-matchings in bipartite graphs. (English) Zbl 1372.05176
MSC:
05C70
Approximation and online algorithms for multidimensional bin packing: a survey. (English) Zbl 1398.68007
Subquadratic submodular function minimization. (English) Zbl 1370.90206
Hatami, Hamed (ed.) et al., Proceedings of the 49th annual ACM SIGACT symposium on theory of computing, STOC ’17, Montreal, QC, Canada, June 19–23, 2017. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-4528-6). 1220-1231 (2017).
Filter Results by …
Document Type
- Journal Articles (92)
- Collection Articles (34)
all
top 5
Author
- Feldman, Moran (5)
- Levin, Asaf (5)
- Soto, José A. (5)
- Takazawa, Kenjiro (5)
- Zenklusen, Rico (5)
- Chakraborty, Dibyayan (4)
- Disser, Yann (4)
- Epstein, Leah (4)
- Hoefer, Martin (4)
- Pandit, Supantha (4)
- Berndt, Sebastian (3)
- Das, Sandip (3)
- Dumitrescu, Adrian (3)
- Felsner, Stefan (3)
- Grau, José María (3)
- Jansen, Klaus (3)
- Khan, Arindam (3)
- Kleinberg, Robert D. (3)
- Klimm, Max (3)
- Kobourov, Stephen G. (3)
- Maack, Marten (3)
- Svensson, Ola (3)
- Wang, Yong (3)
- Weinberg, Seth Matthew (3)
- Akaria, Islam (2)
- Bandyapadhyay, Sayan (2)
- Bayón, Luis (2)
- Beideman, Calvin (2)
- Chandrasekaran, Karthekeyan (2)
- Chaplick, Steven (2)
- Chen, Ning (2)
- Chepoi, Victor D. (2)
- Correa, José R. (2)
- De Luca, Felice (2)
- Du, Donglei (2)
- Dütting, Paul (2)
- Feuilloley, Laurent (2)
- Fife, Tara (2)
- Fortuny Ayuso, Pedro (2)
- Gravin, Nick (2)
- Hossain, Md. Iqbal (2)
- Kawase, Yasushi (2)
- Kobayashi, Yusuke (2)
- Künnemann, Marvin (2)
- Lin, Chengyu (2)
- Lubiw, Anna (2)
- Lukot’ka, Robert (2)
- Maheshwari, Anil (2)
- Mehrabi, Saeed (2)
- Miao, Peihan (2)
- Mondal, Debajyoti (2)
- Mukherjee, Joydeep (2)
- Oller-Marcén, Antonio M. (2)
- Oxley, James G. (2)
- Pérez-Lantero, Pablo (2)
- Ravi, Ramamoorthi (2)
- Rohwedder, Lars (2)
- Ruiz, Maria M. (2)
- Schewior, Kevin (2)
- Sumita, Hanna (2)
- Suri, Subhash (2)
- Tang, Zhihao Gavin (2)
- Tkadlec, Josef (2)
- van Zuylen, Anke (2)
- Weckbecker, David (2)
- Wilhelmi, Lisa (2)
- Williamson, David P. (2)
- Wu, Chenchen (2)
- Xu, Chao (2)
- Xu, Dachuan (2)
- Zhang, Dongmei (2)
- Zhang, Zhenning (2)
- Abels, Andreas (1)
- Ahmed, Shabbir (1)
- Aissi, Hassene (1)
- Albers, Susanne (1)
- Antoniadis, Antonios Foivos (1)
- Arulselvan, Ashwin (1)
- Ashur, Stav (1)
- Azar, Pablo Daniel (1)
- Bahrani, Maryam (1)
- Bernstein, Aaron (1)
- Beyhaghi, Hedyeh (1)
- Bhore, Sujoy Kumar (1)
- Bousquet, Nicolas (1)
- Boyd, Sylvia C. (1)
- Bruss, Franz Thomas (1)
- Čada, Roman (1)
- Caraballo, Luis-Evaristo (1)
- Catanzaro, Daniele (1)
- Çela, Eranda (1)
- Chakrabarty, Deeparnab (1)
- Chakraborty, Sourav (1)
- Chen, Ke (1)
- Chiba, Shuya (1)
- Christensen, Henrik I. (1)
- Das, Aparna (1)
- de Lima, Murilo Santos (1)
- Diarrassouba, Ibrahima (1)
- Dolati, Ardeshir (1)
- and 134 more Authors
all
top 5
Serial
- Algorithmica (10)
- SIAM J. Discrete Math. (7)
- J. Comb. Optim. (7)
- Discrete Appl. Math. (6)
- Math. Oper. Res. (6)
- Theor. Comput. Sci. (6)
- Comput. Geom. (5)
- Math. Program. (4)
- SIAM J. Comput. (3)
- Eur. J. Comb. (3)
- Discrete Optim. (3)
- Discrete Math. (2)
- Inf. Process. Lett. (2)
- Networks (2)
- Discrete Comput. Geom. (2)
- Games Econ. Behav. (2)
- Theory Comput. Syst. (2)
- Adv. Math. (1)
- J. Comb. Theory, Ser. B (1)
- J. Comput. Syst. Sci. (1)
- Oper. Res. Lett. (1)
- Physica D (1)
- Order (1)
- Linear Algebra Appl. (1)
- Distrib. Comput. (1)
- Electron. J. Comb. (1)
- INFORMS J. Comput. (1)
- Math. Methods Oper. Res. (1)
- RAIRO, Oper. Res. (1)
- ACM J. Exp. Algorithm. (1)
- Optim. Lett. (1)
- Probab. Surv. (1)
- J. Oper. Res. Soc. China (1)
- Comput. Sci. Rev. (1)
- Sahand Commun. Math. Anal. (1)
- Ural Math. J. (1)
- SN Oper. Res. Forum (1)
