×

Found 87 Documents (Results 1–87)

Submodular optimization with contention resolution extensions. (English) Zbl 07650070

Achlioptas, Dimitris (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques, 22nd international conference, APPROX 2019, and 23rd international conference, RANDOM 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, September 20–22, 2019. Proceedings. Wadern: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 145, Article 3, 17 p. (2019).
MSC:  68W20 68W25 90C27
PDFBibTeX XMLCite
Full Text: DOI

A bi-criteria approximation algorithm for \(k\)-means. (English) Zbl 1398.68680

Jansen, Klaus (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. Proceedings of the 19th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2016, and the 20th international workshop on randomization and computation, RANDOM 2016, Paris, France, September 7–9, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-018-7). LIPIcs – Leibniz International Proceedings in Informatics 60, Article 14, 20 p. (2016).
MSC:  68W25 62H30 90C59
PDFBibTeX XMLCite
Full Text: DOI arXiv

Optimal approximation for submodular and supermodular optimization with bounded curvature. (English) Zbl 1371.90143

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1134-1148 (2015).
PDFBibTeX XMLCite
Full Text: DOI arXiv

New approximations for broadcast scheduling via variants of \(\alpha\)-point rounding. (English) Zbl 1372.68047

Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1050-1069 (2015).
MSC:  68M20 68W25 90B35
PDFBibTeX XMLCite
Full Text: DOI

Stochastic scheduling on unrelated machines. (English) Zbl 1359.68039

Mayr, Ernst W. (ed.) et al., 31st international symposium on theoretical aspects of computer science, STACS’ 14, Lyon, France, March 5–8, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-65-1). LIPIcs – Leibniz International Proceedings in Informatics 25, 639-650 (2014).
MSC:  68M20 68W25 90B36
PDFBibTeX XMLCite
Full Text: DOI

Submodular stochastic probing on matroids. (English) Zbl 1359.90111

Mayr, Ernst W. (ed.) et al., 31st international symposium on theoretical aspects of computer science, STACS’ 14, Lyon, France, March 5–8, 2014. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-65-1). LIPIcs – Leibniz International Proceedings in Informatics 25, 29-40 (2014).
PDFBibTeX XMLCite
Full Text: DOI

Polynomial-time approximation schemes for circle packing problems. (English) Zbl 1425.68437

Schulz, Andreas S. (ed.) et al., Algorithms – ESA 2014. 22nd annual European symposium, Wrocław, Poland, September 8–10, 2014. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8737, 713-724 (2014).
PDFBibTeX XMLCite
Full Text: DOI

Integrated supply chain management via randomized rounding. (English) Zbl 1406.90018

Pardo, Alberto (ed.) et al., LATIN 2014: theoretical informatics. 11th Latin American symposium, Montevideo, Uruguay, March 31 – April 4, 2014. Proceedings. Berlin: Springer (ISBN 978-3-642-54422-4/pbk). Lecture Notes in Computer Science 8392, 562-573 (2014).
MSC:  90B06 68W25 90B05
PDFBibTeX XMLCite
Full Text: DOI

Energy efficient scheduling and routing via randomized rounding. (English) Zbl 1359.68034

Seth, Anil (ed.) et al., 33nd international conference on foundations of software technology and theoretical computer science, FSTTCS 2013, Guwahati, India, December 12–14, 2013. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-64-4). LIPIcs – Leibniz International Proceedings in Informatics 24, 449-460 (2013).
PDFBibTeX XMLCite
Full Text: DOI arXiv

No-wait flowshop scheduling is as hard as asymmetric traveling salesman problem. (English) Zbl 1336.90041

Fomin, Fedor V. (ed.) et al., Automata, languages, and programming. 40th international colloquium, ICALP 2013, Riga, Latvia, July 8–12, 2013, Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-39205-4/pbk). Lecture Notes in Computer Science 7965, 769-779 (2013).
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximation algorithms for the joint replenishment problem with deadlines. (English) Zbl 1336.68289

Fomin, Fedor V. (ed.) et al., Automata, languages, and programming. 40th international colloquium, ICALP 2013, Riga, Latvia, July 8–12, 2013, Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-39205-4/pbk). Lecture Notes in Computer Science 7965, 135-147 (2013).
MSC:  68W25 68Q17 90B06
PDFBibTeX XMLCite
Full Text: DOI arXiv

Approximating the configuration-LP for minimizing weighted sum of completion times on unrelated machines. (English) Zbl 1377.90034

Goemans, Michel (ed.) et al., Integer programming and combinatorial optimization. 16th international conference, IPCO 2013, Valparaíso, Chile, March 18–20, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36693-2/pbk). Lecture Notes in Computer Science 7801, 387-398 (2013).
MSC:  90B35 68W25 90C05
PDFBibTeX XMLCite
Full Text: DOI

An efficient polynomial-time approximation scheme for the joint replenishment problem. (English) Zbl 1377.90007

