Search results for "pseudo-polynomial"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
53	Daniel Lokshtanov, Jesper Nederlof	Saving space by algebraization.	STOC	2010	DBLP DOI BibTeX RDF	moebius, dynamic programming, space efficient, fourier
45	Siming Huang	Inverse Problems of Some NP-Complete Problems.	AAIM	2005	DBLP DOI BibTeX RDF	pseudo-polynomial algorithm, integer programming, Inverse problem, Knapsack problem
43	Jeng-Liang Tsai, Tsung-Hao Chen, Charlie Chung-Ping Chen	Optimal minimum-delay/area zero-skew clock tree wire-sizing in pseudo-polynomial time.	ISPD	2003	DBLP DOI BibTeX RDF	?-optimal, incremental refinement, pseudo-polynomial, clock tree, wire-sizing, zero-skew
28	Florian Berger, Rolf Klein	A traveller's problem.	SCG	2010	DBLP DOI BibTeX RDF	affine mappings, continuous dijkstra, frogger, pseudo-polynomial approximation, computational geometry, partition, np-hardness, motion planning, undecidability
28	Mark Cieliebak, Stephan J. Eidenbenz, Aris Pagourtzis	Composing Equipotent Teams.	FCT	2003	DBLP DOI BibTeX RDF
25	Rodolfo Pellizzoni, Giuseppe Lipari	A New Sufficient Feasibility Test for Asynchronous Real-Time Periodic Task Sets.	ECRTS	2004	DBLP DOI BibTeX RDF
23	Lisa Fleischer, Martin Skutella	The Quickest Multicommodity Flow Problem.	IPCO	2002	DBLP DOI BibTeX RDF
22	Ferdinando Cicalese, Eduardo Sany Laber	On the competitive ratio of evaluating priced functions.	SODA	2006	DBLP DOI BibTeX RDF
22	Samarjit Chakraborty, Thomas Erlebach, Lothar Thiele	On the Complexity of Scheduling Conditional Real-Time Code.	WADS	2001	DBLP DOI BibTeX RDF
22	Roberto Aringhieri, Andrea Grosso, Pierre Hosteins, Rosario Scatamacchia	Polynomial and pseudo-polynomial time algorithms for different classes of the Distance Critical Node Problem.	Discret. Appl. Math.	2019	DBLP DOI BibTeX RDF
22	Noriyuki Fujimoto	A Pseudo-Polynomial Time Algorithm for Solving the Knapsack Problem in Polynomial Space.	COCOA	2016	DBLP DOI BibTeX RDF
22	Evgeny R. Gafarov, Alexander A. Lazarev, Frank Werner 0001	Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one.	Ann. Oper. Res.	2012	DBLP DOI BibTeX RDF
22	Yunlong Liu, Xiaodong Wu	Fast Coupled Path Planning: From Pseudo-Polynomial to Polynomial.	COCOON	2010	DBLP DOI BibTeX RDF
20	Sudipta Sengupta	Algorithms and Approximation Schemes for Minimum Lateness/Tardiness Scheduling with Rejection.	WADS	2003	DBLP DOI BibTeX RDF
19	Hua Gong, Lixin Tang	The Coordination of Two Parallel Machines Scheduling and Batch Deliveries.	COCOON	2008	DBLP DOI BibTeX RDF
17	Hans L. Bodlaender, Richard B. Tan, Thomas C. van Dijk, Jan van Leeuwen	Integer Maximum Flow in Wireless Sensor Networks with Energy Constraint.	SWAT	2008	DBLP DOI BibTeX RDF
17	Xiliang Zhong, Cheng-Zhong Xu 0001	System-wide energy minimization for real-time tasks: lower bound and approximation.	ICCAD	2006	DBLP DOI BibTeX RDF
17	Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige	Minimum Cost Source Location Problems with Flow Requirements.	LATIN	2006	DBLP DOI BibTeX RDF
17	Rodolfo Pellizzoni, Giuseppe Lipari	Feasibility Analysis of Real-Time Periodic Tasks with Offsets.	Real Time Syst.	2005	DBLP DOI BibTeX RDF	scheduling, real-time systems
17	Yash P. Aneja, R. Chandrasekaran, K. P. K. Nair	Minimal-cost system reliability with discrete-choice sets for components.	IEEE Trans. Reliab.	2004	DBLP DOI BibTeX RDF
17	Terence Kelly	Generalized Knapsack Solvers for Multi-unit Combinatorial Auctions: Analysis and Application to Computational Resource Allocation.	AMEC	2004	DBLP DOI BibTeX RDF
17	Wing Ning	Strongly NP-hard discrete gate-sizing problems.	IEEE Trans. Comput. Aided Des. Integr. Circuits Syst.	1994	DBLP DOI BibTeX RDF
15	Marcel Morales, Nguyen Thi Dung	A "pseudo-polynomial" algorithm for the Frobenius number and Gröbner basis.	J. Symb. Comput.	2024	DBLP DOI BibTeX RDF
15	Mohammed Lalou, Hamamache Kheddouci	Pseudo-polynomial algorithms for solving the Knapsack Problem with dependencies between items.	Comput. Oper. Res.	2023	DBLP DOI BibTeX RDF
15	Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan 0001, Saket Saurabh 0001	On the optimality of pseudo-polynomial algorithms for integer programming.	Math. Program.	2023	DBLP DOI BibTeX RDF
15	Ferenc Illés	Linearly representable games and pseudo-polynomial calculation of the Shapley value.	CoRR	2022	DBLP DOI BibTeX RDF
15	Pierre Bourhis, Laurence Duchien, Jérémie Dusart, Emmanuel Lonca, Pierre Marquis, Clément Quinton	Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits.	CoRR	2022	DBLP BibTeX RDF
15	Kanstantsin Pashkovich	Computing the nucleolus of weighted voting games in pseudo-polynomial time.	Math. Program.	2022	DBLP DOI BibTeX RDF
15	Masato Tanaka, Tomomi Matsui	Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games.	Math. Soc. Sci.	2022	DBLP DOI BibTeX RDF
15	Masato Tanaka, Tomomi Matsui	Pseudo Polynomial Size LP Formulation for Calculating the Least Core Value of Weighted Voting Games.	CoRR	2021	DBLP BibTeX RDF
15		Retracted: A novel pseudo-polynomial approach for shortest paths problems.	Networks	2021	DBLP DOI BibTeX RDF
15	Milos Danilovic, Dragan Vasiljevic, Biljana Cvetic	A novel pseudo-polynomial approach for shortest path problems.	Networks	2021	DBLP DOI BibTeX RDF
15	Maxence Delorme, Manuel Iori	Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems.	INFORMS J. Comput.	2020	DBLP DOI BibTeX RDF
15	Rei Mizuta	Pseudo-Polynomial Time Algorithm for Computing Moments of Polynomials in Free Semicircular Elements.	CoRR	2019	DBLP BibTeX RDF
15	Adam N. Letchford, Juan José Salazar González	The Capacitated Vehicle Routing Problem: Stronger bounds in pseudo-polynomial time.	Eur. J. Oper. Res.	2019	DBLP DOI BibTeX RDF
15	Dmitry I. Arkhipov, Olga Battaïa, Alexander A. Lazarev	An efficient pseudo-polynomial algorithm for finding a lower bound on the makespan for the Resource Constrained Project Scheduling Problem.	Eur. J. Oper. Res.	2019	DBLP DOI BibTeX RDF
15	Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino	A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions.	Inf. Comput.	2019	DBLP DOI BibTeX RDF
15	Soh Kumabe, Takanori Maehara, Ryoma Sin'ya	Linear Pseudo-Polynomial Factor Algorithm for Automaton Constrained Tree Knapsack Problem.	WALCOM	2019	DBLP DOI BibTeX RDF
15	Klaus Jansen, Malin Rau	Closing the Gap for Pseudo-Polynomial Strip Packing.	ESA	2019	DBLP DOI BibTeX RDF
15	Waldo Gálvez, Fabrizio Grandoni 0001, Salvatore Ingala, Arindam Khan 0001	Improved Pseudo-Polynomial-Time Approximation for Strip Packing.	CoRR	2018	DBLP BibTeX RDF
15	Soh Kumabe, Takanori Maehara, Ryoma Sin'ya	Linear Pseudo-Polynomial Factor Algorithm for Automaton Constrained Tree Knapsack Problem.	CoRR	2018	DBLP BibTeX RDF
15	Jatin Batra, Naveen Garg 0001, Amit Kumar 0001	Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-polynomial time.	CoRR	2018	DBLP BibTeX RDF
15	Kanstantsin Pashkovich	Computing the Nucleolus of Weighted Voting Games in Pseudo-polynomial Time.	CoRR	2018	DBLP BibTeX RDF
15	Jatin Batra, Naveen Garg 0001, Amit Kumar 0001	Constant Factor Approximation Algorithm for Weighted Flow Time on a Single Machine in Pseudo-Polynomial Time.	FOCS	2018	DBLP DOI BibTeX RDF
15	Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan 0001, Saket Saurabh 0001	On the Optimality of Pseudo-polynomial Algorithms for Integer Programming.	ESA	2018	DBLP DOI BibTeX RDF
15	Yoshiyuki Karuno, Oki Nakahama	Pseudo-Polynomial Time Algorithms for Producing Cardinality Constrained Packages by Multi-Head Weighers.	SCIS&ISIS	2018	DBLP DOI BibTeX RDF
15	Carlo Comin, Romeo Rizzi	Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games.	Algorithmica	2017	DBLP DOI BibTeX RDF
15	Klaus Jansen, Malin Rau	Closing the gap for pseudo-polynomial strip packing.	CoRR	2017	DBLP BibTeX RDF
15	François Clautiaux, Saïd Hanafi, Rita Macedo, Marie-Emilie Voge, Cláudio Alves	Iterative aggregation and disaggregation algorithm for pseudo-polynomial network flow models with side constraints.	Eur. J. Oper. Res.	2017	DBLP DOI BibTeX RDF
15	Nuno Braga, Cláudio Alves, Rita Macedo	Exact Solution of the Multi-trip Inventory Routing Problem using a Pseudo-polynomial Model.	ICORES	2017	DBLP DOI BibTeX RDF
15	Jürgen Rietz, Cláudio Alves, Nuno Braga, José M. Valério de Carvalho	An exact approach based on a new pseudo-polynomial network flow model for integrated planning and scheduling.	Comput. Oper. Res.	2016	DBLP DOI BibTeX RDF
15	Shuaian Wang	Fundamental properties and pseudo-polynomial-time algorithm for network containership sailing speed optimization.	Eur. J. Oper. Res.	2016	DBLP DOI BibTeX RDF
15	Waldo Gálvez, Fabrizio Grandoni 0001, Salvatore Ingala, Arindam Khan 0001	Improved Pseudo-Polynomial-Time Approximation for Strip Packing.	FSTTCS	2016	DBLP DOI BibTeX RDF
15	Yuichi Sudo, Toshimitsu Masuzawa, Gen Motoyoshi, Tutomu Murase	Pseudo Polynomial Time Algorithms for Optimal Longcut Route Selection.	IEICE Trans. Inf. Syst.	2015	DBLP DOI BibTeX RDF
15	Özgür Özpeynirci, Cansu Kandemir	A Pseudo-Polynomial Time Algorithm for a Special Multiobjective Order Picking Problem.	Int. J. Inf. Technol. Decis. Mak.	2015	DBLP DOI BibTeX RDF
15	Marcin Jurdzinski, Ranko Lazic 0001, Sylvain Schmitz	Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time.	CoRR	2015	DBLP BibTeX RDF
15	Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino	A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and Few Random Positions.	CoRR	2015	DBLP BibTeX RDF
15	Carlo Comin, Romeo Rizzi	An Improved Pseudo-Polynomial Upper Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games.	CoRR	2015	DBLP BibTeX RDF
15	Dvir Shabtay, George Steiner, Liron Yedidsion	A pseudo-polynomial time algorithm for solving the resource dependent assignment problem.	Discret. Appl. Math.	2015	DBLP DOI BibTeX RDF
15	Marcin Jurdzinski, Ranko Lazic 0001, Sylvain Schmitz	Fixed-Dimensional Energy Games are in Pseudo-Polynomial Time.	ICALP (2)	2015	DBLP DOI BibTeX RDF
15	Oskar Skibski, Tomasz P. Michalak, Yuko Sakurai, Makoto Yokoo	A Pseudo-Polynomial Algorithm for Computing Power Indices in Graph-Restricted Weighted Voting Games.	IJCAI	2015	DBLP BibTeX RDF
15	Miguel Couceiro, Tamás Waldhauser	Pseudo-polynomial functions over finite distributive lattices.	Fuzzy Sets Syst.	2014	DBLP DOI BibTeX RDF
15	Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Kazuhisa Makino	A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Random Positions.	ICALP (1)	2013	DBLP DOI BibTeX RDF
15	José Federico Vizcaino González, Christiano Lyra, Fábio Luiz Usberti	A pseudo-polynomial algorithm for optimal capacitor placement on electric power distribution networks.	Eur. J. Oper. Res.	2012	DBLP DOI BibTeX RDF
15	Marie-Emilie Voge, François Clautiaux	Theoretical Investigation of Aggregation in Pseudo-polynomial Network-Flow Models.	ISCO	2012	DBLP DOI BibTeX RDF
15	Rita Macedo, Cláudio Alves, José M. Valério de Carvalho, François Clautiaux, Saïd Hanafi	Solving the vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model.	Eur. J. Oper. Res.	2011	DBLP DOI BibTeX RDF
15	Ajay Kumar Bangla, David A. Castañón	Pseudo-polynomial auction algorithm for Nonlinear Resource Allocation.	ACC	2011	DBLP DOI BibTeX RDF
15	Miguel Couceiro, Tamás Waldhauser	Pseudo-polynomial Functions over Finite Distributive Lattices.	ECSQARU	2011	DBLP DOI BibTeX RDF
15	Hassene Aissi, Cristina Bazgan, Daniel Vanderpooten	General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems.	Discret. Optim.	2010	DBLP DOI BibTeX RDF
15	Sung-Pil Hong, Sung-Jin Cho, Myoung-Ju Park	A pseudo-polynomial heuristic for path-constrained discrete-time Markovian-target search.	Eur. J. Oper. Res.	2009	DBLP DOI BibTeX RDF
15	Giovanni Incerti	Vibration control of a SCARA manipulator using pseudo-polynomial motion laws.	IROS	2008	DBLP DOI BibTeX RDF
15	Simone G. O. Fiori, Pietro Burrascano	Analytical results on pseudo-polynomial functional-link neural units for blind density shaping.	IJCNN	1999	DBLP DOI BibTeX RDF
15	Takahito Kuno, Takahiro Utsunomiya	A Pseudo-Polynomial Primal-Dual Algorithm for Globally Solving a Production-Transportation Problem.	J. Glob. Optim.	1997	DBLP DOI BibTeX RDF
15	Paolo M. Camerini, Giulia Galbiati, Francesco Maffioli	Random Pseudo-Polynomial Algorithms for Exact Matroid Problems.	J. Algorithms	1992	DBLP DOI BibTeX RDF
14	Thi Huyen Chau Nguyen, Pascal Richard, Enrico Bini	Approximation techniques for response-time analysis of static-priority tasks.	Real Time Syst.	2009	DBLP DOI BibTeX RDF	Uniprocessor real-time scheduling, Static-priority tasks, Approximation scheme, Worst-case response time
14	Alejandro Masrur, Sebastian Drössler, Georg Färber	Improvements in Polynomial-Time Feasibility Testing for EDF.	DATE	2008	DBLP DOI BibTeX RDF
14	Hans L. Bodlaender, Alexander Grigoriev, Nadejda V. Grigorieva, Albert Hendriks	The Valve Location Problem in Simple Network Topologies.	WG	2008	DBLP DOI BibTeX RDF	Valve location problem, computational complexity, dynamic programming, binary search, bounded treewidth
14	Lei Li, Jun Wei 0001, Tao Huang 0001	High Performance Approach for Multi-QoS Constrained Web Services Selection.	ICSOC	2007	DBLP DOI BibTeX RDF
14	Sushu Zhang, Karam S. Chatha	Approximation algorithm for the temperature-aware scheduling problem.	ICCAD	2007	DBLP DOI BibTeX RDF
14	Yuichi Asahiro, Jesper Jansson 0001, Eiji Miyano, Hirotaka Ono 0001, Kouhei Zenmyo	Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree.	AAIM	2007	DBLP DOI BibTeX RDF
14	Prabha Sharma	Algorithms for the optimum communication spanning tree problem.	Ann. Oper. Res.	2006	DBLP DOI BibTeX RDF	Cost of communication, Cut-tree, Star-tree, Adjacent spanning tree, Adjacent basic feasible solution
14	Noureddine Kettaf, Abdelhafid Abouaissa, Thang Vu Duong, Pascal Lorenz	An efficient QoS routing algorithm for solving MCP in ad hoc networks.	Telecommun. Syst.	2006	DBLP DOI BibTeX RDF	Ad hoc, QoS routing, Path selection, Multiple constraints
14	Eranda Çela, Bettina Klinz, Christophe Meyer	Polynomially solvable cases of the constant rank unconstrained quadratic 0-1 programming problem.	J. Comb. Optim.	2006	DBLP DOI BibTeX RDF	Quadratic 0-1 programming, Special case, Constant rank matrix, Stable sets, Local minima
14	Nathan Fisher, Sanjoy K. Baruah	A Fully Polynomial-Time Approximation Scheme for Feasibility Analysis in Static-Priority Systems with Arbitrary Relative Deadlines.	ECRTS	2005	DBLP DOI BibTeX RDF
14	Ying Xiao 0001, Krishnaiyan Thulasiraman, Guoliang Xue	Approximation and Heuristic Algorithms for Delay Constrained Path Selection under Inaccurate State Information.	QSHINE	2004	DBLP DOI BibTeX RDF
14	Turgay Korkmaz, Marwan Krunz	Routing multimedia traffic with QoS guarantees.	IEEE Trans. Multim.	2003	DBLP DOI BibTeX RDF
14	Pascal Berthomé, Madiagne Diallo, Afonso Ferreira	Generalized Parametric Multi-terminal Flows Problem.	WG	2003	DBLP DOI BibTeX RDF
14	Arye Barkan, Haim Kaplan	Partial Alphabetic Trees.	ESA	2002	DBLP DOI BibTeX RDF
14	Samarjit Chakraborty, Simon Künzli 0001, Lothar Thiele	Approximate Schedulability Analysis.	RTSS	2002	DBLP DOI BibTeX RDF
14	Xiaotie Deng, Chung Keung Poon, Yuzhong Zhang	Approximation Algorithms in Batch Processing.	ISAAC	1999	DBLP DOI BibTeX RDF
14	Manfred Wiegers	The k-section of Treewidth Restricted Graphs.	MFCS	1990	DBLP DOI BibTeX RDF
11	Franz-Josef Brandenburg, Mao-cheng Cai	Shortest Path and Maximum Flow Problems in Networks with Additive Losses and Gains.	FAW	2009	DBLP DOI BibTeX RDF	extended networks, lossy and gainy arcs, max-flow, unit-loss networks, shortest path, NP-hard
11	Sushu Zhang, Karam S. Chatha, Goran Konjevod	Near optimal battery-aware energy management.	ISLPED	2009	DBLP DOI BibTeX RDF	low power design, dynamic power management, dynamic voltage/frequency scaling
11	Xiliang Zhong, Cheng-Zhong Xu 0001	System-wide energy minimization for real-time tasks: Lower bound and approximation.	ACM Trans. Embed. Comput. Syst.	2008	DBLP DOI BibTeX RDF	Real-Time systems, dynamic voltage scaling, dynamic power management, power-aware scheduling
11	Jiayu Gong, Xiliang Zhong, Cheng-Zhong Xu 0001	Energy and Timing Constrained System Reward Maximization on Wireless Networks.	ICDCS	2008	DBLP DOI BibTeX RDF
11	Amitai Armon, Uri Zwick	Multicriteria Global Minimum Cuts.	Algorithmica	2006	DBLP DOI BibTeX RDF
11	Chung-Yee Lee, Joseph Y.-T. Leung, Gang Yu	Two Machine Scheduling under Disruptions with Transportation Considerations.	J. Sched.	2006	DBLP DOI BibTeX RDF	transportation, machine scheduling, disruption
11	Amitai Armon, Uri Zwick	Multicriteria Global Minimum Cuts.	ISAAC	2004	DBLP DOI BibTeX RDF
11	Feng Chu 0001, Chengbin Chu, Xiao Liu	Lot sizing models with backlog or out-sourcing.	SMC (5)	2004	DBLP DOI BibTeX RDF
11	Hadas Shachnai, Oded Shmueli, Robert Sayegh	Approximation Schemes for Deal Splitting and Covering Integer Programs with Multiplicity Constraints.	WAOA	2004	DBLP DOI BibTeX RDF