Goemans, Michel (ed.) et al., Integer programming and combinatorial optimization. 16th international conference, IPCO 2013, Valparaíso, Chile, March 18–20, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-36693-2/pbk). Lecture Notes in Computer Science 7801, 314-323 (2013).
PDFBibTeX XMLCite
Full Text: DOI

Concentration inequalities for nonlinear matroid intersection. (English) Zbl 1423.05036

Rabani, Yuval (ed.), Proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 420-436 (2012).
MSC:  05B35 68W25
PDFBibTeX XMLCite
Full Text: Link

New and improved bounds for the minimum set cover problem. (English) Zbl 1372.68306

Gupta, Anupam (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 15th international workshop, APPROX 2012, and 16th international workshop, RANDOM 2012, Cambridge, MA, USA, August 15–17, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32511-3/pbk). Lecture Notes in Computer Science 7408, 288-300 (2012).
MSC:  68W25 68Q17 90C27
PDFBibTeX XMLCite
Full Text: DOI

Preemptive and non-preemptive generalized min sum set cover. (English) Zbl 1245.68250

Dürr, Christoph (ed.) et al., STACS 2012. 29th international symposium on theoretical aspects of computer science, Paris, France, February 29th – March 3rd, 2012. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-35-4). LIPIcs – Leibniz International Proceedings in Informatics 14, 465-476, electronic only (2012).
MSC:  68W25 68Q17 90C27
PDFBibTeX XMLCite
Full Text: DOI

Maximizing polynomials subject to assignment constraints. (English) Zbl 1334.68302

Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 510-520 (2011).
PDFBibTeX XMLCite
Full Text: DOI

Matroid matching: the power of local search. (English) Zbl 1293.05035

Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-817-9). 369-378 (2010).
PDFBibTeX XMLCite
Full Text: DOI

Maximum quadratic assignment problem: reduction from maximum label cover and LP-based approximation algorithm. (English) Zbl 1288.68273

Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). Lecture Notes in Computer Science 6198, 594-604 (2010).
MSC:  68W25 90B80 90C35
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the maximum quadratic assignment problem. (English) Zbl 1423.90234

Mathieu, Claire (ed.), Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA 2009, New York, NY, USA, January 4–6, 2009. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 516-524 (2009).
PDFBibTeX XMLCite
Full Text: Link

Non-monotone submodular maximization under matroid and knapsack constraints. (English) Zbl 1304.90173

Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09. Bethesda, MD, USA, May 31 – June 2, 2009. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-613-7). 323-332 (2009).
MSC:  90C27 68W25
PDFBibTeX XMLCite
Full Text: DOI arXiv

A structural lemma in 2-dimensional packing, and its implications on approximability. (English) Zbl 1272.52018

Dong, Yingfei (ed.) et al., Algorithms and computation. 20th international symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16–18, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-10630-9/pbk). Lecture Notes in Computer Science 5878, 77-86 (2009).
MSC:  52B55 68W25
PDFBibTeX XMLCite
Full Text: DOI

Submodular maximization over multiple matroids via generalized exchange properties. (English) Zbl 1255.90106

Dinur, Irit (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 12th international workshop, APPROX 2009, and 13th international workshop, RANDOM 2009, Berkeley, CA, USA, August 21–23, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03684-2/pbk). Lecture Notes in Computer Science 5687, 244-257 (2009).
MSC:  90C27 05B35 68W25
PDFBibTeX XMLCite
Full Text: DOI

Online make-to-order joint replenishment model: Primal dual competitive algorithms. (English) Zbl 1192.90005

Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, January 20–22, 2008. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-898716-47-4). 952-961 (2008).
MSC:  90B05 90-04 68W25
PDFBibTeX XMLCite

Min sum edge coloring in multigraphs via configuration LP. (English) Zbl 1143.90334

Lodi, Andrea (ed.) et al., Integer programming and combinatorial optimization. 13th international conference, IPCO 2008 Bertinoro, Italy, May 26–28, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-68886-0/pbk). Lecture Notes in Computer Science 5035, 359-373 (2008).
PDFBibTeX XMLCite
Full Text: DOI

Harmonic algorithm for \(3\)-dimensional strip packing problem. (English) Zbl 1302.90165

Proceedings of the eighteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2007, New Orleans, LA, USA, January 7–9, 2007. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-0-89871-624-5). 1197-1206 (2007).
MSC:  90C27 68W25
PDFBibTeX XMLCite

Bundle pricing with comparable items. (English) Zbl 1151.91445

Arge, Lars (ed.) et al., Algorithms – ESA 2007. 15th annual European symposium, Eilat, Israel, October 8–10, 2007, Proceedings. Berlin: Springer (ISBN 978-3-540-75519-7/pbk). Lecture Notes in Computer Science 4698, 475-486 (2007).
MSC:  91B24 68Q17 68Q25
PDFBibTeX XMLCite
Full Text: DOI

Approximation algorithms for the multi-item capacitated lot-sizing problem via flow-cover inequalities. (English) Zbl 1136.90408

Fischetti, Matteo (ed.) et al., Integer programming and combinatorial optimization. 12th international IPCO conference, Ithaca, NY, USA, June 25–27, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-72791-0/pbk). Lecture Notes in Computer Science 4513, 454-468 (2007).
PDFBibTeX XMLCite
Full Text: DOI

The Santa Claus problem. (English) Zbl 1301.90057

Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 31-40 (2006).
PDFBibTeX XMLCite
Full Text: DOI

Tight approximation algorithms for maximum general assignment problems. (English) Zbl 1192.90105

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 611-620 (2006).
MSC:  90B80 68W25
PDFBibTeX XMLCite
Full Text: DOI

Improved approximation algorithms for broadcast scheduling. (English) Zbl 1192.90061

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-605-5). 344-353 (2006).
MSC:  90B35 68W25
PDFBibTeX XMLCite
Full Text: DOI Link

Improved approximation algorithm for the one-warehouse multi-retailer problem. (English) Zbl 1155.90311

Díaz, Josep (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 9th international workshop on approximation algorithms for combinatorial optimization problems, APPROX 2006, and 10th international workshop on randomization and computation, RANDOM 2006, Barcelona, Spain, August 28–30, 2006. Proceedings. Berlin: Springer (ISBN 3-540-38044-2/pbk). Lecture Notes in Computer Science 4110, 188-199 (2006).
MSC:  90B05 68W25
PDFBibTeX XMLCite
Full Text: DOI

Job shop scheduling with unit processing times. (English) Zbl 1297.68039

Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2005, Vancouver, BC, Canada, January 23–25, 2005. New York, NY: ACM Press (ISBN 0-89871-585-7). 207-214 (2005).
MSC:  68M20 68W25 68W20
PDFBibTeX XMLCite

Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems. (English) Zbl 1161.68874

Dehne, Frank (ed.) et al., Algorithms and data structures. 9th international workshop, WADS 2005, Waterloo, Canada, August 15–17, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28101-0/pbk). Lecture Notes in Computer Science 3608, 350-359 (2005).
MSC:  68W25 90C35 90C59
PDFBibTeX XMLCite
Full Text: DOI

New approximability and inapproximability results for 2-dimensional bin packing. (English) Zbl 1317.68269

Proceedings of the fifteenth annual ACM-SIAM symposium on discrete algorithms, SODA 2004, New Orleans, LA, USA, January 11–13, 2004. New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-558-X). 196-203 (2004).
PDFBibTeX XMLCite

Approximating asymmetric maximum TSP. (English) Zbl 1176.90608

Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, Baltimore, MD, USA, January 12–14, 2003. New York, NY: Association for Computing Machinery; Philadelphia, PA: Society for Industrial and Applied Mathematics (ISBN 0-89871-538-5/pbk). 646-654 (2003).
MSC:  90C35 68W25
PDFBibTeX XMLCite

Approximations for maximum transportation problem with permutable supply vector and other capacitated star packing problems. (English) Zbl 1078.90511

Penttonen, Martti (ed.) et al., Algorithm theory - SWAT 2002. 8th Scandinavian workshop, Turku, Finland, July 3–5, 2002. Proceedings. Berlin: Springer (ISBN 3-540-43866-1). Lect. Notes Comput. Sci. 2368, 280-287 (2002).
PDFBibTeX XMLCite
Full Text: DOI

A \((2+\varepsilon)\)-approximation algorithm for generalized preemptive open shop problem with minsum objective. (English) Zbl 1010.90506

Aardal, Karen (ed.) et al., Integer programming and combinatorial optimization. 8th international IPCO conference, Utrecht, Netherlands, June 13-15, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2081, 361-369 (2001).
MSC:  90B35 68W25 68Q25
PDFBibTeX XMLCite
Full Text: Link

An approximation algorithm for MAX DICUT with given sizes of parts. (English) Zbl 0976.05060

Jansen, Klaus (ed.) et al., Approximation algorithms for combinatorial optimization. 3rd international workshop, APPROX 2000, Saarbrücken, Germany, September 5-8, 2000. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1913, 34-41 (2000).
MSC:  05C85 68W25
PDFBibTeX XMLCite

Makespan minimization in job shops: a polynomial time approximation scheme. (English) Zbl 1345.90044

Vitter, Jeffrey Scott (ed.) et al., Proceedings of the 31st annual ACM symposium on theory of computing, STOC 1999. Atlanta, GA, USA, May 1–4, 1999. New York, NY: ACM, Association for Computing Machinery (ISBN 1-58113-067-8). 394-399 (1999).
MSC:  90B35 68W25 90C59
PDFBibTeX XMLCite
Full Text: DOI

Approximation algorithms for maximum coverage and max cut with given sizes of parts. (English) Zbl 0948.90122

Cornuéjols, Gérard (ed.) et al., Integer programming and combinatorial optimization. 7th international IPCO conference, Graz, Austria, June 9-11, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1610, 17-30 (1999).
MSC:  90C27 90C59
PDFBibTeX XMLCite

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

Software